Tra cứu bảng băm - với băm hoàn hảo, trong C

Question

Tôi có một ứng dụng ngôn ngữ C mà tôi cần thực hiện tra cứu bảng.

Các mục nhập là chuỗi, Tất cả đều được biết khi bắt đầu thời gian chạy. Bảng được khởi tạo một lần, và sau đó nhìn lên nhiều lần. Bảng có thể thay đổi, nhưng về cơ bản nó giống như ứng dụng bắt đầu lại. Tôi nghĩ rằng điều này có nghĩa là tôi có thể sử dụng một băm hoàn hảo? Nó là ok để tiêu thụ một thời gian cho khởi tạo hashtable, vì nó xảy ra chỉ một lần.

Sẽ có từ 3 đến 100.000 mục nhập, mỗi mục duy nhất và tôi ước tính rằng 80% trường hợp sẽ có ít hơn 100 mục nhập. Một tra cứu ngây thơ đơn giản là "đủ nhanh" trong những trường hợp đó. (== không ai phàn nàn)

Tuy nhiên trong trường hợp có 10k mục +, tốc độ tra cứu của cách tiếp cận ngây thơ là không thể chấp nhận. Cách tiếp cận tốt để cung cấp hiệu suất tra cứu dựa trên hashtable tốt cho các chuỗi trong C là gì? Giả sử tôi không có thư viện thương mại bên thứ ba như Boost/etc. Tôi nên sử dụng thuật toán băm nào? làm thế nào để tôi quyết định?

Answer 1

Tạo hàm băm hoàn hảo không phải là một vấn đề đơn giản. Có thư viện dành cho nhiệm vụ. Trong trường hợp này, phiên bản phổ biến nhất có lẽ là CMPH. Tôi đã không sử dụng nó mặc dù vậy không thể giúp vượt ra ngoài đó. gperf là một công cụ khác, nhưng nó đòi hỏi các chuỗi được biết đến tại thời gian biên dịch (bạn có thể làm việc xung quanh nó bằng cách biên dịch một .so và tải, nhưng loại quá mức cần thiết).

Nhưng thành thật mà nói, tôi ít nhất cũng cố gắng tìm kiếm nhị phân trước. Chỉ cần sắp xếp mảng bằng cách sử dụng qsort, sau đó tìm kiếm với bsearch (hoặc cuộn của riêng bạn). Cả hai đều là một phần của stdlib.h kể từ C89.

Answer 2

Nếu cách tiếp cận ngây thơ (tôi giả sử bạn tuyến tính) là ok cho 100 mục (do đó, 50 so sánh được thực hiện trên trung bình) thì tìm kiếm nhị phân sẽ đủ hơn 100.000 mục nhập (tối đa 17 lần so sánh).

Vì vậy, tôi sẽ không bận tâm với băm nhưng chỉ cần sắp xếp bảng chuỗi khi khởi động (ví dụ: sử dụng qsort) và sau đó sử dụng tìm kiếm nhị phân (ví dụ: sử dụng bsearch) để tra cứu các mục nhập.

Answer 3

Nếu kích thước bảng (tối đa) được biết, đồng bộ có thể bắt đầu bằng chuỗi là rất dễ thực hiện. Kích thước trên đầu chỉ là hai int cho mỗi mục. Với hàm băm hợp lý chỉ có 1,5 đầu dò mỗi lần tra cứu là cần thiết trên mức trung bình, điều này cho một bảng nạp 100%.

Xây dựng một băm hoàn hảo chỉ khả thi nếu dữ liệu của bạn không thay đổi. Một khi nó thay đổi, bạn sẽ phải tính toán lại và rehash, đó là cách đắt hơn so với làm một vài so sánh thêm.