Utiliser une table de hachage pour créer un tableau illimité

Question

Je développe actuellement un langage de programmation en C, et je veux permettre aux utilisateurs de créer des tableaux apparemment "illimités" avec des indices numériques sans sacrifier les performances dans le processus. Par exemple, table [1000000000] serait idéalement créable et accessible en un instant sans la surcharge de mémoire d'une table de 1.000.000.000 d'articles, dont 999.999.999 étaient inutilisés; mais le tableau fonctionnerait également bien lorsque table [n] a été défini pour, disons, 1 ≤ n ≤ 1000000.

Avez-vous des suggestions pour la mise en œuvre d'un tel système de gestion de réseau?

Answer 1

Vous créez un Sparse Array, comme l'article de Wikipedia mentionne, ceux-ci peuvent être représenté par une liste chaînée

Chaque noeud de la liste chaînée peut être un tableau alloué dynamiquement de sorte que vous ne subissez pas de surcharge excessive pour les index consécutifs.

Answer 2

Je pense que vous avez répondu vous-même. Jetez un oeil à CMPH - C Minimal Perfect Hashing Library.

EDIT:

Ou vous pouvez utiliser un B+ Tree pour cartographier l'entier à l'indice réel dans le tableau. L'utilisation de B Trees a un autre avantage: vous pouvez effectuer des requêtes de plage.

Answer 3

Que diriez-vous pointeur à l'aide, vous ne devez pas définir le nombre d'éléments pour, vous pouvez ajouter autant d'éléments que vous voulez

Answer 4

Théoriquement, je pense que c'est possible. Ce dont vous avez besoin est un très bon algorithme de hachage (pour éviter les collisions). Donc, si quelqu'un dit table [100..0]; vous n'avez pas besoin d'allouer l'espace à la fois. Allouer de l'espace selon les besoins. Donc, si dans la table [100..0] j'essaie de remplir les 5 premières valeurs, alors je vais stocker ces cinq valeurs seulement et si j'essaie d'accéder à disons la table [100] alors je devrais obtenir quelque chose comme 'undef' ou 'néant' ....

la bibliothèque mentionnée par the_void semble bien ... mais je ne l'ai pas testé ... :)

Answer 5

Il y a des tableaux Judy http://judy.sourceforge.net/

Answer 6

l'utilisation cmph ne sera pas Aidez-moi. Vous devez connaître toutes les clés à l'avance pour créer une fonction de hachage parfaite (minimale).

Ce que vous voulez est une structure de mappage associatif simple qui vous permettra d'implémenter un tableau fragmenté. Toute table de hachage ou structure arborescente fera l'affaire. Vous pouvez utiliser hash_map ou map out of the box à partir de votre implémentation C++ stl ou de toute structure de données similaire. Si vous voulez vous faire plaisir, vous pouvez utiliser Judy Arrays, mais je doute que cela fasse une différence, à moins que vous ne puissiez évaluer correctement des choses et que vous soyez prêt à considérer des structures de données plus complexes qui feront des hypothèses sur votre cas particulier .

Faites la chose simple. La table de hachage la plus facile à votre disposition est la meilleure réponse. Ne vous embêtez même pas à penser à des fonctions de hachage ou autres, tout ce que votre plate-forme fournit fonctionnera assez bien.