散列表、散列函数和散列冲突以及应用场景（一文看懂）_散列表和散列因子

1.什么是散列表？

        散列表（HashTable，也叫哈希表）：由数组扩展而来，是根据键（Key）直接访问在内存存储位置的数据结构。

        实现原理是：通过散列函数（也叫哈希函数）将元素的键（key）映射为数组下标（转化后的值叫做散列值或哈希值），然后在对应下标位置存储记录值(value)。当我们按照键值查询元素时，就是用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据.

        图示：

2.什么是散列函数？

2.1概念解释

         散列函数其实就是一个数学算法，把无穷的区间内的数据，经过散列函数计算后，均匀分到一个有限区间内。 散列表中有两个关键的概念，一个是散列函数（或者哈希函数），一个就是下面的散列冲突（或者哈希冲突）。

         散列函数用于将键值经过处理后转化为散列值。具有以下特性：

• 散列函数计算得到的散列值是非负整数
• 如果 key1 == key2，则 hash(key1) == hash(key2)
• 如果 key1 != key2，则 hash(key1) != hash(key2)

        图示：

 2.2 常见散列函数（哈希函数）

2.2.1直接定址法 

2.2.2除留余数法 

2.2.3数字分析法 

2.2.4平方取中法 

2.2.5折叠法（叠加法） 

2.2.6随机数法 

        构造哈希函数的方法很多，实际工作中要根据不同的情况选择合适的方法，总的原则是尽可能少的产生冲突。通常考虑的因素有关键字的长度和分布情况、哈希值的范围等。

        当关键字是整数类型时就可以用除留余数法；如果关键字是小数类型，选择随机数法会比较好。

3.什么是散列冲突？以及如何避免冲突？

3.1概念理解      

        散列函数总是将不同的键映射到数组的不同位置，但是实际上，几乎不可能编写出这样的散列函数。

        举例说：有一个数组，它包含26个位置，即是26个英文字母的顺序。你可以使用简单的散列函数，按字母表顺序分配数组的位置。如果你要将苹果的价格存储到散列表中，自然是第一个位置（Apple),把香蕉的价格存储到其中，自然是第二个位置（Banner），看着很顺利，但是当我们存储梨（Ayocados）时，分配的位置又是第一的位置，这很显然和苹果冲突了，这就是冲突。

        总之：所谓散列冲突，简单来说，指的是 key1 != key2 的情况下，通过散列函数处理，hash(key1) == hash(key2)，这个时候，我们说发生了散列冲突。设计再好的散列函数也无法避免散列冲突，原因是散列值是非负整数，集合的总量是有限的，但是现实世界中要处理的键值是无限的，将无限的数据映射到有限的集合，肯定避免不了冲突。

3.2 如何避免散列冲突？

（1）较低的填装因子

        填装因子计算公式：填装因子=散列表中的元素数 / 位置总数

        比如：数组有五个位置，已占用的有两个位置，那么填装因子=2/5=0.4

        如果填装因子等于1，就是刚好装满，如果大于1，意味着数量超过了数组的位置数，你就需要添加位置（调整长度）。填装因子越低，发生冲突的可能性越小，散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就应该调整散列表的长度。

（2）良好的散列函数

        良好的散列函数让数组中的值呈均匀分布，映射的范围尽可能大。糟糕的散列函数让值扎堆，导致大量的冲突。

良好的散列函数有哪些？

*开放地址法：

key哈希后，发现该地值已被占用，可对该地址不断加1，直到遇到一个空的地址。

*再哈希法：

发生“碰撞”后，可对key的一部份再进行哈希处理。

*链地址法（拉链法​​​​​​​）：

链地址法是通过将key映射在同一地址上的value，做成一个链表，这是常用的方法。

 

4.应用场景有哪些？

4.1.将散列表用于查找

        散列表适用于模拟映射关系，可以用查找。比如手机查找电话的案例，根据姓名映射电话号码来查找电话；还有根据域名映射IP来查找网站等

4.2防止重复

        比如投票的案例：哪些人投过票，防止重复投票，就可以利用散列表。首先创建一个散列表，用于记录已投票的人，有人来投票时，检查他是否在散列表中，如果在里面返回true；否则返回false。

4.3将散列表用于缓存

        缓存是一种常用的的加速方式，所有大型网站都是用缓存，而缓存的数据则存储在散列表中。当你访问网站时，他首先检查散列表中是否存储了该页面，存储的有就发送缓存中的数据，没有才让服务器做处理。

参考网址：散列表、散列函数和散列冲突 - 龙福 - 博客园