Một hàm băm nhanh cho chuỗi trong C#

Question

Tôi muốn băm một chuỗi có độ dài lên đến 30. Điều gì sẽ là ý tưởng tốt nhất để làm điều đó nếu thời gian là mối quan tâm của tôi. Chức năng này sẽ được gọi hơn 100 triệu lần. Hiện tại tôi đang sử dụng đoạn mã sau,

static UInt64 CalculateHash(string read, bool lowTolerance) 
{ 
    UInt64 hashedValue = 0; 
    int i = 0; 
    while (i < read.Length) 
    { 
     hashedValue += read.ElementAt(i) * (UInt64)Math.Pow(31, i); 
     if (lowTolerance) i += 2; 
     else i++; 
    } 
    return hashedValue; 
} 

Answer 1

static UInt64 CalculateHash(string read) 
{ 
    UInt64 hashedValue = 3074457345618258791ul; 
    for(int i=0; i<read.Length; i++) 
    { 
     hashedValue += read[i]; 
     hashedValue *= 3074457345618258799ul; 
    } 
    return hashedValue; 
} 

Đây là một hash Knuth. Bạn cũng có thể sử dụng Jenkins.

Answer 2

Tôi đã chơi với triển khai Paul Hsieh, và dường như được nhanh chóng với sự va chạm nhỏ (cho các kịch bản của tôi anyway)

• http://www.azillionmonkeys.com/qed/hash.html

Answer 3

Để tăng tốc độ triển khai của bạn, cuộc gọi (UInt64)Math.Pow(31, i) sẽ được thay thế bằng tra cứu: tính toán trước bảng 30 quyền hạn đầu tiên của 31 và sử dụng nó khi chạy. Kể từ khi giới hạn về chiều dài là 30, bạn chỉ cần 31 yếu tố:

private static unsigned long[] Pow31 = new unsigned long[31]; 

static HashCalc() { 
    Pow31[0] = 1; 
    for (int i = 1 ; i != Pow31.Length ; i++) { 
     Pow31[i] = 31*Pow31[i-1]; 
    } 
} 

// In your hash function... 
hashedValue += read.ElementAt(i) * Pow31[i]; 

Answer 4

Trước hết, hãy cân nhắc sử dụng GetHashCode().

Một cải tiến đơn giản về việc thực hiện hiện tại của bạn:

static UInt64 CalculateHash(string read, bool lowTolerance) 
{ 
    UInt64 hashedValue = 0; 
    int i = 0; 
    ulong multiplier = 1; 
    while (i < read.Length) 
    { 
     hashedValue += read[i] * multiplier; 
     multiplier *= 37; 
     if (lowTolerance) i += 2; 
     else i++; 
    } 
    return hashedValue; 
} 

Nó tránh được việc tính toán dấu chấm động đắt tiền, và các chi phí của ElementAt.

Btw (UInt64)Math.Pow(31, i) không hoạt động tốt đối với các chuỗi dài hơn. Làm tròn điểm nổi sẽ dẫn đến một hệ số 0 cho các ký tự vượt quá 15 hoặc hơn.