听到散列表,第一时间想到 Python 中的 Dict,可是我们是前端。那么散列表在 JS 中是如何描述的呢?这节,我们来一探究竟。

一、散列表

使用散列函数和数组创建了一种被称为散列表 hash table 的数据结构。

Python 提供的散列表实现为字典 ,你可使用函数 dict 来创建散列表。

1
2
3
4
5
6
7
book = dict()
>>> book["jartto"] = 0.67
>>> book["milk"] = 1.49
>>> book["avocado"] = 1.49
>>> print book
{'avocado': 1.49, 'jartto': 0.67, 'milk': 1.49}

散列表由键和值组成。在前面的散列表 book 中,键为商品名,值为商品价格。散列表将键映射到值。

那么 JS 中如何实现呢?

其实 Map 对应的就是散列表,一种 Hash Map 结构。


1
2
3
4
5
6
7
8
let book = new Map();
book.set('jartto', 0.67);
book.set('milk', 1.49);
book.set('avocado', 1.49);
console.log(book); // {"jartto" => 0.67, "milk" => 1.49, "avocado" => 1.49}
book.get('jartto'); // 0.67

二、散列表特性

1.散列函数总是将同样的输入映射到相同的索引。
2.散列函数将不同的输入映射到不同的索引。
3.散列函数知道数组有多大,只返回有效的索引。如果数组包含 5 个元素,散列函数就不会返回无效索引 100。

注意:对于同样的输入,散列表必须返回同样的输出。

三、请问下面哪些散列函数是一致的?

1.f(x) = 1  ←——无论输入是什么,都返回 1
2.f(x) = rand()  ←——每次都返回一个随机数
3.f(x) = next_empty_slot()  ←——返回散列表中下一个空位置的索引
4.f(x) = len(x)  ←——将字符串的长度用作索引

四、防止重复

假设我们要做一个投票统计,每个人只允许投票一次,为此,首先创建一个散列表,用于记录已投票的人。有人来投票时,检查他是否在散列表中。

书中均为 Python 实现,这里我们都转为 JS 实现。

1
2
3
4
5
6
7
8
9
10
11
let voted = new Map();
function checkVoter(name) {
if(voted.has(name)) {
console.log('kick them out!');
} else {
voted.set(name, true);
console.log('let them vote!');
}
}
checkVoter('jartto') // let them vote!
checkVoter('jartto') // kick them out!

五、总结

这里总结一下,散列表适合用于:
1.模拟映射关系;
2.防止重复;
3.缓存/记住数据,以免服务器再通过处理来生成它们。

注意:
1.散列函数很重要。前面的散列函数将所有的键都映射到一个位置,而最理想的情况是,散列函数将键均匀地映射到散列表的不同位置。
2.如果散列表存储的链表很长,散列表的速度将急剧下降。然而,如果使用的散列函数很好 ,这些链表就不会很长!

六、补充:性能

散列表的性能:
1.查找:平均 O(1),最糟 O(n)
2.插入:平均 O(1),最糟 O(n)
3.删除:平均 O(1),最糟 O(n)

在平均情况下,散列表执行各种操作的时间都为 O(1)。

七、散列表实现原理

这里,我们需要理解两个概念:

  • 装填因子:散列表使用数组来存储数据,因此你需要计算数组中被占用的位置数。
  • 调整长度:装填因子大于 1,就意味着有数据是没有存储位置的。

一旦填装因子开始增大,就需要在散列表中添加位置,这被称为调整长度 resizing。通常将数组增长一倍。

填装因子越低,发生冲突的可能性越小,散列表的性能越高。

一个不错的经验规则是:一旦填装因子大于 0.7,就调整散列表的长度。良好的散列函数让数组中的值呈均匀分布。糟糕的散列函数让值扎堆,导致大量的冲突。

八、学习目录