Come può il metodo containsKey () di una tabella hash di Java essere O (1)? [duplicare]

Il motivo per cui l'accesso hash O (1) è in realtà molto diverso dall'accesso alla matrice.

Gli array sono aree di memoria contigue. Per leggere l'elemento 15, devi solo moltiplicare la dimensione dell'elemento per 15 e aggiungere l'indirizzo iniziale. Sia l'addizione che la moltiplicazione sono O (1) (ci vuole tanto tempo per aggiungere due grandi numeri come due piccoli numeri), e poiché i computer forniscono l'accesso alla memoria O (1), la complessità complessiva è ancora O (1).

Un hash funziona in modo molto diverso. Memorizza le cose in luoghi prevedibili, ma quei posti indicizzati non sono visibili all'utente. Una stringa inserita in una tabella hash non viene memorizzata all'indirizzo specificato; invece la tabella prende il contenuto di quella stringa e calcola un indirizzo adatto con hashing quel contenuto a un numero preso da un piccolo insieme di possibilità. Quindi memorizza il valore in quel punto e, se chiedi di nuovo quella chiave, ricalcola il valore dell'hash e cerca quella cella.

Poiché l'insieme di possibili valori hash è inferiore all'insieme di possibili chiavi, è possibile avere collisioni, in modo che sia necessario dedicare un po 'più di tempo a trovare il giusto valore quando più di una di esse è stata inserita lo stesso secchio, ma si può dimostrare che questo accade raramente e non influenza l'analisi complessiva complessità ammortizzata , che è ancora O (1).

Quindi vedi che un array può trovare le cose velocemente perché dici dove caricare; una tabella hash restituisce le cose velocemente perché conosce dove le colloca e può ricostruire efficientemente questo calcolo.

In Java, ogni oggetto ha un metodo hashCode() che restituisce un valore intero a 32 bit, che è sempre lo stesso per lo stesso oggetto. Nella versione più semplice, una tabella hash contiene semplicemente una matrice di dimensioni 2 ^ 32 e una coppia chiave-valore è memorizzata nell'indice corrispondente al codice hash della chiave. Poiché l'accesso dell'array per indice è O (1), l'accesso per chiave hashtable (per la memorizzazione o il recupero) può anche essere O (1).

Ovviamente è un po 'più complesso nella realtà. Primo, puoi sempre avere collisioni, cioè due oggetti diversi che danno lo stesso codice hash. Quindi gli elementi non sono memorizzati direttamente nell'array, piuttosto ogni indice dell'array contiene un "bucket", che è una lista ordinaria di coppie chiave-valore. (Nell'hashtable di Java i bucket sono implementati come elenchi collegati.) Devi cercare nel bucket per trovare l'elemento e questa ricerca sarà O (n), ma a meno che il tuo hashtable contenga un numero estremo di elementi (o il tuo algoritmo hash è sbagliato), gli elementi verranno distribuiti in modo uniforme sull'array e ogni bucket conterrà solo alcuni elementi. (Solo uno nel migliore dei casi.)

In secondo luogo, inizialmente non creerai una matrice di dimensioni 2 ^ 32, poiché sarebbe uno spreco di spazio. Invece, inizialmente si crea un array più piccolo, in cui ogni voce viene mappata su più hashcode. Ciò comporterà ovviamente un rischio maggiore di collisione. Tieni traccia del numero di voci e quando raggiungono una determinata soglia raddoppia la dimensione della matrice e quindi ridistribuisci gli elementi. Ovviamente questo avrà anche un costo in termini di prestazioni. C'è qualche compromesso nella progettazione nel decidere quando ridimensionare l'array. Più grande è l'array rispetto al numero di articoli, meno collisioni e quindi migliori prestazioni, ma anche più spreco di spazio.

Quindi trovare un oggetto è O (n) nel peggiore dei casi in cui tutti gli elementi si trovano nello stesso bucket, ma O (1) nel caso comune (data una funzione hash ben funzionante. hashCode() ovviamente non è garantito.Se scrivi int hashCode(){return 17;} ottieni sempre le peggiori prestazioni del caso). E se il numero di elementi aumenta più della dimensione hash, i bucket iniziano a crescere e di nuovo si ottiene la ricerca O (n). Sui sistemi a 32 bit si esaurirebbe la memoria prima che ciò accadesse, ma con la memoria a 64 bit potrebbe essere teoricamente un problema.

L'aggiunta di un elemento è anche O (1) nel caso comune, ma O (n) se l'aggiunta attiva un ridimensionamento dell'array. Tuttavia, il costo aggregato delle operazioni di ridimensionamento è prevedibile e proporzionale al numero di elementi, quindi il costo ammortizzato per gli add è ancora pari a O (1). Questo non è il caso peggiore con le ricerche, poiché se siamo sfortunati e tutti gli articoli finiscono nello stesso bucket ogni ricerca avrà le prestazioni peggiori e non c'è modo di ammortizzare questo costi.

Naturalmente sia il caso peggiore che il caso comune o medio possono essere rilevanti. In un sistema in tempo reale, è piuttosto importante conoscere le peggiori prestazioni di un'operazione. Per la maggior parte delle applicazioni aziendali, il caso medio è la metrica più importante.

Quando parli di misure (anche misurazioni astratte come "complessità algoritmica") devi sempre specificare esattamente che stai misurando, altrimenti quello che dici è completamente privo di significato.

In questo caso specifico, stai semplicemente dicendo "le tabelle hash sono O (1)", ma non stai dicendo cosa esattamente stai misurando.

In particolare, l'accesso a un valore per chiave in una tabella hash (progettata correttamente) ha

• complessità del passo peggiore di O (n) (o più precisamente, la complessità del passo peggiore di qualsiasi struttura dati viene utilizzata per il "bucket", che di solito è un semplice elenco collegato)
• ammortizzata complessità del passaggio nel caso peggiore di O (1)

In altre parole, tutta la tua confusione è dovuta al fatto che tu stai parlando del caso peggiore e gli altri stanno parlando del peggiore ammortizzato -case , ma ad eccezione di @ Kilian Foth nessuno si è preso la briga di menzionarlo.

L'argomento è simile a quello per il motivo per cui l'aggiunta di un elemento a un array di dimensioni dinamiche è O (n) worst-case e O (1) ammortizzato nel peggiore dei casi. @JacquesB spiega come funziona questo ammortamento per le tabelle hash.