什么是散列表
散列表也叫哈希表，输入某一关键字输出其对应的数值的数据结构
散列表的生成依赖于散列函数，散列函数的要满足如下特性：
（1）每次输入相同的关键字，输出的数字要相同；
（2）不同的关键字要映射到不同的数字上，如果输入不同的关键字却得到了相同的输出数字，那么就不是一个好的散列函数；
散列表的问题
在创建散列表的时候会发生冲突，即将不同的关键字映射到相同的位置。
一种简单的解决方式是，当不同的关键字映射到了同一个位置，就在这里用一个链表。
这样导致的问题是散列表在查找的时候性能会下降。不难看出散列表的性能取决于最终创建出来的散列表是什么样的，于是性能就有了最好和最坏的区别，散列表相对于数组和链表的性能对比如下：
避免冲突要从两个方面考虑，填装因子、散列函数
（1）填装因子度量的是散列表中有多少位置是空的，公式：元素总数/位置总数。填装因子越小越好，也就是空的位置越多越好，当然空的越多也说明对空间浪费的越多，需要根据实际情况而定。一般填装因子要小于0.7为好。
（2）散列函数决定了元素的分布方式，一个好的散列函数要尽量让元素均匀分布，才能发挥出散列表的优性能。
散列表的应用
（1）查找，像电话簿这种场景中，人名和电话有严格的一一对应关系，创建键值对，能够实现快速查找。
（2）缓存，用户经常使用的网页，比如个人主页，先存起来，在点击之后根据用户ID快速找到对应的主页信息。
网友评论