De quelle structure de données s'agit-il?

Question

Quel est le nom de la structure de données, s'il en existe une, comportant les opérations ci-dessous?

• Vous pouvez insérer un élément et une clé vous est donnée.
• Vous pouvez récupérer un élément par sa clé.

Answer 1

Allocateur de mémoire

Vous allouez (insérez) un élément, et avec une clé (pointeur, référence, etc.), vous pouvez récupérer l'élément (y accéder) par la référence du pointeur.

Answer 2

C'est (assez proche) une table des symboles, dans le Lisp sens (à noter que le membre de phrase "de la table des symboles" peut aussi désigner différentes, mais liées à des structures de données). Une table des symboles est une association de touches appelées symboles de valeurs appelées liaisons (ou de fentes ou d'un autre terme).

Le fonctionnement de l'enregistrement d'une nouvelle clé appelée gensym. Lisp symboles de toujours avoir un nom unique, qui est une chaîne de caractères; gensym renvoie un nom qui n'est pas utilisé par n'importe quel symbole. Lisp prend également en charge de la recherche d'un symbole par nom: intern renvoie un symbole donné son nom, et crée le symbole si pas présent; certaines implémentations de fournir de l' intern-soft afin d'éviter la création d'un symbole si il n'y a aucun de ce nom. Étant donné un symbole, vous pouvez récupérer la valeur associée symbol-value.

Si vous ne savez pas Lisp, pense de symboles de variables; gensym crée une nouvelle variable, et symbol-value renvoie la valeur de la variable désignée par la référence. Ces opérations sont particulièrement utiles lors de l'écriture de macros (métaprogrammation), qui Lisp supporte très bien. Moderne Lisp implémentations ont "uninterned des symboles", c'est à dire des symboles qui ne sont pas dans une table, ce qui rend les choses plus propre. Ce n'est pas pertinent pour la structure de données que vous avez en tête (uninterned symboles devaient être des choses qui ne sont pas dans votre structure de données).

Une table des symboles est facilement mis en œuvre sur une carte (dictionnaire) de l'interface (qui est usueally mis en œuvre avec une table de hachage ou de l'équilibre de l'arbre). Gensym est de trouver une nouvelle clé, de le créer et de le retourner. Recherche est l'habitude de la carte de recherche. Si tous vos clés sont créées par gensym, le type de clé peut rester abstraite.

Answer 3

Je ne suis pas sûr de son nom, mais il est implémenté dans les systèmes de contrôle de version. Par exemple, le magasin Git a ce type de données: vous stockez un blob dans celui-ci et obtenez une clé, qui est son hachage SHA-1. Plus tard, vous pourrez récupérer votre blob en utilisant cette clé.

Je pense que certains systèmes de fichiers pourraient aussi fonctionner de cette façon.

Je pourrais l'appeler un "magasin de valeur anonyme".

Answer 4

Cela ressemble à une table de hachage / dictionnaire, bien que la clé soit connue plutôt que donnée.

Answer 5

Dans l'espace des "solutions de stockage d'entreprise" (ou autre), on parle souvent de stockage adressable par le contenu, en supposant que la clé elle-même dérive (par exemple, du hachage cryptographique) du contenu que vous y insérez, mais dans la plupart des cas simplement un détail de mise en œuvre.