Tableau hybride de Lua et table de hachage; existe-t-il ailleurs?

Question

L'implémentation de tables de Lua garde ses éléments en deux parties: une partie de tableau et une partie de hachage.

Une telle chose existe-t-elle dans d'autres langues?

Consultez la section 4, Tables, dans The Implementation of Lua 5.0.

Lua 5.1 Source Code - table.c

Answer 1

Cette idée était originale avec Roberto Ierusalimschy et le reste de l'équipe Lua.J'ai entendu Roberto en parler à l'atelier MIT Lightweight Languages ​​en 2003, et dans cet exposé, il a discuté des travaux antérieurs et a argumenté de manière convaincante que l'idée était nouvelle. Je ne sais pas si d'autres langues l'ont copié depuis.

L'Awk original a un modèle de langage un peu plus restreint que Lua; un nombre ou une chaîne peut être utilisé comme clé dans un tableau, mais les tableaux eux-mêmes ne sont pas des valeurs de première classe: un tableau doit avoir un nom et un tableau ne peut pas être utilisé comme clé dans le tableau. En ce qui concerne l'implémentation, j'ai vérifié les sources pour l'Awk original tel que maintenu par Brian Kernighan, et l'implémentation d'Awk utilise une table de hachage, pas la structure hybride tableau/table de Lua. La distinction est importante car dans Lua, lorsqu'une table est utilisée avec des clés entières consécutives, la surcharge de l'espace est la même que pour un tableau C. C'est pas vrai pour l'original Awk.

Je n'ai pas pris la peine d'étudier toutes les implémentations ultérieures de awk, par exemple, Gnu Awk, mawk, et ainsi de suite.

Answer 2

La chose la plus proche que je peux penser est Javascript - vous créez un tableau avec new Array(), puis passez à l'index soit par numéro ou par valeur de chaîne. Il se peut que pour des raisons de performances, certaines implémentations Javascript choisissent de le faire en utilisant deux tableaux, pour les raisons indiquées dans la documentation de Lua à laquelle vous avez lié.

Answer 3

EDIT: Cela ne répond pas à la question, qui concernait l'implémentation.

AWK l'a également fait.

C'est interesing comment certaines langues amalgament opérations qui sont différentes dans d'autres:

• Liste indexation - a[10]
• indexation Associatif - a['foo']
• Accès aux objets sur le terrain - a.foo
• Fonction/Appels de méthode - a('foo')/a.foo()

Des exemples très incomplets:

• Perl est la langue rare où l'indexation associative/séquentielle ont une syntaxe séparée - a[10]/a{'foo'}. AFAIK, les champs d'objets correspondent à l'une des autres opérations, selon ce que l'implémenteur de la classe a voulu utiliser.

• En Python, tous les 4 sont distincts; L'indexation séquentielle/associative utilise la même syntaxe, mais des types de données distincts leur sont optimisés.

• Dans Ruby, les champs d'objets sont des méthodes sans arguments - a.foo.

• En JavaScript, les champs d'objet a.foo sont syntaxe sucre pour l'indexation associative a['foo']. En Lua et AWK, les tableaux associatifs sont également utilisés pour l'indexation séquentielle - a[10].

• En Arc, l'indexation séquentielle et associative ressemble à des appels de fonctions - (a 10)/(a "foo"), et je pense que a.foo est le sucre syntaxe pour cela aussi (?).

Answer 4

ArrayWithHash est une implémentation rapide de l'hybride de table-hashtable en C++.

Puisque C++ est un langage typé statiquement, seules les clés entières sont autorisées dans ArrayWithHash (aucun moyen d'insérer une chaîne ou une clé de pointeur). En d'autres termes, c'est quelque chose comme un tableau avec sauvegarde de table de hachage pour les grands index. En outre, il utilise une implémentation de table de hachage différente qui est moins efficace en termes de mémoire que l'implémentation de la table Lua.