C ++ 해시 테이블에 좋은 해시 기능이 있습니까?

StackOverflow https://stackoverflow.com/questions/628790

  •  07-07-2019
  •  | 
  •  

문제

코딩 할 해시 테이블의 C ++에서 성능 지향 해시 기능 구현이 필요합니다. 나는 이미 주변을 둘러 보았고 "일반적으로"좋은 해시 기능이 무엇인지 묻는 질문 만 발견했습니다. CRC32 (그러나 좋은 구현을 찾을 수있는 곳)와 몇 가지 암호화 알고리즘을 고려했습니다. 그러나 내 테이블에는 매우 구체적인 요구 사항이 있습니다.

테이블의 모습은 다음과 같습니다.

100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
     examples: "become"    "and he"    ", not "

그만큼 최우선 순위 내 해시 테이블의 빠른 검색 (검색)입니다. 빠른 삽입은 중요하지 않지만 빠른 검색과 함께 올 것입니다. 삭제가 중요하지 않으며, 다시 호흡하는 것은 내가 조사 할 것이 아닙니다. 충돌을 처리하려면 아마도 사용하겠습니다 별도의 체인 설명한대로 여기. 나는 이미 보았다 이 기사, 그러나 이전에 그러한 임무를 처리 한 사람들에 대한 의견을 원합니다.

도움이 되었습니까?

해결책

이제 해시를 원하고 무언가를 원한다고 가정합니다. 빨리 타오르는 당신의 줄은 단지 6 숯이 길기 때문에이 마법을 사용할 수 있기 때문에 그것은 당신의 경우에 효과가 있습니다.

size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
   return (*(size_t*)str)>> precision;
}

CRC는 Slowpokes를위한 것입니다;)

설명:이는 문자열 포인터의 내용을 "LOOK LIKE"SIZE_T (하드웨어의 최적 일치에 따라 int32 또는 int64)에 대한 내용을 캐스팅하여 작동합니다. 따라서 문자열의 내용은 원시 숫자로 해석되며, 더 이상 문자에 대한 걱정이없고, 필요한 정밀도를 비트로 전환합니다 (이 숫자를 최고의 성능으로 조정하면 2 개의 해싱 스트링에 잘 작동했습니다. 수천 세트).

또한 정말 깔끔한 부분은 최신 하드웨어의 괜찮은 컴파일러입니다. 1 어셈블리 명령어에서 이와 같은 문자열을 해시 할 것입니다.

다른 팁

이 간단한 다항식은 놀랍게도 잘 작동합니다. Microsoft Research의 Paul Larson으로부터 다양한 해시 기능과 해시 멀티 플라이어를 연구했습니다.

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

salt 일부로 초기화해야합니다 무작위로 Hashtable이 방어하기 위해 생성되기 전에 선택한 값 해시 테이블 공격. 이것이 당신에게 문제가되지 않으면 0 만 사용하십시오.

충돌을 최소화하려면 테이블의 크기도 중요합니다. 당신의 것이 괜찮은 것 같습니다.

부스트 기능/해시 당신에게 사용될 수 있습니다. 나는 그것을 시도하지 않았으므로 그 성능을 보증 할 수 없습니다.

부스트에도 부스트에도 있습니다 CRC 라이브러리.

나는 a 부스트 첫 번째 (즉, boost :: unordered_map <>). 컨테이너 용 바이너리 트리 대신 해시 맵을 사용합니다.

일부 STL 구현에는 STDEXT 네임 스페이스에 HASH_MAP <> 컨테이너가 있다고 생각합니다.

테이블의 크기는 어떤 크기의 해시를 사용해야하는지 지시합니다. 물론 충돌을 최소화하고 싶습니다. 나는 당신이 최대 항목과 용량으로 무엇을 지정하고 있는지 잘 모르겠습니다 (나에게 같은 것 같다) 어떤 경우에도 그 숫자 중 어느 쪽이든 32 비트 해시가 충분하다는 것을 암시합니다. CRC16 (~ 65,000 가능성)으로 도망 칠 수도 있지만 아마도 많은 충돌이있을 것입니다. 반면에, 충돌은 CRC32 해시보다 더 빨리 다룰 수 있습니다.

CRC32와 함께 가고 싶습니다. 문서와 샘플 코드가 부족하지 않습니다. 최대 값을 파악하고 속도가 우선 순위가 높기 때문에 많은 포인터를 가지고 가십시오. 해시를 사용하여 색인을 생성하십시오. 충돌시 빈 버킷에 부딪 칠 때까지 인덱스를 증가시킵니다. 빠르고 간단합니다.

영어 단어를 저장하기 때문에 대부분의 캐릭터는 문자가 될 것이며 가장 중요한 두 비트의 데이터에는 큰 차이가 없습니다. 그 외에 나는 xor를 사용하여 매우 간단하게 유지할 것입니다. 결국 당신은 암호화 강도를 찾고있는 것이 아니라 합리적으로 배포하는 것입니다. 이 라인을 따라 무언가 :

size_t hash(const std::string &data) {
  size_t h(0);
  for (int i=0; i<data.length(); i++)
    h = (h << 6) ^ (h >> 26) ^ data[i];
  }
  return h;
}

그 외에도 std :: tr1 :: Hash를 해시 함수 및/또는 std :: tr1 :: unordered_map으로 해시 테이블의 구현으로 보셨습니까? 이것을 사용하면 아마도 자신의 클래스를 구현하는 데 반대하는 많은 작업이 저장 될 것입니다.

해시 테이블의 최우선 과제는 빠른 검색 (검색)입니다.

해시 테이블에서 검색하는 것이 O (1)이므로 올바른 데이터 구조를 사용하고 있습니다! :)

CRC32는 잘해야합니다. 구현은 그렇게 복잡하지 않으며 주로 XORS를 기반으로합니다. 좋은 다항식을 사용하는지 확인하십시오.

간단한 것은 어떻습니까 :

// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];

// Hash function for six character strings.
int hash(const char *str)
{
    int ret = 0, mult = 1;
    for (const char *p = str; *p; *p++, mult *= 32) {
        assert(*p >= 0 && *p < 256);
        ret += mult * hashLookup[*p];
    }

    return ret;
}

이것은 32 비트 int를 가정합니다. 문자 당 5 비트를 사용하므로 해시 값은 30 비트 만 있습니다. 아마도 첫 번째 또는 두 문자에 대해 6 비트를 생성하여 이것을 고칠 수 있습니다. 캐릭터 세트가 충분히 작 으면 30 비트 이상이 필요하지 않을 수 있습니다.

짧은 문자열을 검색해야하고 삽입이 문제가되지 않으면 B- 트리 또는 2-3 트리를 사용할 수 있습니다. 해싱으로 인해 많은 것을 얻지 못합니다.

이 작업을 수행하는 방법은 각 노드에 문자를 놓는 것입니다. 먼저 노드 "A"를 확인한 다음 "A"의 어린이 "P"를 확인하고 "P"의 어린이를 확인한 다음 "P"에 대한 어린이입니다. L "및"e ". "Apple"및 "Apply"가있는 상황에서 마지막 노드를 찾아야합니다 (유일한 차이점은 마지막 "e"및 "y"에 있으므로)

그러나 대부분의 경우 몇 단계 만 몇 단계 ( "xylophone"=> "x"-> "ylophone") 후에 단어를 얻을 수 있으므로 이와 같이 최적화 할 수 있습니다. 이것은 해싱보다 빠를 수 있습니다

C ++ 11 이후 C ++는 std::hash< string >( string ). 그것은 효율적인 해싱 함수 일 가능성이 높습니다. 해시 코드의 양호한 분포 대부분의 문자열.

또한 해시 테이블을 구현할 생각이라면 이제 C ++ 사용을 고려해야합니다. std::unordered_map 대신에.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top