Imparare gli algoritmi

Capitolo 3. Vivere meglio grazie a un Hashing migliore

Questo lavoro è stato tradotto utilizzando l'AI. Siamo lieti di ricevere il tuo feedback e i tuoi commenti: [e-mail]

In questo capitolo imparerai:

• Come memorizzare le coppie (chiave, valore) in una tabella di simboli e recuperare i valori associati a una chiave.¹

• Come utilizzare un array per memorizzare coppie (chiave, valore) per una ricerca efficiente, se la dimensione dell'array è sufficientemente grande rispetto al numero di coppie memorizzate.

• Come utilizzare un array di liste collegate per memorizzare coppie (chiave, valore) per supportare la possibilità di rimuovere una chiave.

• Come ridimensionare una tabella di simboli per rimanere efficiente.

• Analisi ammortizzata per determinare le prestazioni medie del runtime quando il comportamento di un'operazione può cambiare con invocazioni successive.

• Come il ridimensionamento geometrico riduce la frequenza della costosa operazione di ridimensionamento, il che significa che put() ha prestazioni O(1) ammortizzate in media.

• Come una funzione hash computazionale può distribuire uniformemente i valori delle chiavi, garantendo l'efficienza dell'implementazione della tabella dei simboli.

Associare i valori alle chiavi

Invece di memorizzare solo i valori, potresti aver bisogno di memorizzare una collezione di coppie (chiave, valore) per associare i valori a chiavi specifiche. Questo è noto come tipo di tabella di simboli, che ti permette ...