Làm cách nào để tôi tối ưu hóa bảng băm cho một tập hợp nhất định?

Question

Giả sử tôi có một tập hợp các cặp khóa-giá trị mà tôi định lưu trữ trong bảng băm. Dân số cố định và sẽ không bao giờ thay đổi. Những gì tối ưu hóa có sẵn cho tôi để làm cho bảng băm càng nhanh càng tốt? Tôi nên tập trung vào tối ưu hóa nào? Đây là giả định tôi có rất nhiều không gian. Sẽ có một số lượng hợp lý của các cặp (nói không quá 100.000).

EDIT: Tôi muốn tối ưu hóa tìm kiếm. Tôi không quan tâm phải mất bao lâu để xây dựng.

Answer 1

Tôi sẽ đảm bảo rằng băm của khóa của bạn thành giá trị duy nhất. Điều này sẽ đảm bảo rằng mọi tra cứu sẽ là thời gian cố định và do đó, càng nhanh càng tốt.

Vì bạn không bao giờ có thể có hơn 100.000 khóa, hoàn toàn có thể có 100.000 giá trị băm.

Ngoài ra, hãy đảm bảo rằng bạn sử dụng hàm tạo cần int để chỉ định dung lượng ban đầu (Đặt nó thành 100.000) và một phao để đặt hệ số tải. (Sử dụng 1) Ngoài ra, thực hiện việc này yêu cầu bạn có chức năng băm hoàn hảo cho khóa của mình. Tuy nhiên, điều này sẽ dẫn đến tra cứu nhanh nhất có thể, trong số lượng ít nhất bộ nhớ.

Answer 2

Đảm bảo không có xung đột. Nếu không có va chạm, bạn được đảm bảo O (1) thời gian tra cứu liên tục. Tối ưu hóa tiếp theo sau đó sẽ là tra cứu.

Sử dụng profiler để tối ưu hóa từng mảnh. Thật khó mà không có điều đó.

Answer 3

Việc tối ưu hóa phải được thực hiện theo phương pháp hashCode của khóa class. Điều cần lưu ý là thực hiện phương pháp này để tránh va chạm.

Answer 4

Nói chung, để tối ưu hóa bảng băm, bạn muốn giảm thiểu va chạm trong việc xác định hàm băm của bạn, vì vậy các nhóm của bạn sẽ không chứa nhiều mục và tìm kiếm băm sẽ trả về ngay lập tức.

Hầu hết thời gian, điều đó có nghĩa là bạn nên đo đầu ra của hàm băm trên không gian sự cố. Vì vậy, tôi đoán tôi muốn khuyên bạn nên nhìn vào đó

Answer 5

Nếu có thể tạo một bảng băm lớn sao cho không có va chạm gì cả, nó sẽ là lý tưởng. Kể từ khi chèn và tra cứu của bạn sẽ được thực hiện trong thời gian không đổi.

Nhưng nếu không thể, hãy thử chọn hàm băm sao cho các khóa của bạn được phân phối đồng đều trên bảng băm.

Answer 6

Perfect hashing algorithms giải quyết vấn đề, nhưng không được chia tỷ lệ thành 100 nghìn đối tượng. Tôi đã tìm thấy một số Java MPH package nhưng chưa thử.

Answer 7

Nếu dân số được biết tại thời gian biên dịch, thì giải pháp tối ưu là sử dụng hàm băm hoàn hảo tối thiểu (MPH). Các Wikipedia page về chủ đề này liên kết đến một số công cụ Java có thể tạo ra các.

Answer 8

Nhận thuật toán băm hoàn hảo để cung cấp các giá trị hoàn toàn duy nhất cho các đối tượng 100K có khả năng gần như không thể. Hãy xem xét nghịch lý sinh nhật. Ngày mà mọi người được sinh ra có thể được coi là một thuật toán băm hoàn hảo nếu bạn có nhiều hơn 23 người bạn có nhiều khả năng có xung đột, và đó là trong bảng 365 ngày.

Vậy bạn cần một bảng lớn đến mức nào trong 100K?

Nếu chìa khóa của bạn là dây, chiến lược tối ưu của bạn là một cây, không phải là nhị phân mà là n-branch tại mỗi ký tự. Nếu các phím chỉ có chữ thường thì nó vẫn dễ dàng hơn khi bạn chỉ cần 26 khi bạn tạo một nhánh.

Chúng tôi bắt đầu với 26 khóa. Theo ký tự đầu tiên, giả sử f f có thể có giá trị được liên kết với nó. Và nó có thể có cây con. Tra cứu một cây con của o. Điều này dẫn đến nhiều subtrees sau đó tìm kiếm o tiếp theo. (Bạn biết nơi mà đã được dẫn đầu!). Nếu điều này không có giá trị liên kết với nó, hoặc chúng ta nhấn một cây con rỗng trên đường, chúng ta biết giá trị không được tìm thấy.

Bạn có thể tối ưu hóa không gian trên cây nơi bạn nhấn một điểm độc đáo. Giả sử bạn có một cửa sổ chính và nó trở thành duy nhất ở ký tự thứ 4. Tại thời điểm này, nơi bạn gán giá trị, bạn cũng lưu trữ chuỗi thực tế được liên kết với nó. Trong ví dụ của chúng tôi có thể có một giá trị được liên kết với foo nhưng khóa liên quan đến nó có thể là thực phẩm chứ không phải foo.

Tôi nghĩ công cụ tìm kiếm của Google sử dụng kỹ thuật tương tự như vậy.

Answer 9

Câu hỏi quan trọng là chìa khóa của bạn là gì. (Không có ý định chơi chữ.) Như những người khác đã chỉ ra, mục đích là để giảm thiểu số lượng va chạm băm. Nếu bạn có thể nhận được số lần va chạm băm bằng không, tức là hàm băm của bạn tạo ra một giá trị duy nhất cho mỗi khóa thực sự được truyền cho nó, bạn sẽ có một băm hoàn hảo.

Lưu ý rằng trong Java, hàm băm thực sự có hai bước: Đầu tiên, khóa được chạy thông qua hàm hashCode cho lớp của nó. Sau đó, chúng tôi tính giá trị chỉ mục vào bảng băm bằng cách lấy giá trị này modulo kích thước của bảng băm.

Tôi nghĩ rằng mọi người thảo luận về hàm băm hoàn hảo có xu hướng quên bước thứ hai đó. Ngay cả khi bạn đã viết hàm hashCode tạo ra một giá trị duy nhất cho mỗi khóa được chuyển đến nó, bạn vẫn có thể nhận được một băm hoàn toàn khủng khiếp nếu giá trị này modulo kích thước bảng băm không phải là duy nhất. Ví dụ, giả sử bạn có 100 khóa và hàm hashCode của bạn trả về các giá trị 1, 1001, 2001, 3001, 4001, 5001, ... 99001. Nếu bảng băm của bạn có 100.000 vị trí, đây sẽ là băm hoàn hảo. Mỗi phím đều có khe riêng. Nhưng nếu nó có 1000 slot, tất cả chúng đều băm vào cùng một slot. Nó sẽ là băm tồi tệ nhất có thể.

Vì vậy, hãy xem xét việc xây dựng hàm băm tốt. Lấy những trường hợp cực đoan. Giả sử rằng chìa khóa của bạn là một ngày. Bạn biết rằng tất cả các ngày sẽ là vào tháng Giêng cùng năm. Sau đó, sử dụng ngày trong tháng vì giá trị băm sẽ tốt như nó sẽ nhận được: mọi thứ sẽ băm thành một số nguyên duy nhất trong một phạm vi nhỏ. Mặt khác, nếu ngày của bạn là ngày đầu tiên của tháng trong nhiều năm và nhiều tháng, lấy ngày của tháng sẽ là một băm khủng khiếp, vì mọi khóa thực tế sẽ ánh xạ tới "1".

Điểm của tôi là nếu bạn thực sự muốn tối ưu hóa băm của mình, bạn cần biết bản chất của dữ liệu. Phạm vi giá trị thực tế mà bạn sẽ nhận được là bao nhiêu?