Una hashmap di Java è veramente O (1)?

Ho visto alcune affermazioni interessanti sugli hashmap SO re Java e sul loro tempo di ricerca O(1) . Qualcuno può spiegare perché è così? A meno che queste hashmap siano molto diverse da qualsiasi algoritmo di hashing su cui sono stato acquistato, deve sempre esistere un set di dati che contiene collisioni.

In tal caso, la ricerca sarebbe O(n) anziché O(1) .

Qualcuno può spiegare se sono O (1) e, in tal caso, come ottengono ciò?

Una caratteristica particolare di una HashMap è che, diversamente dagli alberi bilanciati, il suo comportamento è probabilistico. In questi casi è di solito più utile parlare di complessità in termini di probabilità che si verifichi un evento nel peggiore dei casi. Per una mappa hash, ovviamente è il caso di una collisione rispetto a quanto sia piena la mappa. Una collisione è abbastanza facile da stimare.

collisione = n / capacità

Quindi una mappa di hash con un numero modesto di elementi è abbastanza probabile che si verifichi almeno una collisione. La notazione Big O ci consente di fare qualcosa di più avvincente. Osserva che per ogni costante fissa arbitraria k.

O (n) = O (k * n)

Possiamo utilizzare questa funzione per migliorare le prestazioni della mappa hash. Potremmo invece pensare alla probabilità di almeno 2 collisioni.

collisione x 2 = (n / capacità) 2

Questo è molto più basso. Poiché il costo della gestione di una collisione supplementare è irrilevante per le prestazioni di Big O, abbiamo trovato un modo per migliorare le prestazioni senza effettivamente modificare l’algoritmo! Possiamo generalizzare questo a

p collisione xk = (n / capacità) k

E ora possiamo ignorare un numero arbitrario di collisioni e finire con una minacciosa probabilità di più collisioni di quelle che stiamo calcolando. È ansible ottenere la probabilità a un livello arbitrariamente piccolo scegliendo il k corretto, il tutto senza alterare l’effettiva implementazione dell’algoritmo.

Parliamo di questo dicendo che la mappa hash ha accesso O (1) ad alta probabilità

Sembra che si mischi il comportamento del caso peggiore con il runtime medio (previsto). Il primo è in effetti O (n) per le tabelle hash in generale (cioè non utilizza un hashing perfetto), ma questo è raramente rilevante nella pratica.

Qualsiasi implementazione di hash table affidabile, accoppiata a un hash metà decente, ha una prestazione di recupero di O (1) con un fattore molto piccolo (2, in effetti) nel caso previsto, all’interno di un margine di varianza molto stretto.

In Java, HashMap funziona utilizzando hashCode per individuare un bucket. Ogni bucket è un elenco di elementi che risiedono in quel bucket. Gli articoli sono scansionati, usando uguali per il confronto. Quando aggiungi elementi, HashMap viene ridimensionato una volta raggiunta una certa percentuale di carico.

Quindi, a volte dovrà confrontarsi con alcuni elementi, ma generalmente è molto più vicino a O (1) che a O (n). Per scopi pratici, è tutto ciò che dovresti sapere.

Ricorda che o (1) non significa che ogni ricerca esamina solo un singolo elemento, significa che il numero medio di elementi controllati rimane costante rispetto al numero di elementi nel contenitore. Quindi se occorrono in media 4 confronti per trovare un object in un contenitore con 100 articoli, dovrebbe anche richiedere una media di 4 confronti per trovare un object in un contenitore con 10000 articoli e per qualsiasi altro numero di articoli (c’è sempre un un po ‘di varianza, specialmente attorno ai punti in cui la tabella hash rihash e quando c’è un numero molto piccolo di elementi).

Quindi le collisioni non impediscono al contenitore di avere operazioni su o (1), a condizione che il numero medio di chiavi per bucket rimanga entro un limite fisso.

So che questa è una vecchia domanda, ma in realtà c’è una nuova risposta.

Hai ragione che una mappa hash non è O(1) , in senso stretto, perché il numero di elementi diventa arbitrariamente grande, alla fine non sarai in grado di cercare in tempo costante (e la notazione O è definita in termini di numeri che possono diventare arbitrariamente grandi).

Ma non segue che la complessità in tempo reale sia O(n) perché non esiste una regola che dice che i bucket devono essere implementati come una lista lineare.

Infatti, Java 8 implementa i bucket come TreeMaps quando superano una soglia, il che rende l’ora effettiva O(log n) .

Se il numero di bucket (chiamiamolo b) è mantenuto costante (il solito caso), allora la ricerca è in realtà O (n).
Man mano che n diventa grande, il numero di elementi in ogni bucket è in media n / b. Se la risoluzione della collisione viene eseguita in uno dei modi usuali (ad esempio l’elenco collegato), la ricerca è O (n / b) = O (n).

La notazione O riguarda ciò che accade quando n diventa sempre più grande. Può essere fuorviante se applicato a determinati algoritmi e le tabelle di hash sono un esempio calzante. Scegliamo il numero di bucket in base a quanti elementi ci aspettiamo di gestire. Quando n ha all’incirca la stessa dimensione di b, allora la ricerca è approssimativamente costante, ma non possiamo chiamarla O (1) perché O è definito in termini di limite come n → ∞.

O(1+n/k) dove k è il numero di bucket.

Se l’implementazione imposta k = n/alpha allora è O(1+alpha) = O(1) poiché alpha è una costante.

Abbiamo stabilito che la descrizione standard delle ricerche di tabelle hash pari a O (1) si riferisce al tempo previsto per il caso medio, non alla rigorosa prestazione del caso peggiore. Per una tabella hash che risolve le collisioni con il concatenamento (come l’hashmap di Java) questo è tecnicamente O (1 + α) con una buona funzione di hash , dove α è il fattore di carico della tabella. Sempre costante finché il numero di oggetti che stai memorizzando non è più di un fattore costante più grande della dimensione della tabella.

È stato anche spiegato che in senso stretto è ansible build input che richiedono ricerche O ( n ) per qualsiasi funzione di hash deterministica. Ma è anche interessante considerare il tempo atteso nel caso peggiore, che è diverso dal tempo di ricerca medio. Usare il concatenamento è O (1 + la lunghezza della catena più lunga), per esempio Θ (log n / log log n ) quando α = 1.

Se ti interessano i metodi teorici per ottenere previsioni di casi peggiori attesi per il tempo costante, puoi leggere dell’hashing dinamico perfetto che risolve le collisioni in modo ricorsivo con un’altra tabella hash!

È O (1) solo se la tua funzione di hashing è molto buona. L’implementazione della tabella hash Java non protegge dalle funzioni hash errate.

Se è necessario far crescere la tabella quando si aggiungono o meno elementi non è rilevante per la domanda perché riguarda il tempo di ricerca.

Questo fondamentalmente vale per la maggior parte delle implementazioni di hash table nella maggior parte dei linguaggi di programmazione, in quanto l’algoritmo stesso non cambia realmente.

Se non ci sono collisioni presenti nella tabella, è sufficiente effettuare una sola ricerca, pertanto il tempo di esecuzione è O (1). Se sono presenti collisioni, è necessario eseguire più di una ricerca, che riduce le prestazioni a O (n).

Dipende dall’algoritmo scelto per evitare le collisioni. Se l’implementazione utilizza il concatenamento separato, lo scenario peggiore si verifica quando ogni elemento di dati viene sottoposto a hashing sullo stesso valore (scelta scadente della funzione di hash, ad esempio). In tal caso, la ricerca dei dati non è diversa da una ricerca lineare su un elenco collegato, vale a dire O (n). Tuttavia, la probabilità che ciò accada è trascurabile e le ricerche migliori ei casi medi rimangono costanti cioè O (1).

Accademici a parte, da un punto di vista pratico, HashMaps dovrebbe essere accettato come avente un impatto sulle prestazioni insignificante (a meno che il tuo profiler non ti dica diversamente).

Solo nel caso teorico, quando gli hashcode sono sempre diversi e anche il bucket per ogni codice hash è diverso, esiste O (1). Altrimenti, è di ordine costante cioè su incremento di hashmap, il suo ordine di ricerca rimane costante.

Gli elementi all’interno di HashMap sono memorizzati come una matrice di elenchi collegati (nodes), ogni elenco collegato nella matrice rappresenta un bucket per un valore hash univoco di una o più chiavi.
Durante l’aggiunta di una voce in HashMap, l’hashcode della chiave viene utilizzato per determinare la posizione del bucket nell’array, ad esempio:

 location = (arraylength - 1) & keyhashcode 

Qui il & rappresenta operatore AND bit a bit.

Ad esempio: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

Durante l’operazione get utilizza lo stesso metodo per determinare la posizione del bucket per la chiave. Nel migliore dei casi ogni hashcode è univoco e restituisce un bucket univoco per ogni chiave, in questo caso il metodo get spende solo il tempo per determinare la posizione del bucket e il recupero del valore che è costante O (1).

Nel peggiore dei casi, tutte le chiavi hanno lo stesso codice hash e memorizzate nello stesso bucket, questo si traduce in un attraversamento dell’intero elenco che porta a O (n).

Nel caso di java 8, il bucket Elenco collegato viene sostituito con TreeMap se le dimensioni aumentano a più di 8, riducendo l’efficienza di ricerca del caso peggiore a O (log n).

Ovviamente le prestazioni dell’hashmap dipendono dalla qualità della funzione hashCode () per l’object dato. Tuttavia, se la funzione è implementata in modo tale che la possibilità di collisioni sia molto bassa, avrà una prestazione molto buona (questo non è rigorosamente O (1) in ogni caso ansible ma è nella maggior parte dei casi).

Ad esempio, l’implementazione predefinita in Oracle JRE consiste nell’utilizzare un numero casuale (che viene archiviato nell’istanza dell’object in modo che non venga modificato, ma disabilita anche il blocco spinto, ma si tratta di un’altra discussione), quindi la possibilità di collisioni è molto basso.