一个语言的诞生（Act I）

第一幕 哈希表

哈希表是动态脚本语言的基石。动态语言中，全局变量表、全局字符串表、对象虚函数表、元数据表皆为哈希表。欲实现语言，则必先实现哈希表。

哈希表原理很简单，不再赘述。不同语言实现的哈希表主要区别在于处理碰撞的机制不同。一种叫“Separate chaining”，PHP的哈希表使用了这种方式；另一种叫“Open addressing”，Lua的哈希表使用的是这种。前者发生碰撞会创建一个新的bucket，然后用链表将所有碰撞的bucket链接起来；而后者在现有的buckets中找到一个空的bucket来存放发生碰撞的key-value pair。我选择的是后一种方式，一方面是节约内存，另一方面还能节省GC开销。

哈希表初始大小为8，也就是哈希表包含8个buckets。考虑到取余是一个比较耗CPU的操作，所以哈希表大小以2的指数倍增长，这样可以用位移的方式来取余。

key值可以是任何可哈希的对象，比如字符串、整数、浮点数、元组。本来觉得所有引用对象将地址作为哈希值也可以作为key，后来一想不对——因为GC采用的是Mark-Compact算法，每次GC后对象的地址可能是不同的。考虑是不是要在对象数据结构里增加一个唯一ID域。

另外有个问题就是“hash collision DoS vulnerability”。就是恶意构造N多HASH值一样的字符串提交，把哈希表变成了链表。PHP的解决方案是限制用户提交参数的个数，Lua的解决方案是增加一个随机的seed。Lua的解决方案是最完美的，不过采用seed是有成本的，而且考虑到今后的RPC调用，想要hash复用就不行了。最后还是采用类型PHP的方案，接受用户外部数据的时候做下限制就可以了。

补充： 哈希表的键类型选择纠结了很久。一般来说，任何实现哈希表的语言中字符串类型或整型都可以作为key，而其他类型是否允许作为key就没有个统一标准了。比如C#对象有提供GetHashCode方法用于计算散列，所以字典的键支持所有的类型。Python和Lua中使用对象的内存地址作为哈希值。

再补充： 最后决定在Object头部添加一个hash值域。该值迟计算，当第一次请求获取对象哈希值时根据对象地址求得哈希值，之后该对象就一直使用该值，无论对象地址是否改变。