Mảng chuỗi là khóa hàm băm?

Question

Có thể, bằng bất kỳ ngôn ngữ nào (không quan trọng), để có hàm băm sử dụng một chuỗi các chuỗi làm khóa?

Ý tôi là một cái gì đó như thế này:

hash(["word1", "word2", ...]) = "element" 

thay vì cổ điển:

hash("word") = "element" 

tôi cần một cái gì đó như thế vì mỗi từ tôi muốn sử dụng như chìa khóa có thể thay đổi sản lượng phần tử của hàm. Tôi đã có một chuỗi các từ và tôi muốn một đầu ra cụ thể cho chuỗi đó (cũng là thứ tự có thể thay đổi kết quả).

Answer 1

Chắc chắn. Bất kỳ cấu trúc dữ liệu nào cũng có thể được băm. Bạn chỉ cần đưa ra một định nghĩa nghiêm ngặt về bình đẳng và sau đó đảm bảo rằng băm (A) == băm (B) nếu A == B. Giả sử định nghĩa của bạn là [s1, s2, ..., sm] == [t1, t2, ..., tn] nếu và chỉ nếu m == n và si == ti cho i = 1..m và chuỗi tiếp theo s == t nếu và chỉ khi | s | == | t | và s [i] == t [i] cho 0 < = i < | s |. Bạn có thể tạo một băm theo nhiều cách:

• Ghép tất cả các chuỗi trong danh sách và băm kết quả bằng bất kỳ hàm băm chuỗi nào.
• Làm tương tự, thêm dấu tách như dấu phẩy (,)
• băm từng chuỗi riêng lẻ và xor kết quả.
• Chuỗi chữ thập eash riêng lẻ, thay đổi giá trị băm trước đó và xor giá trị mới vào băm.
• Nhiều khả năng hơn nữa ...

Định nghĩa về sự bình đẳng là quan trọng. Nếu ví dụ thứ tự không quan trọng trong danh sách hoặc so sánh chuỗi không phân biệt dạng chữ, thì hàm băm phải được thiết kế để đảm bảo hàm băm (A) == băm (B) nếu A == B. Bắt sai này sẽ khiến tra cứu thất bại.

Java là một ngôn ngữ cho phép bạn xác định hàm băm cho bất kỳ loại dữ liệu nào. Và trên thực tế, một danh sách thư viện các chuỗi sẽ hoạt động tốt như một khóa sử dụng hàm băm mặc định.

HashMap<ArrayList<String>, String> map = new HashMap<ArrayList<String>, String>(); 

ArrayList<String> key = new ArrayList<String>(); 
key.add("Hello"); 
key.add("World"); 

map.put(key, "It's me."); 
// map now contains mapping ["Hello", "World"] -> "It's me." 

Answer 2

Có thể, nhưng trong hầu hết các trường hợp, bạn sẽ phải xác định hàm băm của riêng bạn để dịch một mảng thành một khóa băm. Ví dụ, trong java, array.hashCode() dựa trên hàm Object.hashCode() dựa trên tham chiếu chính nó chứ không phải nội dung của Object.

Bạn cũng có thể xem Arrays.deepHashCode() function in java nếu bạn quan tâm đến việc triển khai chức năng băm được xây dựng trên một mảng.