La création d'une table de hachage à partir de zéro?
Je suis en train d'écrire un programme qui permettra de hachage des mots à partir d'un document en même temps que la fréquence de leur utilisation et des numéros de ligne. J'ai pensé que je l'avais fini quand on m'a dit que vous devez créer une table de hachage à partir de zéro. Je ne sais pas par où commencer. Des suggestions quant à où et comment commencer serait appréciée.
- Est-ce un devoir?
- J'aimerais commencer ici: en.wikipedia.org/wiki/Hashtable
- Commencez avec un tableau et une fonction de hachage.
Vous devez vous connecter pour publier un commentaire.
Une table de hachage est une importante et fondamentale de la structure de données. Vous pouvez en lire plus à ce sujet à La page Wikipedia de la table de Hachage de l'article. Heureusement, ils sont assez faciles à mettre en œuvre.
Essentiellement d'une table de hachage est une structure de données qui prend une clé et retourne ou stocke une valeur de cette clé.
À leur base, ils sont généralement mis en œuvre à l'aide d'un tableau, que nous appellerons
arr
tels que des paires clé-valeur sont stockées àarr[key.hashCode()%arr.length]
. Notez que depuis votre tableau n'est pas de longueur infinie, et quehashCode
n'est pas garanti pour produire des valeurs uniques, vous finirez par retrouver avec des clés de cette carte pour le même indice de la matrice. Ceci est appelé un collision.Un moyen de résoudre ces collisions est de stocker une liste, pour chaque membre de
arr
. Alors, la définition dearr
ressemblerait à ceciTous les objets qui correspondent à
arr[key.hashCode()%arr.length]
sera ajouté à la liste à cette position. Lorsque vous souhaitez récupérer un objet à partir de la table de hachage, de sauter de la liste chaînée trouvé àarr[key.hashCode()%arr.length]
et itérer sur chaque membre de la liste, jusqu'à ce que vous trouver une paire clé-valeur, où les clés sont.equals
.Une bonne table de hachage de la mise en œuvre pourrait faire des choses comme redimensionner
arr
une fois qu'il est trop plein.Pour créer une table de hachage, Vous devez garder à l'esprit la structure de ce qu'il est que vous voulez construire. Une table de hachage a 2 éléments, un jeu de clé et une valeur définie. Pensez à comment vous représenter ces et comment vous assurez-vous que les touches toujours la carte à la valeur appropriée.
Prochaine, pensez à votre fonction de hachage. Rappelez-vous qu'Il n'y a pas de "bonne" fonction de hachage. Vous avez juste besoin de trouver un qui fonctionne bien pour vous.
Une fois ces deux choses sont prises en charge, le reste est simple. Méthodes d'écriture de travailler sur les deux ensembles sont fondamentalement juste une question de habilement à l'aide de la fonction de hachage.
Bonne Chance!
Supplémentaire astuce: n'oubliez pas que la valeur de l'ensemble de la table de hachage n'est pas nécessairement de la même taille que l'ensemble des clés. Rappelez-vous le concept de seaux. C'est très important.
Commencer avec l'étude de la HashMap classe Java. Notez que c'est une extension de la AbstractMap, et que AbstractMap fournit un grand nombre de fonctionnalités de base que vous voulez. Pas tous, cependant. La méthode la plus importante, put(), jette toujours UnsupportedOperationException. C'est par la conception. Pour en faire un MyHashMap, vous avez besoin de redéfinir cette méthode. À l'intérieur de put() seront à l'endroit où vous allez faire tout votre hashy choses visées à Jack est super réponse.
En le faisant de cette façon, vous pouvez tester votre mise en œuvre plus facilement. Exécuter une série de tests dans lesquels vous fournir une HashMap en tant que paramètre. Puis exécuter le même code avec un objet de votre MyHashMap. Puisque les deux sont des implémentations de Carte, vous pouvez substituer l'un à l'autre sans changer le code, et vous serez confiant sur ce que vos tests sont de vous dire.
Suffit d'utiliser un tableau pour votre table. Vous aurez besoin d'une fonction de hachage, et un facteur de charge. Le facteur de charge permettra de déterminer si vous redimensionnez la table pour conserver l'efficacité. Une simple fonction de hachage pour une chaîne de caractères est de faire la somme de chaque caractère ascii de la valeur multipliée par 2^(caractère d'index) et un mod le montant de cette somme par la longueur de la table. par exemple,
Vous pouvez utiliser
String.hashCode
trop. Pour résoudre les collisions de la méthode la plus simple est linéaire de sondage, mais de clustering va se produire rapidement. Vous pouvez mettre en œuvre double hachage pour de meilleures performances.