1、什么是散列表

散列表就类似于键值对的形式一一对应，将输入映射到数字，并且每次输入输出都是一致的。 比如

2、散列表应用

• 1、用于查找

例如： 手机号查找

• 2、防止重复

例如：选举投票

• 3、用作缓存

例如：访问页面的缓存

3、散列表的优势

• 1、平均情况下，散列表的查找时间复杂度为O(1)

原因是，在查找的情况下，散列表只需要输入并返回对应的数字即可，而在链表中查询的话需要一个一个去遍历。 这里散列表具有数组查找的优势

• 2、在平均情况下，散列表删除和插入的时间复杂度为O(1)

同理，这里的删除和插入原理一样，输入并返回对应的数字就即可。 在删除和插入的时候，散列表具有链表的优势

4、散列表的冲突

假设你的散列表有26个位置，散列函数也很简单，按照字母的排序来分配位置。 按照字母分配 这里就会出现一个问题：

• 1、 存入苹果APPLE 放在第0个位置
• 2、存入香蕉Banana 放在第1个位置
• 3、存入梨Pear 放在第15个位置
• 4、存入李plum 放在15个位置
• ...
• 但是15的位置已经存入的梨，这里就引起了冲突

冲突:给两个不同的键分配了同一个地址，最简单的解决方案是如果遇到有冲突的，就在冲突的位置存储一个链表。但是如果存储一个链表，就意味着散列表的所有元素都在一个链表中。 ps：这里告诉我们，散列函数是非常重要的，如果散列表越长，那么速度就会急速下降，但是，如果散列函数很优，那么链表就不会很长。 如果说速度下降，就可能会导致散列表的时间复杂度为O(n)

减少冲突可以提升散列表的性能。所以，减少冲突的方式有两种：

• 1、良好的散列函数
• 2、较低的填装因子

5、什么是填装因子

填装因子的计算公式： 比如：这里的填装因子就是2/5 在散列表中，如果填装因子>1的情况下，就意味着商品数量超过了数组的位置数。一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度（resizing）。因为填装因子越低，发生冲突的可能性就越小。一旦填装因子大于0.7，就调整散列表的长度

6、总结

• 1、 你可以结合散列函数和数组来创建散列表。
• 2、 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
• 3、 散列表的查找、插入和删除速度都非常快。
• 4、 散列表适合用于模拟映射关系。
• 5、 一旦填装因子超过0.7，就该调整散列表的长度。
• 6、 散列表可用于缓存数据（例如，在Web服务器上）。
• 7、 散列表非常适合用于防止重复。