Perché non esiste una TreeMap simultanea?

Question

Ho un paio di domande relative a java.util.concurrent; pacchetto:

1. Perché nelle API di Java v'è la non-concorrente TreeMap da un lato e la concomitante ConcurrentSkipListMap su un altro?

2. Perché non lo chiamano ConcurrentTreeMap? È sicuro dire che SkipListMap include una TreeMap?

Per esempio un non concomitante HashMap ha ottenuto la sua controparte concomitante ConcurrentHashMap. Perché non succede per lo TreeMap?

Answer 1

Perché c'è una TreeMap non concomitante su un lato e ConcurrentSkipListMap su un altro?

Sospetto che ciò sia stato fatto perché creare una struttura ad albero concomitante era troppo difficile o soffriva di problemi di prestazioni di blocco. In termini di collezioni ordinate, SkipList sono strutture di dati molto semplici e offrono comportamenti e prestazioni simili agli alberi.

In realtà sono più deluso dal fatto che non ci sia una raccolta SkipList non simultanea.

È sicuro dire che una SkipListMap ha incluso una TreeMap?

No. è sicuro di dire che un SkipList dà caratteristiche simili in termini di un insieme ordinato di elementi che dà O(logN) prestazioni per la ricerca, inserimento, cancellazione, ecc .. Almeno dà un'approssimazione probabilistico di quella prestazione.

Ecco uno good page about skiplists. Sono strutture dati estremamente interessanti. Posso solo sperare che vengano insegnate nelle moderne classi di strutture di dati di programmazione.

Answer 2

La classe TreeMap viene chiamata in questo modo perché è implementata utilizzando uno balanced search tree. Lo ConcurrentSkipListMap viene chiamato così perché è implementato utilizzando uno skip list. Perché non esiste una versione simultanea di TreeMap? Forse perché è difficile creare una struttura ad albero che si adatti a livelli elevati di concorrenza; una lista skip simultanea è più facile da implementare correttamente.