Come fare per creare una Hashmap in C da zero? Quali sarebbero i parametri presi in considerazione e in che modo testeresti l'hashmap quanto è buono? Come in quelli che sarebbero i casi di test di riferimento che è necessario eseguire prima che tu dica che la tua mappa hash è completa.Implementazione di una HashMap
Beh, se si conoscono le basi dietro di loro, non dovrebbe essere troppo difficile.
Generalmente si crea un array denominato "bucket" che contiene la chiave e il valore, con un puntatore opzionale per creare un elenco collegato.
Quando si accede alla tabella di hash con una chiave, si elabora la chiave con una funzione di hash personalizzata che restituirà un numero intero. Quindi prendi il modulo del risultato e questa è la posizione dell'indice dell'array o "bucket". Quindi si controlla la chiave unhashed con la chiave memorizzata, e se corrisponde, allora hai trovato il posto giusto.
In caso contrario, si è verificata una "collisione" e si deve scorrere all'interno dell'elenco collegato e confrontare le chiavi finché non si combina. (nota alcune implementazioni usano un albero binario invece di una lista collegata per le collisioni).
Partenza questa implementazione tabella di hash veloce:
L'approccio migliore dipende dalla distribuzione delle chiavi prevista e dal numero di collisioni. Se si prevedono relativamente poche collisioni, in realtà non importa quale metodo viene utilizzato. Se ci sono molte collisioni tra previste, allora quale usare dipende dal costo del rehashing o del sondaggio vs. manipolazione della struttura di dati bucket estensibile.
Ma qui è il codice sorgente di esempio An Hashmap Implementation in C
Come il post successivo dice che abbiamo bisogno di gestire collisione anche. Inoltre l'implementazione hash ha un table_size che è come fisso. Se vogliamo aumentare dinamicamente la dimensione dell'hashmap, senza che il programmatore sappia come è fatto. Potresti suggerire qualcosa? – Thunderboltz
Ridimensionare lo spazio della chiave significa cambiare la funzione di hash o almeno i parametri della funzione e rimodellare tutte le voci. Ogni mappa di dimensioni diverse richiede un diverso set di funzioni hash per mantenere la distribuzione delle chiavi desiderata. – TStamper
Il link è stato interrotto –
Non ci sono altri meccanismi per gestire troppo pieno rispetto alla semplice lista collegata mentalità di voci di overflow, che per esempio spreca molta memoria
Quale meccanismo utilizzare dipende tra le altre cose se si può scegliere la funzione di hash ed è possibile selezionarne più di uno (implementare ad esempio doppio hashing per gestire le collisioni); se ti aspetti di aggiungere spesso elementi o se la mappa è statica una volta riempita; se hai intenzione di rimuovere gli articoli o meno; ...
Il modo migliore per implementare questo è pensare prima a tutti questi parametri e quindi non codificarli autonomamente, ma scegliere un'implementazione matura esistente. Google ha alcune buone implementazioni, ad es. http://code.google.com/p/google-sparsehash/
Sebbene rilevante per gli algoritmi, sparsehash è un'implementazione C++ di una hashmap. Se stai cercando le hashmap prerollate in puro C, guarda altrove. –
L'obiettivo principale di una mappa di hash è archiviare un set di dati e fornire ricerche di tempo quasi costante su di esso utilizzando una chiave univoca. Ci sono due stili comuni di attuazione hashmap:
concatenazioni separate è preferibile se il hashmap può avere una funzione hash povero, non è auspicabile pre-assegnare memoria per slot potenzialmente inutilizzati o voci possono avere dimensioni variabili. Questo tipo di hashmap può continuare a funzionare in modo relativamente efficiente anche quando il fattore di carico supera 1,0.Ovviamente, in ogni voce è richiesta memoria aggiuntiva per memorizzare i puntatori degli elenchi collegati.
Le mappe di hash che utilizzano l'indirizzamento aperto presentano potenziali vantaggi in termini di prestazioni quando il fattore di carico viene mantenuto al di sotto di una determinata soglia (in genere circa 0,7) e viene utilizzata una funzione di hash ragionevolmente buona. Questo perché evitano potenziali errori di cache e molte piccole allocazioni di memoria associate a un elenco collegato ed eseguono tutte le operazioni in un array contiguo e pre-allocato. Anche l'iterazione attraverso tutti gli elementi è più economica. La cattura è costituita da hashmap che utilizzano l'indirizzamento aperto devono essere riallocati a una dimensione maggiore e rehashed per mantenere un fattore di carico ideale, oppure devono affrontare una significativa penalizzazione delle prestazioni. È impossibile che il loro fattore di carico superi 1,0.
Alcune metriche di prestazioni chiave per valutare la creazione di un HashMap dovrebbe includere:
Ecco una implementazione di hashmap flessibile che ho realizzato. Ho usato l'indirizzamento aperto e il sondaggio lineare per la risoluzione delle collisioni.
Oltre a LL e alberi, è possibile avere una mappa hash per bucket che utilizza un hash diverso per gestire le collisioni. – sudo