Tại sao ConcurrentNavigableMap được triển khai dưới dạng danh sách bỏ qua?

Question

Gần đây tôi đã chạy vào ConcurrentSkipListMap, đây là triển khai skip listConcurrentNavigableMap. Bây giờ tôi tự hỏi, tại sao nó được thực hiện như là một skip list.

Có skip list triển khai "chuẩn" điều hướng đồng thời bản đồ không? Điều gì làm cho skip list đặc biệt tốt cho nó?

Answer 1

ConcurrentSkipListMap mã nguồn đã ghi lại lý do.

Có hai lý do cho dùng phương pháp này thay vì việc triển khai thông thường mảng dựa trên

1. mảng dựa dường như gặp nhiều phức tạp và overhead
2. Chúng ta có thể sử dụng các thuật toán rẻ hơn cho các chỉ số chủ yếu-đi qua liệt kê hơn có thể được sử dụng cho các danh mục cơ sở

đây là javadoc

/* 
* This class implements a tree-like two-dimensionally linked skip 
* list in which the index levels are represented in separate 
* nodes from the base nodes holding data. **There are two reasons 
* for taking this approach instead of the usual array-based** 
* structure: 1) Array based implementations seem to encounter 
* more complexity and overhead 2) We can use cheaper algorithms 
* for the heavily-traversed index lists than can be used for the 
* base lists. Here's a picture of some of the basics for a 
* possible list with 2 levels of index: 
* 
* Head nodes   Index nodes 
* +-+ right  +-+      +-+ 
* |2|---------------->| |--------------------->| |->null 
* +-+     +-+      +-+ 
* | down    |      | 
* v     v      v 
* +-+   +-+ +-+  +-+   +-+  +-+ 
* |1|----------->| |->| |------>| |----------->| |------>| |->null 
* +-+   +-+ +-+  +-+   +-+  +-+ 
* v    | |   |    |   | 
* Nodes next  v v   v    v   v 
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ 
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null 
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+