Techniques simples de la fonction de hachage

Question

Je suis assez novice dans le hachage en Java et je me suis retrouvé bloqué sur certaines parties. J'ai une liste de 400 articles (et stockés dans une liste de 1.5x = 600), dont l'identifiant de l'article varie de 1-10k. J'ai regardé quelques fonctions de hachage et j'ai d'abord copié les exemples dans le paquet, qui a juste utilisé le pliage. J'ai remarqué que j'avais 50-60% de nœuds nuls, ce qui est apparemment trop. J'ai également remarqué que juste modding l'ID par 600 tend à le réduire à un solide 50% de null.

Ma fonction de hachage actuelle ressemble, et d'être aussi laid que ce soit, il est seulement une diminution de 1% en nulls d'un modding simple, avec une longueur de la liste avg de 1,32 ...

public int getHash(int id) 
    { 
     int hash = id; 

     hash <<= id % 3; 
     hash += id << hash % 5; 

     /* let's go digit by digit! */   
     int digit; 
     for(digit = id % 10; 
      id != 0; 
      digit = id % 10, id /= 10) 
     { 
     if (digit == 0) /* prevent division by zero */ 
      continue; 
     hash += digit * 2; 
     } 

     hash >>= 5; 
     return (hash % 600); 
    } 

Quelles sont les bonnes techniques pour créer simples fonctions de hachage?

Answer 1

Je le garderais simple. Renvoyez le id de votre élément comme code de hachage, et laissez la hashtable s'inquiéter de le ressasser s'il le juge nécessaire. Votre but devrait être de créer un code de hachage unique à votre objet.

Java HashMap utilise la méthode rabâcher suivante:

/** 
* Applies a supplemental hash function to a given hashCode, which 
* defends against poor quality hash functions. This is critical 
* because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0. 
*/ 
static int hash(int h) { 
    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

Answer 2

Il ya un article de revue agréable here. En outre, le Wikipedia article on hash functions est un bon aperçu. Il suggère d'utiliser un test du chi carré pour évaluer la qualité de votre fonction de hachage.