Bản đồ băm được tối ưu hóa để tra cứu

Question

Tôi đang tìm một số bản đồ có các phím cố định (cố định trong khi khởi tạo) và tìm kiếm nhanh hơn. Nó có thể không hỗ trợ thêm/cập nhật các phần tử sau này. Có một số thuật toán tìm danh sách các khóa và tạo thành một hàm để tìm kiếm nhanh hơn sau này không. Trong trường hợp của tôi, các phím là dây.

Cập nhật:

Các khóa không biết lúc biên dịch. Nhưng trong thời gian khởi tạo ứng dụng. Sẽ không có thêm bất kỳ sự bổ sung nào sau này nhưng sẽ có rất nhiều điều tra cứu. Vì vậy, tôi muốn tìm kiếm được tối ưu hóa.

Answer 1

CMPH có thể là những gì bạn đang tìm kiếm. Về cơ bản, đây là gperfmà không cần yêu cầu đặt tại thời điểm biên dịch.

Mặc dù tất nhiên std::unordered_map như C++ 11 có thể chỉ làm quá, mặc dù có thể với một vài va chạm.

Vì bạn tra cứu chuỗi, cho chuỗi, một trie (bất kỳ vị trí trie khác, crit-bit hoặc bất kỳ tên sôi nổi nào) có thể đáng xem xét, đặc biệt nếu bạn có nhiều trong số chúng. Có rất nhiều triển khai trie miễn phí tự do có sẵn.
Lợi thế của các lần thử là chúng có thể nén chỉ mục, vì vậy chúng sử dụng ít bộ nhớ hơn, có khả năng có dữ liệu trong bộ nhớ cache cao hơn. Ngoài ra, mẫu truy cập ít ngẫu nhiên hơn, cũng thân thiện với bộ nhớ cache. Bảng băm phải lưu trữ giá trị cộng với hàm băm và lập chỉ mục nhiều hơn hoặc ít hơn ngẫu nhiên (không phải ngẫu nhiên, nhưng không thể đoán trước) vào bộ nhớ. Cấu trúc giống như trie/trie lý tưởng chỉ cần thêm một bit phân biệt một khóa từ tiền tố chung của nó trong mỗi nút.

(Lưu ý bởi cách mà O (log (N)) hoàn toàn có thể có thể nhanh hơn O (1) trong một trường hợp như vậy, bởi vì lớn-O không xem xét những thứ như thế.)

Answer 2

Thử google-sparsehash: http://code.google.com/p/google-sparsehash/

An extremely memory-efficient hash_map implementation. 2 bits/entry overhead! 
The SparseHash library contains several hash-map implementations, including 
implementations that optimize for space or speed. 

Answer 3

Lưu ý rằng đây là những điều khác biệt: bạn có cần giới hạn trên không, bạn có cần tốc độ nhanh điển hình hay bạn cần tra cứu nhanh nhất từ ​​trước đến giờ, không có câu hỏi nào? Người cuối cùng sẽ trả bạn, hai cái đầu tiên có thể là mục tiêu mâu thuẫn nhau.

---

Bạn có thể thử tạo hàm băm hoàn hảo dựa trên đầu vào (nghĩa là hàm băm không có va chạm của bộ đầu vào). Đây là một vấn đề được giải quyết bằng cách nào đó (ví dụ: this, this). Tuy nhiên, chúng thường tạo ra mã nguồn và có thể dành nhiều thời gian đáng kể để tạo ra hàm băm.

Sửa đổi điều này sẽ sử dụng hàm băm chung (ví dụ: shift-multiply-add) và thực hiện tìm kiếm bạo lực trên các thông số phù hợp.

Điều này phải được giao dịch với chi phí của một vài so sánh chuỗi (không quá đắt nếu bạn không phải đối chiếu).

Một tùy chọn khác là sử dụng hai hàm băm riêng biệt - điều này làm tăng chi phí của một tra cứu đơn lẻ nhưng làm cho sự xuống cấp ít có khả năng hơn người ngoài hành tinh ăn cắp đồng hồ của bạn. Nó là khá khó mà điều này sẽ là một vấn đề với các chuỗi điển hình và một hàm băm phong nha.

Answer 4

Trong một chủ đề tương tự ((số) mục được biết đến tại thời gian biên dịch), tôi đã tạo ra một mục này: Lookups on known set of integer keys. Chi phí thấp, không cần băm hoàn hảo. May mắn thay, nó là trong C ;-)