khi nào để thay đổi kích thước bảng băm?

Question

Trong các triển khai bảng băm khác nhau, tôi đã thấy "số ma thuật" cho khi một bảng băm có thể thay đổi được nên thay đổi kích thước (phát triển). Thông thường con số này là một nơi nào đó giữa 65% đến 80% của các giá trị được thêm vào mỗi khe được phân bổ. Tôi giả sử giao dịch giảm là số lượng cao hơn sẽ tạo ra khả năng có nhiều va chạm hơn và số lượng thấp hơn với chi phí sử dụng nhiều bộ nhớ hơn.

Câu hỏi của tôi là số này đến như thế nào?

Có tùy ý không? dựa trên thử nghiệm? dựa trên một số logic khác?

Answer 1

Khi đoán, hầu hết mọi người ít nhất bắt đầu từ các số trong một cuốn sách (ví dụ, Knuth, Tập 3), được sản xuất bằng cách kiểm tra. Tùy thuộc vào tình hình, một số có thể thực hiện kiểm tra sau đó, và thực hiện điều chỉnh cho phù hợp - nhưng từ những gì tôi đã nhìn thấy, đây có lẽ là trong thiểu số.

Như tôi đã nêu trong số previous answer, số "đúng" cũng phụ thuộc rất nhiều vào cách bạn giải quyết xung đột. Đối với tốt hơn hoặc tệ hơn, thực tế này dường như bị bỏ qua rộng rãi - mọi người thường xuyên không chọn những con số đặc biệt thích hợp cho độ phân giải va chạm mà họ sử dụng.

OTOH, điểm khác mà tôi thấy trong thử nghiệm của tôi là nó hiếm khi tạo ra nhiều sự khác biệt. Bạn có thể chọn số trên một phạm vi khá rộng và có được tốc độ tổng thể khá giống nhau. Điều chính là phải cẩn thận để tránh đẩy số quá cao, đặc biệt là nếu bạn đang sử dụng một cái gì đó giống như thăm dò tuyến tính để giải quyết va chạm.

Answer 2

Theo như tôi biết số lượng là một heuristic dựa trên thử nghiệm thực nghiệm.

Với phân phối hợp lý các giá trị băm có vẻ như hệ số tải ma thuật là - như bạn nói - thường khoảng 70%. Một yếu tố tải nhỏ hơn có nghĩa là bạn đang lãng phí không gian vì không có lợi ích thực sự; một hệ số tải cao hơn có nghĩa là bạn sẽ sử dụng ít không gian hơn nhưng dành nhiều thời gian hơn để xử lý các xung đột băm.

(Tất nhiên, nếu bạn biết rằng giá trị băm của bạn được phân phối một cách hoàn hảo thì hệ số tải của bạn có thể là 100% và bạn vẫn sẽ không có không gian lãng phí và không có va chạm băm.)

Answer 3

đó phụ thuộc vào các phím . Nếu bạn biết rằng hàm băm của bạn là hoàn hảo cho tất cả các khóa có thể (ví dụ, sử dụng gperf), thì bạn biết rằng bạn sẽ chỉ có một vài va chạm, vì vậy con số này cao hơn.

Nhưng phần lớn thời gian, bạn không biết nhiều về khóa ngoại trừ chúng là văn bản. Trong trường hợp này, bạn phải đoán vì bạn thậm chí không có dữ liệu thử nghiệm để tìm hiểu trước cách hàm băm của bạn hoạt động như thế nào.

Vì vậy, bạn hy vọng điều tốt nhất. Nếu hàm băm của bạn rất tệ đối với các khóa, thì bạn sẽ có rất nhiều va chạm và điểm phát triển sẽ không bao giờ đạt được. Trong trường hợp này, con số được chọn là không liên quan.

Nếu hàm băm của bạn là đủ, thì nó chỉ tạo ra một vài va chạm (dưới 50%), do đó, một số từ 65% đến 80% có vẻ hợp lý.

Điều đó cho biết: Trừ khi bảng băm của bạn phải hoàn hảo (= kích thước lớn hoặc nhiều quyền truy cập), đừng bận tâm. Nếu bạn có, nói rằng, mười yếu tố, xem xét những vấn đề này là một sự lãng phí thời gian.

Answer 4

Va chạm phụ thuộc nhiều vào dữ liệu và hàm băm được sử dụng.

Hầu hết các số dựa trên chẩn đoán hoặc giả định về phân phối bình thường giá trị băm. (Giá trị AFAIK khoảng 70% là điển hình cho các bảng băm mở rộng, nhưng người ta luôn có thể xây dựng luồng dữ liệu đó, để bạn nhận được nhiều xung đột/ít hơn)

Answer 5

Tôi nghĩ bạn không muốn xem xét bảng "đầy đủ" (bao nhiêu "nhóm" trong tổng số nhóm có giá trị) nhưng thay vào đó số lần va chạm có thể mất để tìm vị trí cho mục mới .

Tôi đọc một số cuốn sách biên dịch năm trước (không thể nhớ tiêu đề hoặc tác giả) đề xuất chỉ sử dụng danh sách được liên kết cho đến khi bạn có nhiều hơn 10 đến 12 mục. Điều đó dường như hỗ trợ hơn 10 va chạm có nghĩa là thời gian để tái kích thước.

The Design and Implementation of Dynamic. Hashing for Sets and Tables in Icon cho thấy chiều dài chuỗi băm trung bình là 5 (trong thuật toán đó, số lần va chạm trung bình) đủ để kích hoạt phục hồi. Có vẻ như được hỗ trợ bằng cách kiểm tra, nhưng tôi không chắc tôi đang đọc bài báo một cách chính xác.

Có vẻ như điều kiện thay đổi kích thước chủ yếu là kết quả thử nghiệm.