Lua的混合数组和哈希表，是否在其他地方存在？

Question

Lua的表实现将其元素分为两部分：数组部分和哈希部分。

其他编程语言中是否存在类似的实现？

请查看Lua 5.0的实现中的第4节“表”。 Lua 5.1源代码 - table.c

- Rudiger

Answer 1

这个想法最初由Roberto Ierusalimschy和Lua团队提出。我听说过Roberto在2003年的MIT轻量级语言研讨会上发表了有关此想法的演讲，在这次演讲中，他讨论了先前的工作，并有力地证明了这个想法是新颖的。我不知道其他编程语言是否在此后也采用了该想法。

与Lua相比，原始的Awk具有更为受限的语言模型；在数组中，只能使用数字或字符串作为键，但数组本身不是一级值：数组必须有一个名称，并且数组不能被用作数组中的键。

关于实现，我已经检查了由Brian Kernighan维护的原始Awk源代码，并且Awk的实现使用哈希表，而不是Lua的混合数组/表结构。这种区别很重要，因为在Lua中，当一个表与连续的整数键一起使用时，空间开销与C数组相同。然而，这在原始的Awk中并不成立。

我没有去调查所有后来的awk实现，例如Gnu Awk、mawk等。

- Norman Ramsey

Answer 2

编辑：这并没有回答问题，问题是关于实现的。

AWK 也可以做到。

有趣的是一些语言将在其他语言中不同的操作混为一谈：

• 列表索引 - a[10]
• 关联索引 - a['foo']
• 对象字段访问 - a.foo
• 函数/方法调用 - a('foo') / a.foo()

非常不完整的例子：

• Perl 是罕见的语言，其中顺序/关联索引具有不同的语法 - a[10] / a{'foo'}。据我所知，对象字段映射到另一个操作之一，具体取决于类的实现者想使用哪个操作。

• 在 Python 中，所有四个操作都是不同的；顺序/关联索引使用相同的语法，但单独的数据类型针对它们进行了优化。

• 在 Ruby 中，对象字段是没有参数的方法 - a.foo。

• 在 JavaScript 中，对象字段 a.foo 是关联索引 a['foo'] 的语法糖。

• 在 Lua 和 AWK 中，关联数组也用于顺序索引 - a[10]。

• 在 Arc 中，顺序和关联索引看起来像函数调用 - (a 10) / (a "foo")，我认为 a.foo 也是这个的语法糖（？）。

- Beni Cherniavsky-Paskin

---

Fortress和Clojure也将映射视为其键的函数，将数组视为其索引的函数。毕竟，它们本质上就是这样。 - Jörg W Mittag

问题是关于实现，而不是语言模型。原始的awk仍由Brian Kernighan维护，使用哈希表。 - Norman Ramsey

你说得对，我完全错了！不能给自己点踩，所以给你的回答点个赞。 - Beni Cherniavsky-Paskin

Answer 3

我能想到的最接近的东西是Javascript - 你可以用new Array()创建一个数组，然后可以通过数字或字符串值进行索引。出于性能原因，一些Javascript实现可能会选择使用两个数组来完成这个操作，和你提供的Lua文档中所述的原因类似。

- Kendall Helmstetter Gelner

Answer 4

ArrayWithHash 是 C++ 中一个快速的数组哈希表混合实现。

由于 C++ 是一种静态类型语言，因此 ArrayWithHash 只允许使用整数键（无法插入字符串或指针键）。换句话说，它类似于具有哈希表备份的大索引数组。此外，它使用不同的哈希表实现，比 Lua 表实现更少的内存效率。

- stgatilov