Warum gibt es keine gleichzeitige TreeMap?

Question

Ich habe ein paar Fragen zu java.util.concurrent; Paket bezogen werden:

1. Warum in der Java-API gibt es die nicht gleichzeitige TreeMap auf der einen Seite und die gleichzeitige ConcurrentSkipListMap auf einem anderen?

2. Warum haben sie es nicht ConcurrentTreeMap genannt? Ist es sicher zu sagen, dass eine SkipListMap eine TreeMap enthält?

Zum Beispiel eine nicht gleichzeitige HashMap hat seine gleichzeitige Gegenstück ConcurrentHashMap bekam. Warum passiert das nicht für die TreeMap?

Answer 1

Warum gibt es die nicht gleichzeitige TreeMap auf der einen Seite und die ConcurrentSkipListMap auf einer anderen Seite?

Ich vermute, dass dies getan wurde, weil das gleichzeitige Erstellen einer Baumstruktur zu schwierig war oder an Sperrleistungsproblemen litt. In Bezug auf geordnete Sammlungen sind SkipLists sehr einfache Datenstrukturen und bieten Bäumen ein ähnliches Verhalten und eine ähnliche Leistung.

Ich bin eigentlich mehr enttäuscht, dass es keine nicht-gleichzeitige SkipList-Sammlung selbst gibt.

Ist es sicher zu sagen, dass eine SkipListMap eine TreeMap enthielt?

Nein, es ist sicher zu sagen, dass ein SkipList ähnliche Merkmale in Bezug auf eine geordnete Sammlung von Gegenständen gibt, die O(logN) Leistung für die Suche gibt, einfügen, löschen, etc .. Wenigstens gibt es eine probabilistische Annäherung von dieser Leistung.

Hier ist ein good page about skiplists. Sie sind extrem coole Datenstrukturen. Ich kann nur hoffen, dass sie in modernen Programmierdatenstrukturen unterrichtet werden.

Answer 2

Die Klasse TreeMap heißt so, weil sie mit einem balanced search tree implementiert wird. Die ConcurrentSkipListMap wird so genannt, weil sie mit einem skip list implementiert ist. Warum gibt es keine gleichzeitige Version von TreeMap? Möglicherweise, weil es schwer ist, eine Baumstruktur zu erstellen, die auf hohe Nebenläufigkeit skaliert; Eine gleichzeitige Überspringungsliste lässt sich leichter korrekt implementieren.