Distribuzione del bucket Hashcode in java

Question

Supponiamo di dover memorizzare 1000 oggetti in Hashset, è meglio disporre di 1000 bucket contenenti ogni oggetto (generando un valore univoco per hashcode per ciascun oggetto) o avere 10 bucket contenenti circa 100 oggetti?

1 vantaggio di avere un bucket univoco è che posso salvare il ciclo di esecuzione chiamando il metodo equals()?

Perché è importante impostare il numero di bucket e distribuire gli oggetti tra loro nel modo più uniforme possibile?

Quale dovrebbe essere il rapporto ideale tra oggetto e benna?

Answer 1

Perché è importante impostare il numero di contenitori e distribuire gli oggetti tra loro quanto più uniformemente possibile?

A HashSet dovrebbe essere in grado di determinare l'appartenenza in O (1) tempo in media. Dalla documentation:

Questa classe offre prestazioni costante di tempo per le operazioni di base (aggiungere, rimuovere, contiene e dimensione), assumendo la funzione hash disperde gli elementi correttamente tra i secchi.

L'algoritmo un Hashset utilizza per raggiungere questo obiettivo è quello di recuperare il codice hash per l'oggetto e usare questo per trovare il secchio giusto. Quindi itera su tutti gli elementi nel bucket fino a quando ne trova uno uguale. Se il numero di elementi nel bucket è maggiore di O (1), la ricerca richiederà più tempo di O (1).

Nel peggiore dei casi, se tutti gli elementi hanno un hash nello stesso bucket, occorrerà O (n) per determinare se un oggetto è nell'insieme.

Quale dovrebbe essere il rapporto ideale tra oggetto e benna?

C'è un compromesso spazio-tempo qui. Aumentando il numero di benne diminuisce la possibilità di collisioni. Tuttavia, aumenta anche i requisiti di memoria. Il set di hash ha due parametri initialCapacity e loadFactor che consentono di regolare il numero di bucket creati da HashSet. Il fattore di caricamento predefinito è 0,75 e ciò va bene per la maggior parte degli scopi, ma se hai esigenze particolari puoi scegliere un altro valore.

Maggiori informazioni su questi parametri si possono trovare nella documentazione per HashMap:

Questa implementazione fornisce prestazioni costanti in tempo per le operazioni di base (get e put), assumendo la funzione di hash disperde gli elementi correttamente tra i secchi. Le visualizzazioni di iterazione su collezione richiedono tempi proporzionali alla "capacità" dell'istanza di HashMap (il numero di bucket) più le sue dimensioni (il numero di mappature di valori-chiave). Pertanto, è molto importante non impostare la capacità iniziale troppo alta (o il fattore di carico troppo basso) se le prestazioni di iterazione sono importanti.

Un'istanza di HashMap ha due parametri che influiscono sulle sue prestazioni: capacità iniziale e fattore di carico. La capacità è il numero di bucket nella tabella hash e la capacità iniziale è semplicemente la capacità al momento della creazione della tabella hash. Il load factor è una misura di quanto è possibile ottenere la tabella hash prima che la sua capacità venga aumentata automaticamente.Quando il numero di voci nella tabella hash supera il prodotto del fattore di carico e la capacità corrente, la capacità viene approssimativamente raddoppiata chiamando il metodo rehash.

Come regola generale, il fattore di carico predefinito (.75) offre un buon compromesso tra costi di spazio e tempo. Valori più alti riducono l'overhead dello spazio ma aumentano il costo di ricerca (riflesso nella maggior parte delle operazioni della classe HashMap, inclusi get e put). Il numero previsto di voci nella mappa e il suo fattore di carico dovrebbero essere presi in considerazione quando si imposta la sua capacità iniziale, in modo da ridurre al minimo il numero di operazioni di rehash. Se la capacità iniziale è maggiore del numero massimo di voci diviso per il fattore di carico, non si verificherà mai alcuna operazione di restringimento.

Answer 2

Circa un bucket per elemento è migliore per il processore, troppi bucket sono dannosi per la memoria. Java inizierà con una piccola quantità di bucket e aumenterà automaticamente la capacità del tuo HashSet una volta avviato il riempimento, quindi non devi preoccuparti se la tua applicazione non ha problemi di prestazioni e hai identificato un hashset come causa.

Se si dispone di più elementi in ciascun bucket, le ricerche iniziano a richiedere più tempo. Se disponi di molti bucket vuoti, stai utilizzando più memoria del necessario e l'iterazione sugli elementi richiede più tempo.

Questo sembra un'ottimizzazione prematura in attesa che accada anche se - il costruttore predefinito va bene nella maggior parte dei casi.

Answer 3

Object.hashCode() sono di tipo int, si può avere solo 2^32 valori diversi è per questo che si crea secchi e distribuire gli oggetti tra di loro.

Edit: Se si utilizza 2^32 secchi per memorizzare 2^32 oggetto poi con aria di sfida ottenere operazioni vi consentirà di ottenere costantemente la complessità, ma quando si inserisce uno dopo l'altro elemento per memorizzare 2^32 oggetti poi rimasticare si esibirà di mezzi se noi stanno usando Object[] come bucket quindi ogni volta che supera la lunghezza di array creerà nuovo array con di dimensioni maggiori e copierà elementi in questo. questo processo aumenterà la complessità. Ecco perché utilizziamo lo equals e il hashcode in rapporto e ciò viene effettuato dallo Hashsets stesso fornendo il migliore hashing algorithm.