Tabella hash di progettazione con semplice funzione di hash

Se vuoi costruire una tabella hash in Java, dovresti sfruttare i metodi hashCode e equals che ha l'oggetto ogni , quindi non c'è bisogno di escogitare un hash personalizzato funzione. Nota che tutti i "caratteri" di Java sono già numeri nell'intervallo 0x00 – 0xFFFF (sono unità di codice UTF-16, non caratteri ASCII o byte).

La tua idea che il codice hash sia un'interpretazione Base-26 o Base-128 è una buona idea per i testi solo alfabetici / ASCII. Ma ci sono alcuni problemi che riesco a vedere:

• Le stringhe non contengono solo lettere ASCII, ma anche simboli o spazi. Di frequente, il testo conterrà caratteri Unicode che non hanno equivalenti ASCII.

• Un codice hash è un numero intero. Per trovare un bucket, devi fare buckets.get(hashCode % buckets.size()) . Tuttavia, gli interi Java contengono 32 bit, che offrono abbastanza bit per circa 4,5 caratteri ASCII. Supponendo che la tua implementazione cambi a sinistra di sette bit e "o" s i nuovi bit al codice hash attuale,

  int hashCode = 0;
  for (char c : str) {
      hashCode <<= 7;
      hashCode |= c & 0x7F;
  }
  

  quindi solo gli ultimi 5 caratteri sarebbero significativi. Ciò semplifica la creazione di collisioni hash: civilisation e train station .

  Questo può essere evitato con una funzione hash più intelligente in cui qualsiasi bit rimarrà in qualche modo significativo. E. i bit nel codice hash potrebbero essere ruotati anziché spostati, e i nuovi bit potrebbero essere "xor" ed al valore esistente:

  int hashCode = 0;
  for (char c : str) {
      // rotate the bits
      hashCode = (hashCode << 1) | (hashCode >> (32 - 1));
      // xor new bits
      hashCode ^= c;
  }
  

  Java utilizza un funzione hash leggermente diversa :

  for (char c : str) {
      hashCode = 31 * hashCode + c;
  }
  

  La moltiplicazione con 31 assicura che tutti i bit vengano infine utilizzati senza rendere irrilevante alcun bit. L'overflow non è un problema a causa dell'operazione modulo quando si determina un bucket. Il valore di 31 è in gran parte irrilevante, ma essendo un numero primo evita le collisioni di hash.

L'uso dei codici ASCII di una stringa non è in realtà un metodo errato per l'hashing di un valore.

Le singole lettere non sono ugualmente comuni - e è più comune di g, e g è molto più comune di x, quindi i bucket diventerebbero in qualche modo sbilanciati, ma prendendo una somma MOD 26 su diverse lettere funzionerà molto meglio, perché le lettere rare e comuni si combinano in modo che tutti i valori compresi tra 0 e 26 si verifichino molto.

Il problema è che il controllo di ogni lettera in una stringa richiede molto tempo. Questo è il motivo per cui il codice di produzione di solito utilizza operazioni matematiche come la divisione su campi e costanti accuratamente selezionati che sono già numerici e equidistribuiti. Ma per imparare a programmare una tabella hash, vai avanti e usa i codici lettera.