Hàm băm cho một chuỗi

Question

Hiện tại chúng tôi đang xử lý hàm băm trong lớp của mình. Người hướng dẫn của chúng tôi đã yêu cầu chúng tôi sử dụng hàm băm trên internet để so sánh với hai hàm chúng tôi đã sử dụng trong mã của chúng tôi.

Thứ nhất:

int HashTable::hash (string word) 
// POST: the index of entry is returned 
{  int sum = 0; 
     for (int k = 0; k < word.length(); k++) 
      sum = sum + int(word[k]); 
     return sum % SIZE; 
} 

Thứ hai:

int HashTable::hash (string word) 
{ 
    int seed = 131; 
    unsigned long hash = 0; 
    for(int i = 0; i < word.length(); i++) 
    { 
     hash = (hash * seed) + word[i]; 
    } 
    return hash % SIZE; 
} 

đâu SIZE là 501 (Kích thước của bảng băm) và đầu vào đến từ một tập tin văn bản với hơn 20.000 từ.

Tôi đã thấy this câu hỏi với một vài ví dụ về mã nhưng không chắc chắn chính xác những gì cần tìm kiếm trong hàm băm. Nếu tôi hiểu chính xác, trong trường hợp của tôi, một băm có một đầu vào (chuỗi) và thực hiện phép tính toán để chỉ định chuỗi một số và chèn nó vào một bảng. Quá trình này được thực hiện để tăng tốc độ tìm kiếm danh sách?

Nếu logic của tôi là âm thanh, có ai có ví dụ hay tài nguyên hiển thị hàm băm khác có liên quan đến chuỗi không? Hoặc thậm chí là quá trình viết hàm băm hiệu quả của riêng tôi.

Answer 1

Thứ nhất, nó thường không quan trọng mà nhiều trong thực tế. Hầu hết các hàm băm đều "đủ tốt".

Nhưng nếu bạn thực sự quan tâm, bạn nên biết rằng đó là một chủ đề nghiên cứu của chính nó. Có hàng nghìn bài báo về điều đó. Bạn vẫn có thể lấy bằng tiến sĩ ngay hôm nay bằng cách nghiên cứu & thuật toán băm thiết kế.

Hàm băm thứ hai của bạn có thể tốt hơn một chút, vì có lẽ nên tách chuỗi "ab" khỏi chuỗi "ba". Mặt khác, nó có lẽ ít nhanh hơn hàm băm đầu tiên. Nó có thể, hoặc có thể không, có liên quan cho ứng dụng của bạn.

Tôi đoán rằng các hàm băm được sử dụng cho các chuỗi bộ gen hoàn toàn khác với các hàm băm được sử dụng để băm tên họ trong cơ sở dữ liệu điện thoại. Có lẽ ngay cả một số hàm băm chuỗi cũng phù hợp hơn với tiếng Đức, hơn là từ tiếng Anh hoặc tiếng Pháp.

Nhiều thư viện phần mềm cung cấp cho bạn hàm băm đủ tốt, ví dụ: Qt có qhash và C++ 11 có std::hash trong <functional>, Glib có một số hash functions trong C và POCO có một số chức năng hash.

Tôi thường có các hàm băm liên quan đến số nguyên tố (xem Bézout's identity) và xor, như ví dụ:

#define A 54059 /* a prime */ 
#define B 76963 /* another prime */ 
#define C 86969 /* yet another prime */ 
#define FIRSTH 37 /* also prime */ 
unsigned hash_str(const char* s) 
{ 
    unsigned h = FIRSTH; 
    while (*s) { 
    h = (h * A)^(s[0] * B); 
    s++; 
    } 
    return h; // or return h % C; 
} 

Nhưng tôi không tự xưng là chuyên gia băm. Tất nhiên, các giá trị của A, B, C, FIRSTH tốt nhất nên là số nguyên tố, nhưng bạn có thể đã chọn các số nguyên tố khác.

Nhìn vào một số hoạt động MD5 để có được cảm giác về hàm băm nào có thể.

Hầu hết sách hay về thuật toán đều có ít nhất một chương dành riêng cho băm. Bắt đầu bằng wikipages trên hash function & hash table.

Answer 2

Java String implements hashCode like this:

public int hashCode() 

Returns a hash code for this string. The hash code for a String object is computed as 

    s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and^indicates exponentiation. (The hash value of the empty string is zero.) 

Vì vậy, một cái gì đó như thế này:

int HashTable::hash (string word) { 
    int result = 0; 
    for(size_t i = 0; i < word.length(); ++i) { 
     result += word[i] * pow(31, i); 
    } 
    return result; 
} 

Answer 3

- Cách đi những ngày này -

Sử dụng SipHash. Để bảo vệ bạn.

- Old and Dangerous -

unsigned int RSHash(const std::string& str) 
{ 
    unsigned int b = 378551; 
    unsigned int a = 63689; 
    unsigned int hash = 0; 

    for(std::size_t i = 0; i < str.length(); i++) 
    { 
     hash = hash * a + str[i]; 
     a = a * b; 
    } 

    return (hash & 0x7FFFFFFF); 
} 

unsigned int JSHash(const std::string& str) 
{ 
     unsigned int hash = 1315423911; 

     for(std::size_t i = 0; i < str.length(); i++) 
     { 
      hash ^= ((hash << 5) + str[i] + (hash >> 2)); 
     } 

     return (hash & 0x7FFFFFFF); 
} 

Hỏi google cho "hàm băm mục đích chung"

Answer 4

chức năng Hash để sử dụng thuật toán có thường 2 bàn thắng, đầu tiên họ cần phải nhanh nhẹn, thứ hai họ phải phân biệt đồng đều các giá trị trên các số có thể. Hàm băm cũng được yêu cầu cung cấp cho cùng một số cho cùng một giá trị đầu vào.

nếu giá trị của bạn là chuỗi, sau đây là một số ví dụ cho hàm băm xấu:

1. string[0] - các ký tự ASCII az là cách thường xuyên hơn sau đó những người khác
2. string.lengh() - giá trị có thể xảy ra nhất là 1

Hàm băm tốt cố gắng sử dụng mọi bit của đầu vào trong khi vẫn giữ thời gian tính toán tối thiểu. Nếu bạn chỉ cần một số mã băm, hãy thử nhân các byte với số nguyên tố, và tổng hợp chúng.

Answer 5

Sử dụng boost::hash

#include <boost\functional\hash.hpp> 

...

std::string a = "ABCDE"; 
size_t b = boost::hash_value(a);