Perché initialCapacity di Hashtable è 11 mentre il DEFAULT_INITIAL_CAPACITY in HashMap è 16 e richiede una potenza di 2

Question

Confronto tra HashMap e Hashtable codice sorgente in jdk 1.6, vidi sotto codici all'interno HashMap

/** 
* The default initial capacity - MUST be a power of two. 
*/ 
static final int DEFAULT_INITIAL_CAPACITY = 16; 

    int capacity = 1; 
    while (capacity < initialCapacity) 
     capacity <<= 1; 

tuttavia, in Hashtable , ho visto sotto i codici?

table = new Entry[initialCapacity]; 

public Hashtable() { 
    this(11, 0.75f); 
} 

quindi la mia domanda è: perché HashMap richiede una potenza di 2 come capacità iniziale? e mentre hashtable scegliere 11 come la capacità iniziale predefinita? Suppongo che questo non ha nulla a che fare con la cosa che hashtable è thread-safe e non consente chiavi o valori nulli.

thx.

Answer 1

Il seguente articolo affronta questa domanda in modo dettagliato: HashMap requires a better hashCode() - JDK 1.4 Part II.

In base a questo articolo, il motivo principale per passare alla potenza di due dimensioni era che il mascheramento dei bit è più veloce della divisione dei numeri interi. Questo non è senza conseguenze negative, illustrati da uno degli autori originali:

Joshua Bloch: Lo svantaggio di usare una potenza di due figli è che la tabella hash risultante è molto sensibile alla qualità del hash funzione (hashCode). È fondamentale che qualsiasi modifica nell'input debba influire sui bit di ordine basso del valore hash. (Idealmente, dovrebbe influenzare tutti i bit del valore hash con uguale probabilità.) Perché non abbiamo la certezza che questo sia vero, abbiamo inserito una funzione hash secondaria (o "difensiva") quando siamo passati alla potenza di due tabella hash. Questa funzione di hash viene applicata ai risultati di hashCode prima di mascherare i bit di ordine basso. Il suo compito è quello di distribuire le informazioni su tutti i bit, e in particolare sui bit di ordine basso. Naturalmente è necessario eseguire molto velocemente, oppure si perde il vantaggio di passare alla tabella di potenza di due dimensioni. La funzione di hash secondaria originale in 1.4 si è rivelata insufficiente. Sapevamo che questa era una possibilità teorica, ma pensavamo che ciò non influisse su nessun set di dati pratici. Abbiamo sbagliato. La funzione secondaria di sostituzione dell'hash (che ho sviluppato con l'aiuto di un computer) ha forti proprietà statistiche che garantiscono quasi una buona distribuzione del bucket.

Answer 2

Questo potrebbe aiutare:

http://www.concentric.net/~Ttwang/tech/primehash.htm

Fondamentalmente, se non ricordo male, quando si dispone di una tabella hash con una dimensione che è potenza di 2, è facile ottenere una funzione di hash basato su i bit meno rilevanti della chiave.

L'utilizzo di un numero primo (come in 11) come dimensioni del tavolo rende meno probabile la collisione sulle righe del tavolo, pertanto l'inserimento è "più economico".

Answer 3

Il requisito per la dimensione della tabella di essere una potenza di due è un dettaglio di implementazione, non noto agli utenti della classe - è per questo che il cinturatore silenziosamente aggiusta il valore alla successiva potenza maggiore di due invece di segnalare un errore.

L'implementazione di Hashtable presuppone che l'hash non sia distribuito in modo uniforme, quindi tenta di utilizzare un numero di bin che è primo nella speranza di evitare picchi nella distribuzione di frequenza dell'hash.

La combinazione di questi due dettagli di implementazione porta a prestazioni non buone.

(ad esempio, una funzione hash primitiva sarebbe

int hash(String s, int nBins) { 
    return s[0] % nBins; 
} 

Se nBins è 32, e e E finiscono nello stesso scomparto, quindi la distribuzione di valori hash correla con la distribuzione di occorrenza di lettere, che ha picchi distinti - quindi la distribuzione di frequenza avrebbe un picco a 32.)

Answer 4

Hashtable utilizza dimensioni tabella pseudo-prime e aumenta le dimensioni della tabella relativamente più lentamente. HashMap utilizza una potenza di 2 come bit saggio ed è più veloce rispetto al modulo.

Ironia della sorte, un modulo di una potenza di 2 significa che è necessario un buon hashCode() in quanto i bit più in alto verrebbero ignorati, quindi HashMap ha un metodo per riorganizzare l'hashCode che si ottiene per evitare questo problema, il che significa che può essere effettivamente più lento. : Z