Comment faire pour implémenter une table de hachage à l'aide d'un Arbre de Recherche Binaire?
J'ai été en mesure de mettre à la table de hachage à l'aide du tableau en utilisant simplement la structure de données suivante.
LinkedList<Item<K,V>> table[]
const int MAX_SIZE = 100
je.e un tableau de liste chaînée(hachage avec chaînage).
Maintenant dans divers livres,ils disent que nous pouvons mettre en œuvre une table de hachage avec un BST si nous voulons données ordonnées.
Comment puis-je intégrer à la fois la clé et la valeur dans un BST. Bien que je peux stocker à la fois juste comme je stocker un seul élément de données, mais la clé donne un entier qui agit comme un indice de la matrice après qu'il a été à une fonction de hachage. Comment puis-je utiliser la clé dans le BST? Je n'ai pas besoin d'un indice?
Ce que je peux penser, c'est que je peux comparer les deux touches à l'aide de la fonction et ensuite faire normale de l'insertion,la suppression en conséquence.
MODIFICATIONS:
Supposons que j'ai un TBS à partir de zéro
class Node {
K key;
V value;
Node left;
Node right;
}
class BinarySearchTree {
Node root;
}
class Hashtable {
BinarySearchTree bst;
public void Hashtable() {
bst = new BinarySearchTree();
}
//hashfunction(K key)
//get(K Key)
//put(K key,V value)
//remove(K key)
}
Comment puis-je utiliser la clé mappé en entier pour mettre en œuvre les
insert(V value)
dans BST.
OriginalL'auteur Hooli | 2013-06-24
Vous devez vous connecter pour publier un commentaire.
Java des réponses ont déjà été fournis, mais je devine votre question est plus sur la conception plutôt que de langage spécifiques de mise en œuvre.
Non, nous n'avons pas besoin de calculer un index ou d'utiliser une fonction de hachage. Si nous conservons la clé,des paires de valeurs dans les nœuds de la bst, alors c'est juste une question de parcours de l'arbre en comparant les touches. Cela vous donne également l'avantage de pas de collisions puisque les clés sont uniques.
Vous pouvez utiliser une fonction de hachage et de hachage de la clé, puis parcourir l'arbre en fonction de cette valeur, mais cela peut conduire à des collisions si vous n'êtes pas prudent avec la fonction de hachage et alors que vous auriez à maintenir une sorte de chaînage.
Si l'utilisation de la clé ou la valeur de hachage de la clé dépend de la taille de la clé. Si la taille de la clé est grande, il est logique de hachage à une plus petite taille pour plus rapide comparaison.
OriginalL'auteur pmathew
Il y a déjà une mise en œuvre de la STB en java - TreeMap. C'est un équilibrage automatique rouge-noir arbre. Je suppose que la mise en œuvre, il ne serait pas beaucoup de problème. Par exemple:
Depuis la table de hachage doit être mise en œuvre de
Map
interface, je suggère la mise en œuvre dejava.util.Map
. Je voudrais utiliser un BST au travers de la composition plutôt que l'héritage - donc on peut cacher l'API de la BST. Le BST peut être n'importe quoi - dans mon exemple de code que j'ai utilisé de JavaTreeMap
classe.Oui, j'ai été en espérant pour la mettre en œuvre. Je sais que sur SortedMap en Java.
Comment est-ce code est-il pertinent? Expliquer. (5 points)
J'ai lu hashset au lieu de la table de hachage. J'ai édité le code...
Comme par JDK, Dictionnaire de la classe est obsolète. Nous devrions plutôt mettre en œuvre la Carte d'interface tout en mettant en œuvre une coutume HashMap.
OriginalL'auteur darijan
Vous n'avez pas besoin de mettre en œuvre la table de hachage avec une liste de liens.
C'est uniquement le cas lorsque la collision se produit, au lieu d'utiliser le chaînage qui prend le temps linéaire de la recherche O(n) , vous pouvez utiliser l'équilibre de la stb, de sorte que le temps de recherche est réduit à O(log n).
OriginalL'auteur Vishal
Ici est une simple mise en œuvre de la table de hachage avec la BST, comme des seaux. Sur cette base, la mise en œuvre de la Carte montre comment mettre des() et get() fonctionne pour obtenir des données de la Carte soutenu par BST seaux. Cette BST mise en œuvre n'est PAS équilibré. Idéal pour les applications de production, ce BST doit être équilibrée à l'aide de Rouge-Noir algorithme d'arbre à améliorer le temps de recherche.
Avec des seaux mis en œuvre à l'aide équilibré BST par rapport à des Listes Liées, nous sommes en mesure d'améliorer Get(clé) temps de O(n) à O(log n).
Le code complet se trouve ici: https://github.com/prabhash1785/DataStructures/blob/d842d07e1fc3bf7e1caed72eb6b0744a719a9bc6/src/com/prabhash/java/algorithms/datastructures/HashMapWithBST.java
hash = hash >>> 16; // Spread the higher bits
Ne sera pas essentiellement à zéro, tout nombre inférieur à environ 100 000?OriginalL'auteur Prabhash Rathore