JavaScript中Set，Map和Object的区别

发表于 更新于 分类于 Waline：

最近在阅读《Web高效编程与实践优化》的计算机基础一节，看到他讲了JS中Set和Map的区别，以及Object的实现，算是解决了往常的一点疑惑吧，这里简单总结下：

Set

Set一般是使用红黑树实现的，红黑树是一种平衡查找二叉树，它的查找时间复杂度为O（logN）。实际上，Chrome V8的Set是用哈希实现的，它是一个哈希Set

假设我们有这样一段代码：

1
2
3
4
5
6
var set = new Set(); 
//数据为20个数 
var data = [3, 62, 38, 42, 14, 4, 14, 33, 56, 20, 21, 63, 49, 41, 10, 14, 24, 59, 49, 29]; 
for(var i = 0; i < data.length; i++){ 
    set.add(data[i]); 
}

哈希的一个关键的地方是哈希算法，即对一堆数或者字符串做哈希运算得到它们的随机值

1
2
3
4
5
6
7
8
9
10
11
function ComputeIntegerHash(key, seed) { 
    var hash = key; 
    hash = hash ^ seed; //seed = 505553720 
    hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; 
    hash = hash ^ (hash >>> 12); 
    hash = hash + (hash << 2); 
    hash = hash ^ (hash >>> 4); 
    hash = (hash * 2057) | 0; // hash = (hash + (hash << 3)) + (hash << 11); 
    hash = hash ^ (hash >>> 16); 
    return hash & 0x3fffffff; 
}

把数字进行各种位运算，得到一个比较随机的数，然后对这个数进行散射散射的目的是得到这个数放在数组的哪个index。

1
2
3
4
5
6
var capacity = 64; 
var indexes = []; 
for(var i = 0; i < data.length; i++){ 
    indexes.push(ComputeIntegerHash(data[i], seed)  & (capacity - 1)); //去掉高位 
} 
console.log(indexes)

有20个数，容量capacity从16开始增长，每次扩大一倍，到64的时候，可以保证capacity>size*2，因为只有容量是实际存储大小的两倍时，散射结果重复值才能比较低。

现在要查找key=56是否存在这个Set里面，先把56进行哈希，然后散射，按照存放的时候同样的过程

1
2
3
4
5
function SetHas(key){ 
    var index = ComputeIntegerHash(56, seed) & this.capacity; 
    //可能会有重复值，所以需要验证命中的index所存放的key是相等的 
    return setArray[index] !== null  && setArray[index] === key; 
}

上面是哈希存储结构的一个典型实现，但是Chrome的V8的Set/Map 并不是这样实现的，略有不同。

哈希算法是一样的，但是散射的时候用来去掉高位的并不是用 capacity，而是用capacity的一半，叫做buckets的数量，这个去掉高位其实就是通过hash值和容量做一个按位与运算，效果等同于取余。

插入过程

假设我们依次插入9，33，68，57

Set的存储结构分成三部分，第一部分有3个元素，分别表示有效元素个数、被删除的个数、buckets的数量，前两个数相加就表示总的元素个数。

插入9之后，元素个数加1变成1，初始化的buckets数量为2。

第二部分对应buckets，buckets[0]表示第1个bucket所存放的原始数据的index，源码里面叫做entry，9在data这个数组里面 的index为0，所以它在bucket的存放值为0，并且bucket的散射值为0，所以bucket[0]=0。

第三部分是记录key值的空间，9的entry为0，所以它放在了3+buckets.length+entry*2=5的位置，每个key值都有两个元素空 间，第一个存放key值，第二个是keyChain，它的作用下面将提到

插入33之后

插入68，68的bucket值也为1，和33重复了，因为entry=buckets[1]=1，不为 空，说明之前已经存过了，entry为1指向的数组的位置为 3+buckets.length+entry*2=7，也就是说之前的那个数是放在数组7的位 置，所以68的相邻元素存放值keyChain为7，同时bucket[1]变成68的 entry为2

插入57

查找过程

现在要查找33这个数，通过同样的哈希散射，得到33的bucket=1， bucket[1]=3，3指向的index位置为11，但是11放的是57，不是要找的 33，于是查看相邻的元素为9，非空，可继续查找，位置9存放的是 68，同样不等于33，而相邻的index=10指向位置7，而7存放的就是33 了，通过比较key值相等，所以这个Set里面有33这个数

这里有亮点需要注意：

  • 这里的数据总共是4个数，但是需要比较的次数比较多，key值就 比较了3次，key值的相邻keyChain值比较了2次，总共是5次，比直接来 个for循环还要多。所以数据量比较小时，使用哈希存储速度反而更 慢，但是当数据量偏大时优势会比较明显

  • 还有一个问题就是一旦容量不够，就会触发扩容，会把上述所有的hash计算过程重新来一遍。

Map

和Set基本一致，不同的地方是，map多了存储value的地方，

当然它不是直接存放字符串“hello”，而是存放hello的指针地址， 指向实际存放hello的内存位置。

JS Object

这个可以参考这篇博客：https://sunra.top/posts/37711/