散列函数设计的好坏，决定了散列表冲突的概率大小，也直接决定了散列表的性能。一个好的散列函数基本满足两个原则
1、计算hash值简单
过于复杂的散列函数，会消耗很多计算时间，也就间接地影响到散列表的性能，因此散列涵的计算要简单、快速。
2、散列函数计算出来的地址要分布均匀
散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突，即便出现冲突，散列到每个槽里的数据也会比较平均，这样可以保证存储空间的合理使用。
实际工作中，我们还需要综合考虑各种因素。这些因素有关键字的长度、特点、分布、还有散列表的大小等。
常用设计散列函数基本思路：
- 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-20的号码增加了年级、班级，如1 变成了202103001， 2 变成了202103002，那么此时我们上面那个哈希函数就不适用了。尽管我们不能直接把号码作为数组下标，我们可以用号码的后两位做为数组的下标，即我们的哈希函数可以改为
- 1 function hash (key) {
- 2 return String(key).substring(6)
- 3 }
除留余数法是使用的比较多的一种，公式为：
如果散列表的表长为m，p为小于等于m的最大的质数，在一般情况下，对质数取余会让冲突更少，数据元素在散列表分布的更均匀。
质数又称素数，除了1和自身，不能被其他自然数整除的数 如（2，3，5，7，11，13，17，...）
如有数据 { 10，15，20，25，30，35，40，45，50 }，表长为10，那么我们对 7 取余如下，其中 ^ 表示为空的链表：
选择一个随机函数，用关键字作为随机函数的种子，返回值作为散列地址，即
可结合除留余数
总结散列函数基本设计原则
散列函数设计没有固定的方法，需要结合实际情况考虑如下因素：
- 要清楚关键字分布的情况、范围、规律，结合上面常用几种方法，写出散列函数
- 散列表的大小要合理，太大浪费空间太小则容易产生冲突
- 散列表的数据分布要均匀，不要一些下标中有很多元素，其他的没有或者很少
- 散列函数代码要精简，追求的是简单高效、分布均匀
散列冲突
再好的散列函数也无法避免散列冲突，因为散列值是非负整数，总量是有限的，但是现实世界中要处理的键值是无限的，将无限的数据映射到有限的集合，肯定避免不了冲突。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。
我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。下面简单介绍下链表法
链表法
链表法是一种更加常用的散列冲突解决办法，在散列表中，每个下标会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
每一个数组下标对应的链表可以是单链表也可以是双链表。
当插入的时候，我们只需要通过散列函数计算出对应的下标，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。
当查找、删除一个元素时，我们同样通过散列函数计算出对应下标，然后遍历链表查找或者删除。
前端哈希数据结构
javascript 中的Object、Set、WeakSet、Map、WeakMap 都是哈希结构。
经验首页