Comment faire une clé ont plusieurs valeurs dans une table de hachage?

Question

J'ai 100 entrées et je dois les hacher dans une hashtable de taille limitée.

Je sais comment travailler avec la première entrée, ht.put(k,v) fait l'affaire.

Mais dès que je veux ajouter une autre valeur, l'ancienne est écrasée. Je ne veux pas faire cela, je veux l'ajouter dans une liste liée ou un arraylist.

Hashtable<Integer,Integer> ht = new Hashtable<Integer,Integer>(211); 

ht.put(1, 40); 
ht.put (1, 60); 

System.out.println(ht.get(1)); 
// output is 60 

Comment faire à la fois 40 et 60?

Answer 1

Vous utilisez la même clé (1), ce qui n'est pas ce que vous vouliez, sauf si vous vouliez ajouter plus de valeurs à la même clé, dans ce cas avez la table de hachage HashMap<Integer,List<Integer>> integerArrayMap.

Dans Hashtable, la clé DOIT être unique, car vous n'utilisez PAS de clés uniques, la même valeur est en cours de remplacement. alors essayez de mettre les valeurs avec des clés différentes.

ht.put(1, 40); 
ht.put (2, 60); 

Je vous suggère de renvoyer l'api Hashtable ici: https://docs.oracle.com/javase/7/docs/api/java/util/Hashtable.html

Answer 2

Vous avez besoin linéaire sondage http://www.sanfoundry.com/java-program-implement-hash-tables-linear-probing/

Il est impossible de stocker plus d'une valeur dans une cellule d'une table de hachage

Lorsque vous tentez de mapper une nouvelle clé sur une cellule déjà occupée, cela s'appelle une collision.

Il y a quelques schémas d'algorithme pour tenter de travail autour de la collision, l'un est le sondage linéaire - qui trouve le prochain espace libre le plus approprié pour la clé à stocker

Answer 3

Vous pouvez avoir la liste en tant que type de valeur comme:

Hashtable<Integer,List<Integer>> ht = new Hashtable<Integer,List<Integer>>(211); 

Et votre opération de vente ressemblerait à ceci:

public static void put(Hashtable<Integer,List<Integer>> ht, int key, int value) { 
    List<Integer> list = ht.get(key); 
    if (list == null) { 
     list = new ArrayList<Integer>(); 
     ht.put(key, list); 
    } 
    list.add(value); 
} 

[Update1] Si vous voulez, vous pouvez faire de votre extensomètres ion de Hashtable comme:

public class MyHashtable extends Hashtable<Integer,List<Integer>> { 
    public MyHashtable(...) { // add params if needed 
     super(...); 
    } 

    // with additional method: 
    public static void putOne(int key, int value) { 
     List<Integer> list = this.get(key); 
     if (list == null) { 
      list = new ArrayList<Integer>(); 
      this.put(key, list); 
     } 
     list.add(value); 
    } 
} 

Answer 4

La structure de données que vous recherchez est appelé multi carte. Par définition, il a une interface différente de celle d'une carte, car elle autorise plusieurs valeurs associées à la même clé.

Il n'existe pas encore d'implémentation de bibliothèque standard pour cette structure de données. Mais vous pouvez trouver bons dans certaines bibliothèques open source:

• Guava
• Apache Commons Collections

Answer 5

Multimap (https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/Multimap.html) devrait vous aider si vous êtes autorisé à l'utiliser. Vous pouvez également utiliser Map<Integer, List<Integer>>.