Cette question m'a été posée dans une interview. Je pense que le seul moyen d'obtenir la meilleure solution est le SOF. La question était donc "
8 Réponses :
Réponse courte:
Ce serait une gamme de tableaux (ou de listes). où Lorsque vous insérez quelque chose que vous avez besoin d'une fonction pour calculer BOOM fait! :) mappe [beketIdex] retournerait le "godet". BucketIndex Cela utiliserait l'utilisation de l'objet inséré.
Merci willcodejavaforfood :). Vous ne pouvez pas utiliser le hashcode par défaut de l'objet au lieu de BucketIndex?
@ T3CH - Vous voulez probablement que une gamme de hashcodes soit insérée dans un seau. Sinon, vous vous retrouveriez presque avec une gamme d'objets, à l'exception des rares occasions où des hachons sont dupliqués. Comme je l'ai dit, c'est la courte réponse facile, je parie que l'article wiki que quelqu'un posté sur est beaucoup plus élaboré :)
Cela exclut l'adressage ouvert. Bien que ce ne soit pas la mise en œuvre la plus populaire, si je discutais dans une interview, je tiens à cela.
Je suis proposé la même solution lorsqu'on lui a demandé de mettre en œuvre Hashmap en interview! ... cela me donne un sentiment de satisfaction :)
Regardez sur Cliff Click's NONBLOCKINGHAHMAP Pour un exemple de besoin d'un hashmap implémenté dans Java. N'oubliez pas qu'un tableau associé n'est qu'un autre nom pour une carte de hachage, il vous demande donc comment la mettre en œuvre.
Les hachages généralement sont implémentées à l'aide de tableaux standard (pas de listes ou de fantaisie pour la vitesse). Le problème est ce qui se trouve à l'intérieur de chacun de ces tableaux ... dans le cas d'une collision de hachage, souhaitez-vous utiliser une liste linité (chaînage) ou souhaitez-vous rééverser et aller à un autre emplacement de matrice (adresse ouverte). Lisez une autre science informatique pour apprendre le coût / avantage à faire les deux.
Vous devez utiliser une matrice unidimensionnelle. Objet [] arr.
L'index du tableau est le casque normalisé de l'objet clé. Le tableau contient la paire.
La raison en sorte que la valeur consiste en une clé et de la valeur, c'est que s'il y a une collision de hachage, elle doit aller à travers la liste des touches de l'emplacement et savoir quelle est la touche correcte (à l'aide d'un élément égal sur l'objet clé) .
Si vous avez un tableau unidimensionnel d'objets, où mettez-vous les objets dont les hachons les ont mis au même endroit dans la matrice unidimensionnelle d'objets?
public class ArrayAsHashMap {
Object [][] hashArr = new Object [10] [2];
public void put(HashObject key, String value){
int index = key.hashCode();
Object [] arr = {key, value};
hashArr[index] = arr;
}
public String get(HashObject key){
int index = key.hashCode();
Object [] arr = hashArr[index];
return (String)arr[1];
}
}
Ajout d'une approche supplémentaire de plus - Que diriez-nous si nous utilisons le jeu au lieu de HASHMAP de cette manière
Créer une classe personnalisée appelée paire - p>
public static void main(String[] args) {
Set<Pair> set = new HashSet<Pair>();
set.add(new Pair("key1", "val1"));
set.add(new Pair("key2", "val2"));
set.add(new Pair("key1", "val3"));
// you can advanced for loop for looping over set
for (Pair pair : set) {
}
// with java 8 - you can also use streams over it
// set.stream().filter
// set.stream().anyMatch
// and some more methods can be directly used
}
Chaque fois qu'il n'y a pas de valeur présente à un index particulier, nous placerons directement l'objet de saisie à cet indice. Sinon, nous traverserons la liaison LinkedList jusqu'à ce que nous atteindrons la dernière entrée de la liste et placerons le nouvel objet de saisie en tant que nœud suivant du dernier objet de saisie. Dans le processus, si nous trouvons la clé existe déjà, nous remplacons simplement sa valeur avec le nouveau.
public void put(K key, V value){
int index = index(key);
Entry newEntry = new Entry(key, value, null);
if(table[index] == null){
table[index] = newEntry;
}else {
Entry previousNode = null;
Entry currentNode = table[index];
while(currentNode != null){
if(currentNode.getKey().equals(key)){
currentNode.setValue(value);
break;
}
previousNode = currentNode;
currentNode = currentNode.getNext();
}
if(previousNode != null)
previousNode.setNext(newEntry);
}
}
Govind 1 Sandeep 4 Abhishek 3 Vikas 10
Cela devrait aider - en.wikipedia.org/wiki/hash_table :)
Ceci est une question classique des devoirs. Voici un article sur la construction d'un hashmap: ibm.com/developerworks/java / Bibliothèque / J-JTP08223
Cela devrait également aider: codecramp.com/how-to-implement-votre- propre-hashmap