hozuki
commented
9 years ago @akaza-akari
感谢。现在的 Map 和 Set 都已经改用桶+链的实现了。
但是在遍历的时候会遍历整个作为桶的数组（Java 内部实现同样如此），桶的大小太大太小都不好；太大遍历时间长，太小链表（同样是数组）长度长。可以试试调整 BUCKETSIZE 参数观察所需时间。
正确性能保证了，速度下来了。现在的平衡点大概在 50 处，这和线条密度有很大关系。稀疏的时候 B-O 效率比朴素的高很多。您可以尝试一下测试中的一些参数组合。
我用 x * 2147483647 + y 的理由是这样的：
x 和 y 都可能为正/负/零。零的概率比较小。
实数轴被 ±2147483647 大约地分成了4个部分，分别对应x/y取正/负。考虑到 x 和 y（特别是 y，没乘的那个）不容易到 2147483647 这样的数量级，因此能将四种情况区分开，能同时放大 x 和 y 的差异。
BKDR hash 那里是我手误了，现在已经改为了 & 0x7fffffff。
当前（/Hozuki/xross@ed122dd067fc7a348683706a6211f0a37e45c57b），Map和Set的实现有几个问题：
在遇到碰撞时选择丢弃后来的元素，导致数据破坏。为了使这两个数据结构正常运作，此处的表现应为：将后来的元素并入同一个bin中，在get时进行线性搜索。任何只靠输入数据算来的Hash都是不完美的，不能以hashcode不冲突为前提写。
直接使用hashcode来分bin。现代浏览器会在内部用其他的数据结构，比如链表或者字典，来存储Array，因此稀松数组的性能非常糟糕。这个B-O实现在n大的时候反而表现更差，可能与此有关（如果V8为Array使用了O(n)查找的链表，那么Map/Set就不能做到标称的O(1)查找了，拖掉了整个的时间复杂度）。这两个Hash为基础的数据结构应该使用一个分配好的短而坚实的数组，通过mod来选择bin，从而提高性能。
一些链接： V8细节：http://www.smashingmagazine.com/2012/11/writing-fast-memory-efficient-javascript/#v8-optimization-tips Hashtable实现：http://algs4.cs.princeton.edu/34hash/
EDIT:
x * 2147483647 + y不好使应该是因为JS没有int，所有number都是double，没办法利用int的溢出特性来hash。EDIT2: 关于直接使用hashcode的追记，现在的
bkdrHash因为使用&运算符导致出负值，这也可能是造成Array底下被换成其他数据结构的一个因素。用>>> 0是可以把负数转换成对应的uint的。