Hashtable hashing avoid hashcode negativo

Question

Mi chiedo perché non utilizzare Hashtable utilizzando hashcode negativo?

int hash = key.hashCode(); 
int index = (hash & 0x7FFFFFFF) % tab.length; 

Dove (hash & 0x7FFFFFFF) rende il bit relativo da 0 a positivo, ma perché non abbiamo potuto trattare il numero intero a 32 bit con segno come unsigned? o anche usare i trucchi modulari per renderlo positivo. Ad esempio,

public static long int_mod(int hashcode, int tab_length){ 
    return (hashcode % tab_length + tab_length) % tab_length; 
} 

Answer 1

Il valore deve essere compreso tra 0 e tab.length - 1 perché viene utilizzato come indice in una matrice interna (tab in questo caso) memorizzare i valori (ed elementi overflow). Pertanto, non può essere negativo.

Presumo che (hash & 0x7FFFFFFF) % tab.length sia utilizzato in preferenza di (hashcode % tab.length + tab.length) % tab.length perché è più veloce senza aumentare eccessivamente la possibilità di collisioni, ma è necessario trovare un documento di progettazione o parlare con gli sviluppatori originali per sapere con certezza.

Answer 2

... ma perché non potremmo ...

Mi stai chiedendo il motivo per cui una particolare implementazione è stato scelto. Nessuno può dirti questo, tranne forse l'autore originale del codice, se lui o lei si ricorda.

Ci sono sempre diversi modi per implementare un'idea nel codice. La persona che sta scrivendo il codice deve sceglierne uno. Non ha molto senso chiedere, dopo il fatto, perché non sia stata scelta un'altra particolare implementazione.

Answer 3

Java non ha un tipo non firmato nativo. Se lo hashCode avesse valori negativi, dovremo applicare questi trucchetti ovunque utilizziamo lo hashCode come indice nell'array.

Answer 4

Nessuno può parlarvi di perché l'autore originale ha scelto questa implementazione, tranne se stesso (e forse i suoi colleghi),. Non importa in ogni caso perché funziona bene.

Informazioni sull'implementazione proposta: Probabilmente non fa ciò che si pensa di . Dovresti aggiornare cosa fa realmente l'operatore% in java: For example here. Aggiungi overflow intero nel mix e l'espressione proposta può generare valori negativi ...

Answer 5

C'è una ragione apparentemente grande per cui non possiamo trattare l'int firmato come non firmato: gli sviluppatori Java originali pensavano che il supporto senza firma fosse un complicazione inutile, poiché l'aritmetica non firmata può essere confusing. Da allora, questo non è stato un problema abbastanza grande per Java.

Come verdesmerald mentioned, poiché non v'è alcuna chiara annotazione del motivo per cui è stato scelto (hash & 0x7FFFFFFF) % tab.length sopra qualcosa per l'effetto del modding intelligente, anche se possiamo trovare giustificazioni per la decisione, in ultima analisi, possiamo solo speculare sul perché è stato fatto.

Un ultimo punto della semantica, che probabilmente non è così importante: non è tanto che Hashtable non sta usando hashcode negativi quanto è che gli hashcode vengono "tradotti" in una forma non negativa per l'indice.

Answer 6

Se si mantiene la capacità di una potenza di 2,

private static final int CAPACITY = 64; 
private static final int HASH_MASK = CAPACITY - 1; 

final int index = obj.hashCode() & HASH_MASK; 

In sostanza, mascherare tutti, ma i bit inferiori in cui si è interessati. Supponendo che gli N bit inferiori abbiano come anche una distribuzione come l'intero codice hash.