perché no:Perché Object # hashCode() Restituisce int invece di lunga
public native long hashCode();
invece di:
public native int hashCode();
per una maggiore possibilità di raggiungere codici hash univoco?
Perché maximum length of an array è Integer.MAX_VALUE.
Poiché l'uso principale di hashCode() è determinare quale slot per inserire un oggetto in nell'array appoggio di un HashMap/Hashtable, un hashcode>Integer.MAX_VALUE non sarebbe in grado di essere memorizzati nella matrice.
Punto valido . Non sono sicuro che sia documentato in spec, ma 'HashMap' da Sun JDK non può avere una tabella più grande di' 1 << 30' (~ 'Integer.MAX_VALUE/2') – Roman
-1: L'array di supporto è quasi sempre molto più piccolo, quindi deve essere ridimensionato comunque. Ridimensionare da 64 bit non sarebbe un problema. Inoltre, hashCode() è consentito restituire valori negativi ... –
grazie per la risposta matt b, è assolutamente logico ora – dimitrisli
In ogni caso, il valore del codice hash verrà utilizzato per determinare un numero di righe in una tabella che è un valore relativamente piccolo.
In HashMap, ad esempio, la tabella predefinita contiene
256 righe
solo 16 righe (Sun JDK 1.6.0_17). Ciò significa che il numero di riga è determinato in modo simile:
int rowNumber = obj.hashCode() % rowsCount;
Così, la distribuzione reale è compreso tra 0 rowsCount.
UPD: Ricordo l'implementazione di ConcurrentHashMap. In poche parole, ConcurrentHashMap contiene molte tabelle relativamente piccole. Inizialmente la funzione hashCode viene utilizzata per determinare il numero della tabella e successivamente viene utilizzata la stessa funzione per determinare una riga nella tabella selezionata.
Questo approccio rimuove la limitazione della dimensione dell'array (e consente anche di creare una tabella hash distribuita).
Quindi, sono incline alla conclusione che hashCode restituisce int perché copre la maggior parte dei casi di utilizzo.
Questo non è abbastanza accurato, in quanto la dimensione della tabella può essere diversa dal valore predefinito, sia quando la tabella cresce o se diversi argomenti per 'initialCapacity' vengono passati al costruttore' HashMap'. –
E cosa non è preciso? :) Nessuno sostiene che il tavolo possa avere dimensioni maggiori di default. – Roman
è necessario rimuovere il bit più alto (ora il rowNumber può essere negativo) '(obj.hashCode & 0x7fffffff)% rowCount'. Dal momento che l'operazione mod è come 30 cpu clock (bitwise ed è 1), il numero di voci è mantenuto un power-of-2 e l'operazione è semplicemente '(obj.hashCode & (array.length-1))' – bestsss
Suppongo che si tratti di un equilibrio tra costo di calcolo e intervallo di hash. I codici hash vengono così frequentemente referenziati che spingere il doppio dei dati ogni volta che si ha bisogno di un hash sarebbe costoso, soprattutto se si considerano casi d'uso più comuni -
per esempio - se si crea un piccolo hash con 10 o 100, o 1000 valori, la differenza nel numero di collisioni hash che vedrete sarà estremamente trascurabile. Per gli hash più grandi, ... beh, pensa a quanto deve essere grande un hash per 10 ** 32 valori per iniziare ad avere collisioni frequenti, e se è possibile farlo anche in una JVM data la quantità di memoria che ti serve .
Questo potrebbe avere più senso con JDK a 64 bit, tuttavia anche oggi un hashCode lungo farebbe poca differenza. Hashcode non deve essere univoco e int a 32 bit va bene purché abbiate meno di 4 miliardi di voci. –
@PeterLawrey Sono d'accordo con te in linea di principio, ma [Preshing] (http://preshing.com/20110504/hash-collision-probabilities/) mostra che a causa della natura di questo problema, esiste una probabilità del 50% di collisione anche quando il tuo hash table ha appena 77.163 voci! –
@KedarMhaswade una HashMap con voci 78K è probabile che abbia una capacità di 128k in modo da utilizzare solo 17 bit del hashCode agitato. –