c++ - 해시함수 - 해싱 장점




해싱 부동 소수점 값 (3)

비트 패턴을 사용하지 않는 한 가지 이유는 일부 다른 비트 패턴이 같음으로 간주되어 동일한 해시 코드를 가져야한다는 것입니다.

  • 양수 및 음수 0
  • 아마도 비정규 숫자 (IEEE 754에서 발생할 수 있다고 생각하지 않지만 C는 다른 부동 소수점 표현을 허용합니다).
  • 아마도 NAN (적어도 IEEE 754에는 많은 것들이 있습니다. 실제로 NAN 패턴이 그들 자신과 다른 것으로 간주되어야합니다. 이것은 분명히 해쉬 테이블에서 의미있게 사용될 수 없다는 것을 의미합니다)

최근에 나는 부동 소수점에 대한 해시 알고리즘이 어떻게 작동했는지 궁금해서 boost::hash_value 소스 코드를 살펴 보았습니다. 그것은 상당히 복잡 합니다. 실제 구현은 기수의 각 숫자를 반복하고 해시 값을 누적합니다. 정수 해시 함수와 비교하면 훨씬 더 복잡합니다.

내 질문은 : 왜 더 이상 부동 소수점 해시 알고리즘을해야합니까? 부동 소수점 값의 이진 표현을 정수처럼 해시하는 것이 어떨까요?

처럼:

std::size_t hash_value(float f)
{
  return hash_value(*(reinterpret_cast<int*>(&f)));
}

float 는 모든 시스템에서 int 와 크기가 동일하지는 않지만 float 과 동일한 크기의 정수 유형을 추론하기 위해 몇 가지 템플릿 메타 프로그램으로 처리 할 수 ​​있다는 것을 알고 있습니다. 그렇다면 특별히 부동 소수점 유형에서 작동하는 전혀 다른 해시 함수를 도입하면 어떤 이점이 있습니까?


왜 부동 소수점 값을 해시하고 싶습니까? 부동 소수점 값을 평등하게 비교하는 것과 같은 여러 가지 함정이있는 것과 같은 이유로 해시 함수는 유사한 (부정적인) 결과를 가질 수 있습니다.

그러나 당신이 정말로 이것을하고 싶다고 가정 할 때, 나는 부스트 알고리즘이 복잡하다는 것을 의심합니다. 왜냐하면 여러분이 계정을 비정규 화 한 숫자를 취할 때 다른 비트 패턴이 동일한 숫자를 나타낼 수 있기 때문입니다 (아마도 같은 해시를 가져야합니다). IEEE 754에는 또한 양의 값과 음의 값이 모두 동일하지만 서로 다른 비트 패턴을가집니다.

이것은 아마도 알고리즘에서 다르게 나타나지 않았지만 여전히 NaN 값을 시그널링하는 데 신경을 쓸 필요가 있다면 해싱에서 나오지 않을 것입니다.

또한 해시 +/- 무한대 및 / 또는 NaN의 의미는 무엇입니까? 특히 NaN은 많은 표현을 가질 수 있습니다. 모두 동일한 해시를 가져야합니까? 무한대는 단지 두 가지 표현이있는 것 같아서 괜찮아 보인다.


https://svn.boost.org/trac/boost/ticket/4038 에서 살펴보십시오.

본질적으로 그것은 두 가지로 요약됩니다 :

  • 이식성 : 부동 소수점의 이진 표현을 취하면 어떤 플랫폼에서는 동일한 값을 가진 부동 소수점이 이진수로 여러 표현을 가질 수 있습니다. 실제로 그런 문제가있는 플랫폼이 있는지는 모르겠지만 불법화 된 숫자의 합병으로 인해 실제로 발생할 수 있는지 확실하지 않습니다.

  • 두 번째 문제는 sizeof(float)sizeof(int) 같지 않을 수도 있다는 것입니다.

나는 부스트 해시가 실제로 적은 충돌을 피한다고 언급하는 사람을 찾지 못했습니다. 지수에서 가수를 분리하는 것이 도움이 될 수 있다고 생각하지만, 위의 링크는 이것이 운전 설계 결정이라고 제안하지 않습니다.





floating-point