千锋教育2023新版数据结构与算法视频教程（JavaScript数据结构与算法）

p19 散列表结构

 散列表即 HashTable 类，也叫 HashMap 类，是 Dictionary 类的一种散列实现方式。

散列算法的作用是尽可能的在数据结构中找到一个值。在以前的系列中，如果要在数据

结构中获取一个值，需要遍历整个数据结构来找到它。如果使用散列函数，就知道值的

具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在

表中的位置。有时候一些键会有相同的键值。不同的的值在散列表中对应相同位置的时

候，我们称其为冲突。此时，当我们通过相同的散列值去取属性值的时候会出现相互覆

盖、数据丢失的情况。处理冲突有几种方法：分离链接，线性探查和双散列法，这里说

下分离链接法。在链接法中，把散列到同一个槽的元素都放在一个链表中，该槽中存放

链表的头指针，如果不存在这样的链表，则该槽为NULL。槽中的链表既可以是单链表，

也可以是双链表。