什么是Hash表外链？
在hash表中，collision(冲突)是无法避免的。当两个键值散列到同一个桶时，可以使用链表方式将这些键值连接在一起。这些链表被称为“链表散列”，但这些链表也可以链接到外部数组中，这就是hash表的外链。
为什么要使用Hash表外链？
虽然hash表是快速的搜索目录，但碰撞仍然无法避免，特别是当你需要处理大量数据时。当散列函数所得到的值都在一个桶中时，它们需要被连接起来形成一个链表，如果插入到哈希表的键值对很多，那么这张链表的长度可能会很长，这会影响查找时间的表现。而外链可以帮助你解决这个问题。
如何使用Hash表外链？
使用外链的步骤如下：
- 为哈希表申请比桶数更大的数组长度。数组的每个元素管理一个桶，并指向一个外部链表的头节点。
- 实现哈希函数，根据键值生成哈希码。
- 将键值对应的哈希码与应该存放的桶数取余，得到对应的桶的位置。
- 搜索这个桶的链表。如果这个链表的头指针为空，说明这个桶还没有键值插入，直接将键值对插入到哈希表。
- 如果第一个键值对的哈希码与插入键值对的哈希码相同，那么在链表开头插入键值对。
- 否则就在这个链表末尾插入新的键值对。
使用外链技术可以提供更快的检索速度，尤其是在发生冲突的时候。例如，如果键值N的哈希码和键值T的哈希码相同，则这些键值将不得不为哈希表的同一个桶竞争。如果哈希表数组中足够的插槽用于包容全部的键值，那么就容易在避免时间的损失的情况下插入键值。
