Tại sao không có TreeMap đồng thời?

Question

Tôi có một vài câu hỏi liên quan đến java.util.concurrent; gói:

1. Tại sao trong API java có là không đồng thời TreeMap ở một bên và đồng thời ConcurrentSkipListMap trên kia?

2. Tại sao họ không gọi nó là ConcurrentTreeMap? Có an toàn khi nói rằng SkipListMap bao gồm TreeMap không?

Ví dụ một tổ chức phi đồng thời HashMap đã có đối tác đồng thời của nó ConcurrentHashMap. Tại sao nó không xảy ra cho TreeMap?

Answer 1

Tại sao có TreeMap không đồng thời ở một bên và ConcurrentSkipListMap trên một mặt khác?

Tôi nghi ngờ điều này đã được thực hiện vì việc tạo cấu trúc cây đồng thời quá khó hoặc gặp phải sự cố về hiệu suất khóa. Về các bộ sưu tập được sắp xếp, SkipLists là các cấu trúc dữ liệu rất đơn giản và cung cấp hành vi và hiệu suất tương tự cho cây.

Tôi thực sự thất vọng hơn vì bản thân tôi không có bộ sưu tập SkipList không đồng thời.

Có an toàn để nói rằng SkipListMap bao gồm TreeMap không?

số Nó là an toàn để nói rằng một SkipList cho các tính năng tương tự về một bộ sưu tập có thứ tự các mặt hàng cung cấp cho O(logN) hiệu suất cho tra cứu, chèn, xóa, vv .. Ít nhất nó mang lại cho một xấp xỉ xác suất hiệu suất đó.

Đây là good page about skiplists. Chúng là cấu trúc dữ liệu cực kỳ thú vị. Tôi chỉ có thể hy vọng được dạy trong các lớp cấu trúc dữ liệu lập trình hiện đại.

Answer 2

Lớp TreeMap được gọi theo cách đó bởi vì nó được triển khai bằng cách sử dụng balanced search tree. ConcurrentSkipListMap được gọi theo cách đó bởi vì nó được triển khai bằng cách sử dụng skip list. Tại sao không có phiên bản đồng thời của TreeMap? Có thể bởi vì thật khó để tạo ra một cấu trúc cây có quy mô đến mức độ đồng thời cao; danh sách bỏ qua đồng thời dễ thực hiện hơn.