当前位置:   article > 正文

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

散列表和散列因子

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将散列表用于缓存

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

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/688798
推荐阅读
相关标签
  

闽ICP备14008679号