write a hash table

Écrivez une table de hachage en C

Les tables de hachage sont l'une des structures de données les plus utiles. Leur insert rapide et évolutif, leur recherche et leur suppression les rendent pertinents pour un grand nombre de problèmes d'informatique.

Dans ce didacticiel, nous mettons en œuvre une table de hachage à double hachage à double coincer dans C. En travaillant sur ce tutoriel, vous gagnerez:

• Comprendre comment une structure de données fondamentale fonctionne sous le capot
• Une connaissance plus approfondie du moment d'utiliser des tables de hachage, quand ne pas les utiliser, et comment ils peuvent échouer
• Exposition au nouveau code C

C est une grande langue pour écrire une table de hachage parce que:

• La langue ne vient pas avec une
• C'est un langage de bas niveau, vous êtes donc plus approfondi à la façon dont les choses fonctionnent au niveau de la machine

Ce tutoriel suppose une certaine familiarité avec la programmation et la syntaxe C. Le code lui-même est relativement simple et la plupart des problèmes devraient être résolubles avec une recherche Web. Si vous rencontrez d'autres problèmes, veuillez ouvrir un problème GitHub.

L'implémentation complète est d'environ 200 lignes de code et devrait prendre environ une heure ou deux pour travailler.

Contenu

1. Introduction
2. Structure de la table de hachage
3. Fonctions de hachage
4. Gérer les collisions
5. Méthodes de table de hachage
6. Tables de redimensionnement
7. Annexe: Manipulation alternative des collisions

Crédits

Ce tutoriel a été écrit par James Routley, qui blogue sur Routley.io.