Bảng băm sử dụng VLists

Question

Phil Bagwell, trong số 2002 paper on the VList data structure, cho biết rằng bạn có thể sử dụng VList để triển khai bảng băm liên tục. Tuy nhiên, lời giải thích của ông về cách làm việc đó không bao gồm nhiều chi tiết, và tôi không hiểu nó. Ai có thể cho tôi một lời giải thích chi tiết hơn, hoặc thậm chí là ví dụ?

Hơn nữa, nó xuất hiện với tôi từ những gì tôi có thể thấy rằng cấu trúc dữ liệu này, trong khi nó có thể có độ phức tạp lớn-O như một Hashtable, sẽ chậm hơn vì nó thực hiện tra cứu bổ sung. Có ai quan tâm để làm một phân tích chi tiết của chỉ chậm hơn bao nhiêu, tốt nhất là bao gồm cả hành vi bộ nhớ cache? Làm thế nào để mối quan hệ hiệu suất giữa hai thay đổi trong trường hợp không có va chạm hoặc nhiều?

Answer 1

Tôi đã xem bài báo này và nó xuất hiện rất sơ bộ. Thực tế là không có phiên bản nào sau đó đã được xuất bản và bản gốc xuất hiện trong IFL (đây là một cuộc họp đang tiến hành), cho thấy bạn có thể lãng phí thời gian của mình.

Answer 2

Hrmm dường như có một số vấn đề với cấu trúc dữ liệu do bài báo được đề cập.

Tắt dải, các danh sách ngây thơ được đề cập đầu tiên dường như cần tham chiếu duy nhất để nhận được bất kỳ thứ gì gần thời gian đảm bảo được đề xuất. Bạn mất khả năng phần lớn để chia sẻ đuôi. Bạn có thể chia sẻ các nút nhỏ về phía sau của danh sách, nhưng bạn sẽ phải sao chép nút vlist lớn nhất vào thời điểm bạn chống lại điều gì đó trên cdr của vlist vẫn đang hoạt động. Chi phí đó tỷ lệ thuận với chi phí sao chép toàn bộ danh sách.

Với các sửa đổi 2d được đề cập sau đó nó trở thành liên tục, nhưng nó là một hằng số khá lớn, vì bạn ít nhất sao chép phần đầu danh sách trang (hoặc tệ hơn, vlist) và trang đầu tiên trong danh sách của bạn .

Danh sách hàm băm chức năng trong đó dường như không có ý nghĩa nhiều với tôi. Đó chỉ là một sự xáo trộn ngắn ngủi dường như được gắn vào một tờ giấy không liên quan, không đủ chi tiết để thực sự tạo ra nó thực tế như thế nào.