前端数据结构--散列表(哈希表)

2021年11月26日 阅读数:4
这篇文章主要向大家介绍前端数据结构--散列表(哈希表),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

散列表的由来

前面说了数组、链表,他们各自有本身的特色:javascript

  1. 数组:具备随机访问的特色,能够快速的根据下标访问到数据,缺点是插入、删除须要移动数据
  2. 链表:插入、删除只须要改变结点之间的引用,缺点是查找数据须要从根结点遍历访问

 散列表是组合了数组和链表的优点,规避它们的不足而产生新的一种数据结构。散列表是一种经常使用的数据存储技术,散列后的数据能够快速地插入或取用。前端

什么是散列表

  散列表英文叫 Hash table,也叫哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它经过把关键码值映射到表中一个位置来访问记录,以加快查找速度。这个映射函数叫作散列函数,存放记录的数组叫散列表 以下图所示java

上面的定义可能不那么清晰,能够尝试这样理解, 散列表就是经过散列函数(也叫哈希函数)将元素的键映射为数组下标(转化后的值叫作散列值或哈希值),而后在对应下标的位置存储记录值、或者查找记录值,这种数据结构称为散列表。算法

  如图散列表用的是数组支持下标随机访问特性,因此散列表其实就是数组的一种扩展,由数组演化而来。能够说,若是没有数组,就没有散列表。咱们经过散列函数把元素的键值映射为下标,而后将数据存储在数组中对应下标的位置。当咱们按照键值查询元素时,咱们用一样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。数组

散列函数

  从上面能够看出散列函数在散列表中起着很是核心的做用,散列函数,顾名思义,它是一个函数。咱们能够把它定义成 hash(key),其中 key 表示键值,hash(key) 的值表示通过散列函数计算获得的散列值,即数组的下标。数据结构

基本特色函数

  1. 散列函数计算获得的散列值是一个非负整数
  2. 若是 key1 = key2,那 hash(key1) == hash(key2)
  3. 若是 key1 ≠ key2,那 hash(key1) ≠ hash(key2)

第一点:由于数组下标是从 0 开始的,因此散列函数生成的散列值也要是非负整数。性能

第二点:相同的 key,通过散列函数获得的散列值也应该是相同的。spa

第三点:理论上key和散列值是一一对应的,可是种现实是颇有可能一个key对应了多个散列值的状况,这就会存在冲突的状况,这取决于散列函数的设计。设计

设计散列函数

  散列函数设计的好坏,决定了散列表冲突的几率大小,也直接决定了散列表的性能。一个好的散列函数基本知足两个原则

一、计算hash值简单

  过于复杂的散列函数,会消耗不少计算时间,也就间接地影响到散列表的性能,所以散列涵的计算要简单、快速。

二、散列函数计算出来的地址要分布均匀

  散列函数生成的值要尽量随机而且均匀分布,这样才能避免或者最小化散列冲突,即使出现冲突,散列到每一个槽里的数据也会比较平均,这样能够保证存储空间的合理使用。

实际工做中,咱们还须要综合考虑各类因素。这些因素有关键字的长度、特色、分布、还有散列表的大小等。

经常使用设计散列函数基本思路:

一、直接地址法

1 hash(key) = a * key + b  // a、b为常数

这种方法计算最简单,不会产生冲突,适合关键字的分布比较连续,并且长度较小的状况,若是关键字不连续,空位就会比较多,就会形成存储空间的浪费。

假如咱们有 20 名选手参加学校运动会。为了方便记录成绩,每一个选手胸前都会贴上本身的参赛号码。这 20 名选手的号码依次是 1 到 20。如今但愿实现这样一个功能,经过号码快速找到对应的选手信息。

咱们能够把号码为 1 的选手,咱们放到数组中下标为 1 的位置;号码为 2 的选手,咱们放到数组中下标为 2 的位置。以此类推,号码为 k 的选手放到数组中下标为 k 的位置。即咱们的哈希函数只要返回对应的key 便可;

1 function hash (key) {
2    return key
3 }

二、数字分析法

  上面号码太简单了,若是把1-20的号码增长了年级、班级,如1 变成了202103001, 2 变成了202103002,那么此时咱们上面那个哈希函数就不适用了。尽管咱们不能直接把号码做为数组下标,咱们能够用号码的后两位作为数组的下标,即咱们的哈希函数能够改成
1 function hash (key) {
2    return String(key).substring(6)
3 }

三、平方取中法

四、折叠法

五、除留余数法

  除留余数法是使用的比较多的一种,公式为:

1 hash(key) = key % p  

若是散列表的表长为m,p为小于等于m的最大的质数,在通常状况下,对质数取余会让冲突更少,数据元素在散列表分布的更均匀。

质数又称素数,除了1和自身,不能被其余天然数整除的数 如(2,3,5,7,11,13,17,...)

若有数据 { 10,15,20,25,30,35,40,45,50 },表长为10,那么咱们对 7 取余以下,其中 ^ 表示为空的链表:

六、随机数法

选择一个随机函数,用关键字做为随机函数的种子,返回值做为散列地址,即

hash(key) = radmom(key) 

可结合除留余数

总结散列函数基本设计原则

散列函数设计没有固定的方法,须要结合实际状况考虑以下因素:

  1. 要清楚关键字分布的状况、范围、规律,结合上面经常使用几种方法,写出散列函数
  2. 散列表的大小要合理,太大浪费空间过小则容易产生冲突
  3. 散列表的数据分布要均匀,不要一些下标中有不少元素,其余的没有或者不多
  4. 散列函数代码要精简,追求的是简单高效、分布均匀

散列冲突

  再好的散列函数也没法避免散列冲突,由于散列值是非负整数,总量是有限的,可是现实世界中要处理的键值是无限的,将无限的数据映射到有限的集合,确定避免不了冲突。即使像业界著名的MD五、SHA、CRC等哈希算法,也没法彻底避免这种散列冲突。并且,由于数组的存储空间有限,也会加大散列冲突的几率。

  咱们经常使用的散列冲突解决方法有两类,开放寻址法(open addressing)和链表法(chaining)。下面简单介绍下链表法

链表法

  链表法是一种更加经常使用的散列冲突解决办法,在散列表中,每一个下标会对应一条链表,全部散列值相同的元素咱们都放到相同槽位对应的链表中。

每个数组下标对应的链表能够是单链表也能够是双链表。

当插入的时候,咱们只须要经过散列函数计算出对应的下标,将其插入到对应链表中便可,因此插入的时间复杂度是 O(1)。

当查找、删除一个元素时,咱们一样经过散列函数计算出对应下标,而后遍历链表查找或者删除。

前端哈希数据结构

  javascript 中的ObjectSetWeakSetMapWeakMap 都是哈希结构。