Loại cấu trúc dữ liệu nào được sử dụng cho các bản đồ bất biến?

Question

Tôi biết bản đồ có thể thay đổi được như thế nào (sử dụng hashtables) và tôi biết danh sách bất biến hoạt động như thế nào (ví dụ: danh sách liên kết đệ quy) và lợi thế của chúng so với danh sách có thể thay đổi (liên tục thời gian phụ thêm mà không làm hỏng bản gốc)) công việc?

Tôi biết lợi thế của việc không gây rối với bản đồ gốc khi tạo bản đồ mới, nhưng cấu trúc dữ liệu cơ bản hoạt động như thế nào và chúng có đặc điểm hiệu suất nào, ví dụ so với bảng băm có thể thay đổi? Có bất kỳ cấu trúc dữ liệu chuẩn nào mà mọi người sử dụng để triển khai thực hiện chúng, mà tôi có thể tìm trong CLRS/wikipedia không?

Answer 1

Persistent Hash bản đồ được triển khai bằng cấu trúc được gọi là Hash trie. Đó là originally proposed by Phil Bagwell (là thành viên của nhóm Scala tại EPFL) nhưng thực sự được Clojure triển khai trước tiên. Nó nhấn scala khi 2,8 ra trong năm 2010.

Có một great talk on functional data structures bởi Dan Spiewak nơi cơ của Trie băm được giải thích cực kỳ cách rõ ràng cách (cùng với những thứ khác như hàng đợi của ngân hàng)! Anh ấy cũng giải thích hiệu suất to-aptptotic big-O rất tốt trong buổi nói chuyện.

Tháng 10 năm ngoái, Phil cho một cuộc trò chuyện khác tại số London scala Lift Off, lần này trên cấu trúc dữ liệu liên tục song song.

bản đồ được sắp xếp liên tục được thực hiện thông qua một Red-Black tree

Answer 2

Nó có thể là một cây (đỏ đen) hoặc bản đồ băm. Đặc điểm truy cập của họ phụ thuộc vào việc triển khai cơ bản. Cây là O (log n) để đọc truy cập; một bản đồ băm là O (1).