Comment stocker une table de hachage dans un fichier?

Question

Comment puis-je stocker une table de hachage avec chaînage séparé dans un fichier sur le disque?

Génération des données stockées dans la table de hachage lors de l'exécution est cher, il serait plus rapide à charger juste le HT à partir du disque ... si seulement je peux comprendre comment le faire.

Edit: Les recherches sont effectuées avec le HT chargé en mémoire. Je dois trouver un moyen de stocker la table de hachage (en mémoire) à un fichier dans un format binaire. Alors que la prochaine fois que le programme fonctionne, il peut simplement charger le disque dans HT hors RAM.

J'utilise C ++.

Answer 1

Quelle langue utilisez-vous? La méthode courante consiste à faire une sorte sérialisation binaire.

Ok, je vois que vous avez modifié pour ajouter la langue. C ++ il quelques options. Je crois que le mécanisme de sérialisation Boost est assez bonne. De plus, la page de la bibliothèque de sérialisation Boost décrit également des solutions de rechange. Voici le lien:

http://www.boost.org/ doc / libs / 1_37_0 / libs / sérialisation / doc / index.html

Answer 2

En supposant que C / C ++: Utilisation index de tableau et la taille fixe structs au lieu des pointeurs et des allocations de longueur variable. Vous devriez pouvoir écrire directement () les structures de données dans un fichier pour lire plus tard ING ().

Pour tout niveau supérieur: Beaucoup d'API linguistiques plus élevées ont des installations de sérialisation. Java et Qt / C ++ les deux ont des méthodes qui vont arriver immédiatement à l'esprit, donc je sais que d'autres font aussi.

Answer 3

Vous pouvez simplement écrire toute la structure de données directement sur le disque en utilisant la sérialisation (par exemple en Java ). Cependant, vous pourriez être obligé de lire tout l'objet de nouveau dans la mémoire afin d'accéder à ses éléments. Si cela est pratique, vous pourriez alors envisager d'utiliser un fichier pour stocker les éléments de la table de hachage. Au lieu d'utiliser un pointeur pour représenter l'élément suivant de la chaîne, vous suffit d'utiliser la position d'octet dans le fichier.

Answer 4

Laissez tomber les pointeurs pour les indices.

est un peu similaire à la construction d'un sur disque , que je l'ai fait un certain temps retour. Ce qui a fait que si très doux était qu'il pourrait être chargé directement avec mmap lecture au lieu du fichier. Si l'espace de hachage est gérable, disons 2 ¹⁶ ou 2 ²⁴ entrées, alors je pense que je ferais quelque chose comme ceci:

• Gardez une liste d'indices gratuits. (Si le tableau est vide, chaque chaîne d'indice rappelle à l'index suivant.)
• Lorsque enchaînant est nécessaire d'utiliser l'espace libre dans la table.
• Si vous avez besoin de mettre quelque chose dans un index qui est occupé par un squatteur (débordement d'ailleurs):
  • enregistrement de l'indice (appelons-le N)
  • échanger le nouvel élément et le squatter
  • mettre le squatter dans un nouvel indice libre (F).
  • suivre la chaîne sur l'indice de hachage du squatter, pour remplacer N par F.
• Si vous exécutez complètement hors d'indices libres, vous avez probablement besoin d'une plus grande table, mais vous pouvez faire face un peu plus longtemps en utilisant mremap pour créer une pièce supplémentaire après la table.

Cela devrait vous permettre de mmap et d'utiliser directement la table, sans modification. (Effrayant si rapide dans le cache du système d'exploitation!), Mais vous devez travailler avec des indices plutôt que des pointeurs. Il est assez effrayant d'avoir méga-octets disponibles dans syscall-aller-retour en temps et ont encore moins de prendre que dans la mémoire physique, à cause de la pagination.

Answer 5

Peut-être DBM pourrait être utile pour vous.

Answer 6

Si votre implémentation de table de hachage est une bonne, puis juste stocker le hachage et les données de chaque objet - mettre un objet dans la table ne doit pas être cher étant donné le hachage, et non sérialisation la table ou la chaîne vous permet directement variez exactement la mise en œuvre entre les sauvegarder et charger.