首页 > temp > JavaScript教程 >
-
前端数据结构--散列表(哈希表)
散列表的由来
前面说了数组、链表，他们各自有自己的特点：
- 数组：具有随机访问的特点，可以快速的根据下标访问到数据，缺点是插入、删除需要移动数据
- 链表：插入、删除只需要改变结点之间的引用，缺点是查找数据需要从根结点遍历访问
散列表是组合了数组和链表的优势，规避它们的不足而产生新的一种数据结构。散列表是一种常用的数据存储技术，散列后的数据可以快速地插入或取用。
什么是散列表
散列表英文叫 Hash table，也叫哈希表，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录的数组叫散列表 如下图所示
上面的定义可能不那么清晰，可以尝试这样理解， 散列表就是通过散列函数（也叫哈希函数）将元素的键映射为数组下标（转化后的值叫做散列值或哈希值），然后在对应下标的位置存储记录值、或者查找记录值，这种数据结构称为散列表。
如图散列表用的是数组支持下标随机访问特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
散列函数
从上面可以看出散列函数在散列表中起着非常核心的作用，散列函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示键值，hash(key) 的值表示经过散列函数计算得到的散列值，即数组的下标。
基本特点
- 散列函数计算得到的散列值是一个非负整数
- 如果 key1 = key2，那 hash(key1) == hash(key2)
- 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)
第一点：因为数组下标是从 0 开始的，所以散列函数生成的散列值也要是非负整数。
第二点：相同的 key，经过散列函数得到的散列值也应该是相同的。
第三点：理论上key和散列值是一一对应的，但是种现实是很有可能一个key对应了多个散列值的情况，这就会存在冲突的情况，这取决于散列函数的设计。
设计散列函数
散列函数设计的好坏，决定了散列表冲突的概率大小，也直接决定了散列表的性能。一个好的散列函数基本满足两个原则
1、计算hash值简单
过于复杂的散列函数，会消耗很多计算时间，也就间接地影响到散列表的性能，因此散列涵的计算要简单、快速。
2、散列函数计算出来的地址要分布均匀
散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突，即便出现冲突，散列到每个槽里的数据也会比较平均，这样可以保证存储空间的合理使用。
实际工作中，我们还需要综合考虑各种因素。这些因素有关键字的长度、特点、分布、还有散列表的大小等。
常用设计散列函数基本思路：
1、直接地址法
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 }
2、数字分析法
1 function hash (key) { 2 return String(key).substring(6) 3 }
3、平方取中法
4、折叠法
5、除留余数法
除留余数法是使用的比较多的一种，公式为：
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 取余如下，其中 ^ 表示为空的链表：
6、随机数法
选择一个随机函数，用关键字作为随机函数的种子，返回值作为散列地址，即
hash(key) = radmom(key)
可结合除留余数
总结散列函数基本设计原则
散列函数设计没有固定的方法，需要结合实际情况考虑如下因素：
- 要清楚关键字分布的情况、范围、规律，结合上面常用几种方法，写出散列函数
- 散列表的大小要合理，太大浪费空间太小则容易产生冲突
- 散列表的数据分布要均匀，不要一些下标中有很多元素，其他的没有或者很少
- 散列函数代码要精简，追求的是简单高效、分布均匀
散列冲突
再好的散列函数也无法避免散列冲突，因为散列值是非负整数，总量是有限的，但是现实世界中要处理的键值是无限的，将无限的数据映射到有限的集合，肯定避免不了冲突。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。
我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。下面简单介绍下链表法
链表法
链表法是一种更加常用的散列冲突解决办法，在散列表中，每个下标会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
每一个数组下标对应的链表可以是单链表也可以是双链表。
当插入的时候，我们只需要通过散列函数计算出对应的下标，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。
当查找、删除一个元素时，我们同样通过散列函数计算出对应下标，然后遍历链表查找或者删除。
前端哈希数据结构
javascript 中的Object、Set、WeakSet、Map、WeakMap 都是哈希结构。
本文链接：https://www.cnblogs.com/longbensong/p/14702970.html
