In molti posti, ho letto che possiamo usare HashMap qui per la ricerca O (1). In realtà, vorrei chiedere come posso implementare semplici hashmap in grado di soddisfare questa proprietà. Qualcuno può dire alcune hashmaps compreso la cosa di collisione in considerazione.
Non voglio i codici completi. Voglio solo pseudo codice o algoritmo per questo. Sono curioso di sapere cosa cosa perché leggo che queste hashmap usano molto e in molti posti. Grazie mille in anticipo.
Per mantenere le collisioni al minimo, ci sono due grandi cose che devi assolutamente correggere:
La dimensione dell'hashmap deve essere sufficiente per contenere la maggior parte o tutti i dati senza collisioni. Naturalmente, puoi avere una mappa di hash che si ridimensiona dinamicamente dopo aver visto molte collisioni; dovresti comunque ottenere O (1) ammortizzato a condizione che ciò non accada troppo spesso.
La funzione di hash deve essere sufficiente per rendere le collisioni un evento raro sul set di dati. Le proprietà dei tuoi dati sono molto importanti qui, ma per un elenco dettagliato delle opzioni generali, vedi questa domanda PSE esistente . La risposta breve sembra essere "usa FNV-1a".
Inoltre, qui ci sono alcuni esempi di codice semplici per aiutarti a iniziare .
Leggi altre domande sui tag c++ data-structures hashing search