32 비트 정수를 사용하여 충돌 률이 낮은 고속 문자열 해싱 알고리즘

32 비트 정수를 사용하여 충돌 률이 낮은 고속 문자열 해싱 알고리즘

---

빠른 검색을하고 싶은 관련없는 이름이 많이 있습니다. "aardvark"는 항상 모든 곳에서 "aardvark"이므로 문자열을 해시하고 정수를 재사용하면 비교 속도를 높일 수 있습니다. 전체 이름 집합은 알 수 없으며 시간이 지남에 따라 변경됩니다. 작은 (32 또는 16) 비트 값을 생성하고 충돌 률이 낮은 빠른 문자열 해싱 알고리즘이란 무엇입니까?

C / C ++에 특화된 최적화 된 구현을보고 싶습니다.

---

FNV 변형 중 하나가 요구 사항을 충족해야합니다. 빠르고 균등하게 분산 된 출력을 생성합니다.

---

Murmur Hash 는 꽤 좋습니다.

---

고정 문자열 세트의 경우 gperf를 사용하십시오.

문자열 세트가 변경되면 하나의 해시 함수를 선택해야합니다. 이 주제는 이전에 논의되었습니다.

hash_map을 사용할 때 stl 문자열에 사용하는 가장 좋은 해싱 알고리즘은 무엇입니까?

---

eternallyconfuzzled.com 에도 멋진 기사 가 있습니다.

문자열에 대한 Jenkins의 One-at-a-Time 해시는 다음과 같아야합니다.

#include <stdint.h>

uint32_t hash_string(const char * s)
{
    uint32_t hash = 0;

    for(; *s; ++s)
    {
        hash += *s;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }

    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}

---

사용 사례에 따라 더 나을 수있는 또 다른 솔루션은 인턴 문자열 입니다. 예를 들어 Lisp에서 기호가 작동하는 방식입니다.

인턴 된 문자열은 값이 실제 문자열 바이트의 주소 인 문자열 개체입니다. 따라서 전역 테이블을 체크인하여 인턴 된 문자열 객체를 만듭니다. 문자열이 거기에 있으면 인턴 된 문자열을 해당 문자열의 주소로 초기화합니다. 그렇지 않은 경우 삽입 한 다음 인턴 된 문자열을 초기화합니다.

즉, 동일한 문자열에서 빌드 된 두 개의 인턴 된 문자열은 주소 인 동일한 값을 갖게됩니다. 따라서 N이 시스템의 인턴 된 문자열 수인 경우 특성은 다음과 같습니다.

• 느린 구성 (조회 및 ​​메모리 할당 필요)
• 동시 스레드의 경우 글로벌 데이터 및 동기화 필요
• Compare는 O (1)입니다. 실제 문자열 바이트가 아닌 주소를 비교하기 때문입니다 (이는 정렬이 잘 작동하지만 알파벳 정렬이 아님을 의미합니다).

건배,

칼

---

Boost 라이브러리를 사용하지 않는 이유는 무엇 입니까? 그들의 해싱 기능은 사용하기 쉽고 Boost의 대부분은 곧 C ++ 표준의 일부가 될 것입니다. 일부는 이미 있습니다.

부스트 해시는

#include <boost/functional/hash.hpp>

int main()
{
    boost::hash<std::string> string_hash;

    std::size_t h = string_hash("Hash me");
}

boost.org 에서 부스트를 찾을 수 있습니다.

---

좋은 주제에 대해서는 결코 늦지 않으며 사람들이 내 결과에 관심을 가질 것이라고 확신합니다.

해시 함수가 필요했고이 게시물을 읽고 여기에 제공된 링크에 대해 약간의 연구를 수행 한 후 Daniel J Bernstein 알고리즘의 변형을 생각해 냈습니다.이 알고리즘은 흥미로운 테스트를 수행하는 데 사용되었습니다.

unsigned long djb_hashl(const char *clave)
{
    unsigned long c,i,h;

    for(i=h=0;clave[i];i++)
    {
        c = toupper(clave[i]);
        h = ((h << 5) + h) ^ c;
    }
    return h;
}

이 변형은 대소 문자를 무시하고 문자열을 해시하므로 사용자 로그인 자격 증명을 해싱해야합니다. 'clave'는 스페인어로 '열쇠'입니다. 나는 스페인어에 대해 미안하지만 그것의 모국어와 프로그램이 적혀 있습니다.

글쎄, 나는 'test_aaaa'에서 'test_zzzz'까지 사용자 이름을 생성하는 프로그램을 작성했고-문자열을 더 길게 만들기 위해-이 목록에 무작위 도메인을 추가했습니다 : 'cloud-nueve.com', 'yahoo.com ','gmail.com '및'hotmail.com '. 따라서 각각은 다음과 같습니다.

test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, 
test_aaac@gmail.com, test_aaad@hotmail.com and so on.

Here is the output of the test -'Colision entre XXX y XXX' means 'Collision of XXX and XXX'. 'palabras' means 'words' and 'Total' is the same in both languages-.

    Buscando Colisiones...
    Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
    Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
    Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
    Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
    Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
    Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
    Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
    Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
    Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
    Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
    Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108)
    Total de Colisiones: 11
    Total de Palabras  : 456976

That is not bad, 11 collisions out of 456,976 (off course using the full 32 bit as table lenght).

Running the program using 5 chars, that is from 'test_aaaaa' to 'test_zzzzz', actually runs out of memory building the table. Below is the output. 'No hay memoria para insertar XXXX (insertadas XXX)' means 'There is not memory left to insert XXX (XXX inserted)'. Basically malloc() failed at that point.

    No hay memoria para insertar 'test_epjcv' (insertadas 2097701).

    Buscando Colisiones...

    ...451 'colision' strings...

    Total de Colisiones: 451
    Total de Palabras  : 2097701

Which means just 451 collisions on 2,097,701 strings. Note that in none of the occasions, there were more than 2 collisions per code. Which I confirm it is a great hash for me, as what I need is to convert the login ID to a 40 bit unique id for indexing. So I use this to convert the login credentials to a 32 bit hash and use the extra 8 bits to handle up to 255 collisions per code, which lookign at the test results would be almost impossible to generate.

Hope this is useful to someone.

EDIT:

Like the test box is AIX, I run it using LDR_CNTRL=MAXDATA=0x20000000 to give it more memory and it run longer, the results are here:

Buscando Colisiones... Total de Colisiones: 2908 Total de Palabras : 5366384

That is 2908 after 5,366,384 tries!!

VERY IMPORTANT: Compiling the program with -maix64 (so unsigned long is 64 bits), the number of collisions is 0 for all cases!!!

---

Have a look at GNU gperf.

---

The Hsieh hash function is pretty good, and has some benchmarks/comparisons, as a general hash function in C. Depending on what you want (it's not completely obvious) you might want to consider something like cdb instead.

---

Bob Jenkins has many hash functions available, all of which are fast and have low collision rates.

---

You can see what .NET uses on the String.GetHashCode() method using Reflector.

I would hazard a guess that Microsoft spent considerable time optimising this. They have printed in all the MSDN documentation too that it is subject to change all the time. So clearly it is on their "performance tweaking radar" ;-)

Would be pretty trivial to port to C++ too I would have thought.

---

There is some good discussion in this previous question

And a nice overview of how to pick hash functions, as well as statistics about the distribution of several common ones here

---

Described here is a simple way of implementing it yourself: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

A snippet from the post:

if say we have a character set of capital English letters, then the length of the character set is 26 where A could be represented by the number 0, B by the number 1, C by the number 2 and so on till Z by the number 25. Now, whenever we want to map a string of this character set to a unique number , we perform the same conversion as we did in case of the binary format

---

CRC-32. There is about a trillion links on google for it.

참고URL : https://stackoverflow.com/questions/114085/fast-string-hashing-algorithm-with-low-collision-rates-with-32-bit-integer