Hàm băm hoàn hảo tối thiểu

Question

Tôi có nhiều số nguyên trong phạm vi [0; 2^63-1]. Tuy nhiên, chỉ có 10^8 số nguyên. Có không có bản sao. Danh sách đầy đủ được biết ở thời gian biên dịch nhưng chỉ có một số ngẫu nhiên là . Những số này không bao giờ thay đổi.
Để lưu trữ một số nguyên rõ ràng, 8 byte bắt buộc và có giá trị 1 byte được liên kết, do đó lưu trữ rõ ràng yêu cầu khoảng 860 MB.
Vì vậy, tôi muốn tìm hàm băm hoàn hảo tối thiểu để ánh xạ mỗi 10^8 số nguyên từ [0; 2^63-1] đến [0; 10^8-1]. Tôi chỉ nên tìm hàm này một lần, dữ liệu không bao giờ thay đổi và chức năng có thể phức tạp. Nhưng nó phải là tối thiểu, hoàn hảo, và tính toán nên được nhanh chóng. Làm thế nào tôi có thể làm điều này tốt hơn? Có lẽ nó có thể tìm và sử dụng một số subsequences nếu chúng xảy ra?
Cảm ơn.

Answer 1

Hãy để máy tính của bạn làm việc cho bạn:

http://www.gnu.org/software/gperf/

Trích:. "GNU gperf là ​​một hoàn hảo tạo hàm băm Đối với một danh sách nhất định của chuỗi, nó tạo ra một hàm băm và bảng băm, dưới dạng mã C hoặc C++, để tra cứu giá trị tùy thuộc vào chuỗi đầu vào. Hàm băm là hoàn hảo, có nghĩa là bảng băm không có va chạm, và tra cứu bảng băm chỉ cần so sánh chuỗi đơn. "

Answer 2

Tôi đang làm việc trên an algorithm and Java implementation that needs less than 1.6 bits per key.

Trước đây, tôi đã triển khai a minimal perfect hash function tool in Java cần ít hơn 2.0 bit cho mỗi khóa.

Các thuật toán khác được triển khai trong CMPH. Ví dụ CHD cần khoảng 2.06 bit cho mỗi khóa theo mặc định. Nó có thể được cấu hình để sử dụng ít không gian hơn, nhưng thế hệ sau đó sẽ chậm hơn.