Perché TreeMap di Java non consente una dimensione iniziale?

Question

Caricamento 1 000 000 numeri impiegano 2 secondi per caricarsi in una treemap (albero di ricerca binario), ma impiegano millisecondi per caricarsi in una mappa di hash (in java).
L'unica differenza tra i due è che posso vedere che è possibile impostare le dimensioni iniziali di hashmap in modo che non sia necessario ridimensionare continuamente.

Mi sbaglio supporre che le dimensioni iniziali dell'array TreeMap debbano essere impostate? C'è una ragione diversa per cui è così lento?
Esiste un motivo logico per cui non è possibile impostare la dimensione TreeMap o qualsiasi albero di ricerca binaria generico o è sbagliato?

Answer 1

A differenza di HashMap che riassegna i suoi interni come nuovi vengono inseriti, lo TreeMap in genere non rialloca i suoi nodi all'aggiunta di nuovi. La differenza può essere illustrata molto liberamente come quella tra ArrayList e LinkedList: il primo viene riallocato per ridimensionare, mentre il secondo no. Ecco perché l'impostazione della dimensione iniziale di un TreeMap è pressoché priva di significato come provare a impostare la dimensione iniziale di un LinkedList.

differenza La velocità è dovuta alla diversa complessità temporale dei due contenitori: inserimento N nodi in un HashMap è O(n), mentre per il TreeMap è O(N*LogN), che per 1000000 nodi è circa 20 volte asintotica differenza. Sebbene la differenza nella complessità asintotica non si traduca direttamente nella differenza di temporizzazione a causa delle diverse costanti dettate dai singoli algoritmi, serve come un buon modo per decidere quale algoritmo sarà più veloce su input molto grandi.

Answer 2

Una mappa di tre è sempre bilanciata. Ogni volta che aggiungi un nodo all'albero, devi accertarti che i nodi siano tutti in ordine dal comparatore fornito. Non hai una dimensione specificata perché la mappa degli alberi è progettata per un gruppo ordinato di nodi e per attraversare facilmente i nodi.

Una mappa hash deve disporre di una quantità di spazio disponibile per le cose che vengono memorizzate. Il mio professore mi ha sempre detto che ha bisogno di 5 volte la quantità di spazio che gli oggetti o qualsiasi cosa stiate memorizzando in quell'hashmap. Quindi, specificare la dimensione dalla creazione iniziale di Hashmap migliora la velocità della tua hashmap. Altrimenti, se hai più oggetti in una mappa di hash di quanto hai pianificato, l'hashmap deve "ridimensionare".

(a cura per l'ortografia)

Answer 3

mi sbaglio ad assumere dimensione iniziale della matrice di un TreeMap dovrebbe essere in grado di impostare?

Sì. A TreeMap non ha una matrice. A TreeMap utilizza i nodi binari con 2 figli.

Se si sta suggerendo che il numero di figli in un nodo ad albero debba essere un parametro, è necessario capire come questo influisce sul tempo di ricerca. E penso che giri il tempo di ricerca da O(log2N) a O(log2M * log2(N/M)) dove N è gli elementi numerici e M è il numero medio di nodi figli. (E sto facendo alcune supposizioni ottimistiche ...) Non è una "vittoria".

C'è una ragione diversa per cui è così lento?

Sì. La ragione per cui un (grande) TreeMap è lento rispetto a un (grande) HashMap in circostanze ottimali è che la ricerca utilizzando un albero binario bilanciato richiede l'osservazione dei nodi dell'albero log2N. Per contrasto, in un HashMap ottimale (fattore di carico buono e senza hotspot di collisione) una ricerca implica 1 calcolo hashcode e l'esame dei nodi hashchain O(1).

Note:

1. TreeMap utilizza un albero binario un'organizzazione che dà alberi bilanciati, in modo O(log2N) è il caso peggiore occhiata tempo.
2. HashMap prestazioni dipendono dal tasso di collisione della funzione hash e spazio chiave. Nel peggiore dei casi in cui tutte le chiavi finiscono sulla stessa catena di hash, una HashMap ha la ricerca O(N).

Answer 4

Mi sbaglio supporre che le dimensioni iniziali dell'array TreeMap debbano essere impostate?

Sì. non ha una matrice. Ha un albero.