Chức năng băm 32 bit tốt nhất cho các chuỗi ngắn (tên thẻ) là gì?

Question

Chức năng băm 32 bit tốt nhất cho các chuỗi tương đối ngắn là gì?

Chuỗi là tên thẻ bao gồm chữ cái tiếng Anh, số, dấu cách và một số ký tự bổ sung (#, $, ., ...). Ví dụ: Unit testing, C# 2.0.

Tôi đang tìm 'tốt nhất' như trong 'va chạm tối thiểu', hiệu suất không quan trọng cho mục tiêu của tôi.

Answer 1

Nếu hiệu suất không quan trọng, chỉ cần lấy một băm an toàn như MD5 hoặc SHA1 và cắt bớt đầu ra của nó thành 32 bit. Điều này sẽ cung cấp cho bạn phân phối mã băm không thể phân biệt được từ ngẫu nhiên.

Answer 2

Tôi không chắc chắn nếu đó là lựa chọn tốt nhất, nhưng đây là một hàm băm cho chuỗi: (. BẢNG HASH, pg 57)

The Practice of Programming

/* hash: compute hash value of string */ 
unsigned int hash(char *str) 
{ 
    unsigned int h; 
    unsigned char *p; 

    h = 0; 
    for (p = (unsigned char*)str; *p != '\0'; p++) 
     h = MULTIPLIER * h + *p; 
    return h; // or, h % ARRAY_SIZE; 
} 

Theo kinh nghiệm, các giá trị 31 và 37 có được chứng minh là lựa chọn tốt cho hệ số
trong hàm băm cho chuỗi ASCII.

Answer 3

Bạn có thể xem murmurhash2. Nó là nhanh, cũng cho dây nhỏ, và có một bước cuối cùng pha trộn tốt vì vậy nó thậm chí còn trộn lẫn tốt cho các chuỗi rất nhỏ.

Answer 4

Nếu hiếm khi người dùng thêm thẻ mới, thì bạn có thể sử dụng hàm băm hoàn hảo (http://en.wikipedia.org/wiki/Perfect_hash_function) được tính toán lại mỗi lần thêm thẻ mới. Tất nhiên, mà không biết vấn đề bạn đang thực sự cố gắng giải quyết, đó là phỏng đoán để tìm ra những gì bạn có thể làm.

Answer 5

Sử dụng MaPrime2c hàm băm:

 

    static const unsigned char sTable[256] = 
    { 
     0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9, 
     0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28, 
     0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53, 
     0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2, 
     0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8, 
     0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90, 
     0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76, 
     0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d, 
     0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18, 
     0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4, 
     0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40, 
     0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5, 
     0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2, 
     0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8, 
     0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac, 
     0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46 
    }; 


    #define PRIME_MULT 1717 


    unsigned int 
    maPrime2cHash (unsigned char *str, unsigned int len) 
    { 
     unsigned int hash = len, i; 


     for (i = 0; i != len; i++, str++) 
     { 

      hash ^= sTable[(*str + i) & 255]; 
      hash = hash * PRIME_MULT; 
     } 

     return hash; 
    } 

và nhìn vào www.amsoftware.narod.ru/algo2.html cho MaFastPrime, MaRushPrime, vv kiểm tra.

Answer 6

Nếu chương trình của bạn cần giao tiếp với hệ thống khác, tốt hơn nên sử dụng thuật toán nổi tiếng. Cách nhanh chóng & dơ bẩn là sử dụng đầu tiên Một số ký tự của md5 băm. Bạn không cần phải mất hàng giờ hoặc ngày để phát minh ra bánh xe trong dự án của bạn.

Bất lợi là nhận được nhiều cơ hội cao để va chạm. Tuy nhiên, nếu băm của bạn là cho một phiên đóng dấu thời gian, hoặc nhiệm vụ vòng đời ngắn. Không có vấn đề gì khi sử dụng nó.

Answer 7

Điều đó tùy thuộc vào phần cứng của bạn. Trên phần cứng hiện đại, tức là Intel/AMD với SSE4.2 hoặc arm7, bạn nên sử dụng nội tại _mm_crc32_uxx nội tại vì chúng tối ưu cho các chuỗi ngắn. (Đối với các phím dài cũng vậy, nhưng tốt hơn nên sử dụng phiên bản ren của Adler, như trong zlib)

Trên phần cứng cũ hoặc chưa biết, hoặc thăm dò thời gian chạy cho tính năng SSE4.2 hoặc CRC32 hoặc chỉ sử dụng một hàm băm đơn giản chức năng. Ví dụ.Murmur2 hoặc thành phố

Tổng quan về chất lượng và hiệu suất là ở đây: https://github.com/rurban/smhasher#smhasher

Ngoài ra còn có tất cả các hiện thực. Được yêu thích là https://github.com/rurban/smhasher/blob/master/crc32_hw.c và https://github.com/rurban/smhasher/blob/master/MurmurHash2.cpp

Nếu bạn biết trước các phím, hãy sử dụng hàm băm hoàn hảo, không phải hàm băm. Ví dụ. gperf hoặc tôi phash: https://github.com/rurban/Perfect-Hash#name

Ngày nay hoàn hảo thế hệ băm qua một trình biên dịch c là quá nhanh, bạn thậm chí có thể tạo ra chúng một cách nhanh chóng, và dynaload nó.

Answer 8

Tôi rất tiếc vì đã trả lời rất muộn về vấn đề này. Đầu năm nay, tôi đã soạn một trang có tiêu đề Hashing Short Strings có thể hữu ích trong cuộc thảo luận này. Tóm lại, tôi thấy rằng CRC-32 và FNV-1a vượt trội hơn cho các chuỗi ngắn băm. Chúng hiệu quả và sản xuất phân phối rộng rãi và va chạm miễn phí trong các thử nghiệm của tôi. Tôi đã rất ngạc nhiên khi thấy rằng MD5, SHA-1 và SHA-3 đã tạo ra một số lượng va chạm nhỏ khi đầu ra là gập xuống còn 32 bit.