thuật toán băm tốt nhất về mặt va chạm băm và hiệu suất cho các chuỗi

Question

Điều gì sẽ là các thuật toán băm tốt nhất nếu chúng ta có những ưu tiên như sau (theo thứ tự):

1. tối thiểu va chạm băm
2. Performance

Nó không phải bảo mật. Về cơ bản, tôi đang cố tạo một chỉ mục dựa trên sự kết hợp các thuộc tính của một số đối tượng. Tất cả các thuộc tính là chuỗi.

Mọi tham chiếu đến triển khai C# sẽ được đánh giá cao.

Answer 1

Quên cụm từ "tốt nhất". Bất kể thuật toán băm bất kỳ ai có thể đưa ra, trừ khi bạn có một tập hợp dữ liệu rất hạn chế cần phải băm, mọi thuật toán thực hiện rất tốt trên trung bình có thể trở nên vô dụng nếu chỉ được cấp quyền (hoặc từ góc nhìn của bạn) "dữ liệu sai. Thay vì lãng phí quá nhiều thời gian suy nghĩ về việc làm thế nào để có được băm không có va chạm mà không sử dụng quá nhiều thời gian CPU, tôi thà bắt đầu suy nghĩ về "Làm thế nào để làm cho va chạm ít vấn đề" hơn. Ví dụ. nếu mỗi nhóm băm trên thực tế là một bảng và tất cả các chuỗi trong bảng này (có xung đột) được sắp xếp theo thứ tự bảng chữ cái, bạn có thể tìm kiếm trong bảng xô bằng cách sử dụng tìm kiếm nhị phân (chỉ là O (log n)). khi mỗi thùng băm thứ hai có 4 va chạm, mã của bạn sẽ vẫn có hiệu suất khá (nó sẽ chậm hơn một chút so với một bảng va chạm miễn phí, nhưng không nhiều). Một lợi thế lớn ở đây là nếu bảng của bạn đủ lớn và băm của bạn không quá đơn giản, hai chuỗi dẫn đến giá trị băm giống nhau sẽ trông hoàn toàn khác nhau (do đó tìm kiếm nhị phân có thể ngừng so sánh chuỗi sau khi có thể một hoặc hai ký tự trung bình ; làm cho mọi so sánh rất nhanh).

Thực ra tôi đã có một tình huống trước khi tìm kiếm trực tiếp trong một bảng được sắp xếp bằng cách sử dụng tìm kiếm nhị phân hóa ra nhanh hơn băm! Mặc dù thuật toán băm của tôi là đơn giản, nó mất khá nhiều thời gian để băm các giá trị. Thử nghiệm hiệu suất cho thấy rằng chỉ khi tôi nhận được nhiều hơn khoảng 700-800 mục, băm thực sự nhanh hơn tìm kiếm nhị phân. Tuy nhiên, vì bảng không bao giờ có thể lớn hơn 256 mục và vì bảng trung bình dưới 10 mục, điểm chuẩn rõ ràng cho thấy rằng trên mọi hệ thống, mỗi CPU, tìm kiếm nhị phân nhanh hơn. Ở đây, thực tế là thường đã so sánh byte đầu tiên của dữ liệu là đủ để dẫn đến lặp đi lặp lại bsearch tiếp theo (như dữ liệu được sử dụng rất khác nhau trong một đến hai byte đầu tiên) hóa ra là một lợi thế lớn.

Vì vậy, để tóm tắt: Tôi có một thuật toán băm khá, không gây ra quá nhiều va chạm trung bình và khá nhanh (tôi thậm chí còn chấp nhận một số va chạm nữa, nếu nó chỉ rất nhanh!) chúng sẽ trừ khi không gian băm của bạn ít nhất bằng hoặc lớn hơn không gian dữ liệu của bạn và bạn có thể ánh xạ giá trị băm duy nhất cho mọi bộ dữ liệu có thể) .

Answer 2

Không có một thuật toán băm tối ưu duy nhất nào. Nếu bạn có miền đầu vào đã biết, bạn có thể sử dụng trình tạo băm hoàn hảo như gperf để tạo một thuật toán băm sẽ nhận được tỷ lệ 100% trên bộ đầu vào cụ thể đó. Nếu không, không có câu trả lời 'đúng' cho câu hỏi này.

Answer 3

Bạn có thể sử dụng cả hàm băm Knuth described here.

Rất nhanh giả sử kích thước bảng băm công suất 2 - chỉ một lần, một ca và một bit và. Quan trọng hơn (đối với bạn) nó là tuyệt vời tại giảm thiểu va chạm (xem this analysis).

Một số thuật toán tốt khác được mô tả here.

Answer 4

Mã băm đơn giản được sử dụng bởi lớp Chuỗi của Java có thể hiển thị một thuật toán phù hợp.

Dưới đây là triển khai "GNU Classpath". (Giấy phép: GPL)

/** 
    * Computes the hashcode for this String. This is done with int arithmetic, 
    * where ** represents exponentiation, by this formula:<br> 
    * <code>s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]</code>. 
    * 
    * @return hashcode value of this String 
    */ 
    public int hashCode() 
    { 
    if (cachedHashCode != 0) 
     return cachedHashCode; 

    // Compute the hash code using a local variable to be reentrant. 
    int hashCode = 0; 
    int limit = count + offset; 
    for (int i = offset; i < limit; i++) 
     hashCode = hashCode * 31 + value[i]; 
    return cachedHashCode = hashCode; 
    } 

Answer 5

Như Nigel Campbell chỉ định, không có những điều như hàm băm 'tốt nhất', vì nó phụ thuộc vào đặc điểm dữ liệu về những gì bạn đang băm cũng như hay không, bạn cần mật mã chất lượng băm.

Điều đó nói rằng, đây là một số gợi ý:

• Kể từ khi các mục mà bạn đang sử dụng làm đầu vào cho hash chỉ là một tập hợp các chuỗi, bạn chỉ có thể kết hợp các hashcodes cho mỗi người trong số những dây cá nhân . Tôi đã nhìn thấy các pseudo-code sau đây gợi ý để làm điều này, nhưng tôi không biết về bất kỳ phân tích cụ thể của nó:

  int hashCode = 0; 
  
  foreach (string s in propertiesToHash) { 
      hashCode = 31*hashCode + s.GetHashCode(); 
  } 
  

  Theo this article, System.Web có một phương pháp nội bộ kết hợp hashcodes sử dụng

  combinedHash = ((combinedHash << 5) + combinedHash)^nextObj.GetHashCode(); 
  

  Tôi cũng đã thấy mã chỉ đơn giản là xor's hashcodes với nhau, nhưng điều đó có vẻ như một ý tưởng tồi với tôi (mặc dù tôi lại không có phân tích để sao lưu điều này). Nếu không có gì khác, bạn kết thúc với một vụ va chạm nếu các chuỗi giống nhau được băm theo thứ tự khác.

• Tôi đã sử dụng FNV để hiệu quả tốt: http://www.isthe.com/chongo/tech/comp/fnv/

• Paul Hsieh có một bài viết khá: http://www.azillionmonkeys.com/qed/hash.html

• Một bài viết tốt đẹp bởi Bob Jenkins đã được xuất bản lần đầu vào năm 1997 trong Tạp chí Doctor Dobb của (bài viết được liên kết có cập nhật): http://burtleburtle.net/bob/hash/doobs.html

Answer 6

Tôi yêu Stackoverflow! Đọc câu hỏi này khiến tôi nhìn vào hàm băm nhiều hơn một chút và tôi tìm thấy số Cuckoo Hash.

Từ bài viết:

Lookup đòi hỏi kiểm tra chỉ hai Vị trí trong bảng băm, mà cần có thời gian liên tục trong trường hợp xấu nhất (xem Big O notation). Đây là độ tương phản với nhiều bảng băm khác các thuật toán, có thể không có trường hợp xấu nhất liên tục bị ràng buộc vào thời gian để thực hiện tra cứu.

Tôi nghĩ điều đó phù hợp với tiêu chí va chạm và hiệu suất của bạn. Dường như sự cân bằng là loại bảng băm này chỉ có thể nhận được đầy đủ 49%.

Answer 7

Tôi sẽ trở nên què quặt ở đây và đưa ra một câu trả lời lý thuyết hơn là câu trả lời chỉ bằng pin nhưng hãy lấy giá trị trong đó.

Đầu tiên có hai vấn đề riêng biệt:

a. Khả năng va chạm b. Hiệu suất của băm (ví dụ: thời gian, chu kỳ cpu, v.v.)

Hai vấn đề được san hô nhẹ. Chúng không hoàn toàn tương quan.

Sự cố xảy ra với sự khác biệt giữa hashee và không gian băm kết quả. Khi bạn băm một file 1KB (1024 bytes) tập tin và băm có 32 byte sẽ có:

1,0907481356194159294629842447338e + 2466 (tức là một số với 2466 số không) kết hợp khả dĩ của đầu vào tập tin

và băm không gian sẽ có

1,1579208923731619542357098500869e + 77 (tức là một số với 77 số không)

Sự khác biệt là rất lớn. có 2389 khác biệt giữa chúng. CÓ S COL ĐƯỢC THU THẬP (một va chạm là một trường hợp đặc biệt khi hai tập tin đầu vào KHÁC sẽ có cùng một băm chính xác) vì chúng tôi đang giảm 10^2466 trường hợp xuống còn 10^77 trường hợp.

Cách duy nhất để giảm thiểu rủi ro collison là để phóng to không gian băm và do đó để làm cho hahs dài hơn. Lý tưởng nhất là băm sẽ có chiều dài tập tin nhưng điều này là bằng cách nào đó đạo đức.

---

Vấn đề thứ hai là hiệu suất. Điều này chỉ đề cập đến thuật toán của hàm băm. Ofcourse rằng một băm dài hơn sẽ hầu hết có thể yêu cầu nhiều chu kỳ CPU nhưng một thuật toán thông minh hơn có thể không.Tôi không có câu trả lời rõ ràng cho câu hỏi này. Nó quá khó khăn.

Tuy nhiên, bạn có thể đo điểm chuẩn/đo lường các triển khai băm khác nhau và rút ra kết luận trước từ điều này.

Chúc may mắn;)

Answer 8

Đây là một cách đơn giản thực hiện nó cho mình: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

Dưới đây là một đoạn trích từ bài:

nếu nói rằng chúng ta có một bộ ký tự của chữ cái tiếng Anh cơ bản, sau đó chiều dài của bộ ký tự là 26 trong đó A có thể được biểu diễn bằng số 0, B theo số 1, C theo số 2 và cứ tiếp tục cho đến Z theo số 25. Bây giờ, bất cứ khi nào chúng ta muốn ánh xạ một chuỗi ký tự này được đặt thành một số duy nhất , chúng tôi thực hiện cùng một chuyển đổi như chúng tôi đã làm trong trường hợp định dạng nhị phân

Answer 9

"Murmurhash" là khá tốt trên cả hiệu suất và va chạm.

Chủ đề được đề cập tại "softwareengineering.stackexchange" có một số kiểm tra và Murmur thắng.

Tôi đã tự viết C# port của MurmurHash 2 thành .NET và kiểm tra nó trên danh sách các từ tiếng Anh 466k, có 22 va chạm.

Các kết quả và thực hiện đang ở đây: https://github.com/jitbit/MurmurHash.net (từ chối trách nhiệm, tôi tham gia vào dự án mã nguồn mở này!)