哈希表的工作原理和优化技巧有哪些？

哈希表： 还要补一下数据结构里面几个衡量哈希表的概念、参数 以及冲突的概率 哈希表有一个哈希函数\(h（x)\),给定元素代入函数求出应该存储的下标 Hash就是找到一种数据内容和数据存放地址之间的映射关系 哈希函数的目的是减小不必要的存储空间，但有可能却因此引起冲突 冲突：不同的\(x\)的\(h（x）\)相同，导致第一次出现x被误认为多次出现 哈希函数\(h(x)\)的几种计算方法： 直接定址法： \(h（x)=x\)或\(h(x)=kx+b\) 显然当确保\(h（x）\)都是整数时可以 保证不存在冲突，但是当k或b出现分数或负数时，由于下标必须是正整数，所以在某些\(x\)下要进行加减取舍导致存储到附近的整数值中，而对于另一个\(x\)可以使\(h（x）\)本来就是整数，且这个整数与另一个\(x\)的\(h(x)\)加减取舍后的值相同，引起冲突。 数字分析法： 分析数字哪几位出现重复较少，就以哪几位为哈希函数，以减少冲突 平方取中法 把\(x\)求平方 ，然后取几位重复少的，以减少冲突 折叠法 把\(x\)分成 \(x\)的位数/一个常数 个部分 ，前面部分位数相同，最后部分位数可以不同，然后把这些分开的部分加在一起，使位数为这个常数，若位数少则补\(0\)，若位数多则舍去最高位进位，然后把处理过的数作为\(h（x)\). 这种方法一是存在舍去进位，二是若2个数的位数相同，划分方法相同，划分后每部分都一样，只是顺序不同，那么这两个数\(h(x)\)的值相同，会造成冲突。所以也会引起冲突。 除留余数法 这是最常用的方法 \(h(x)=x\mod p\) \(p\)一般是一个质数，以减少冲突，\(p\)要小于等于哈希表大小，这是压缩空间的做法，把一个大数取模使其变小，必然会引起冲突，但可以减少不必要的空间，使存储位置连续 随机数法： 严格说是伪随机数法 \(h(x)=rand(x)\) \(rand\)是伪随机函数，即对于一个\(x\)只会有一个取值，对于不同的\(x\)大概率会有不同的取值，但也会有冲突 真正随机函数对于一个\(x\)每一次的取值不同 平方散列法： \(h(x)=x*x/(2^28)\) 小数全是冲突，大数溢出无所谓，因为右移后是正数，可以当做下标 注意对于任何方法当x为负数时要确保计算出的\(h(x)\)为正数，若不是可以加上大数或求绝对值 fib散列法 \(h(x)=(k*x)/(2^28)\) \(k\)是常数 对于16位整数 \(k\)为\(40503\) 对于32位整数 \(k\)为\(2654435679\) 对于64位整数 \(k\)为 \(11400714819323198485\) 上面的\(k\)是黄金比*(2^多少位整数）算出的，因为fib的前项比后项接近黄金比，所以叫做fib散列法 这样能减少冲突 哈希表处理冲突方法： 拉链法： 将冲突的下标下开一个链表，储存所有冲突元素原数据，链表初始为空，每次尝试插入元素时先算出哈希值，如果这个位置链表为空就插入，说明插入成功，查找失败，如果这个位置链表不为空就从链表头开始查找，如果找到了这个元素就说明查找成功，插入失败，如果遍历完链表还找不到这个元素就在链表头或尾插入这个元素，说明查找失败，插入成功。