HashTable哈希表

概念

散列表(Hash Table)，又称哈希表。是一种数据结构，特点是:数据元素的关键字与其存储地址直接相关
在顺序结构以及树型结构中，数据元素的关键字与其存储位置没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( $log_2 N$ )，搜索的效率取决于搜索过程中元素的比较次数。
那么在哈希中是如何建立关键字与存储地址的联系呢？
通过散列函数（哈希函数）：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
举例：
在这里插入图片描述
这时我们引出两个概念

同义词和散列冲突

若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词"通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”。

如何设计哈希函数？

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

除留余数法

散列表表长为m，取一个不大于m但最接近或等于m的质数p，因为质数除了1和自身以外，不能被其他自然数整除，这样可以大大的让哈希函数计算出来的地址能够均匀分布在整个空间。

直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
其实就是好像之前的计数排序，我们先计算数据之间的区间大小，然后再按照大小关系去从前到后排放。

如何处理冲突？

解决哈希冲突两种常见的方法是：闭散列和开散列

拉链法（开散列）

存放的每一个元素是一个链表，把相同关键字的数据链接起来，寻找数据的时候，先要找到该关键字的位置再去遍历一遍链表，找到该数据。如图：
在这里插入图片描述

开方地址法（闭散列）

线性检测

就是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。
其数学递推公式为:
在这里插入图片描述
m表示散列表表长;d为增量序列;i可理解为“第i次发生冲突
说人话就是，冲突了就往该冲突元素的后一个位置放。
如图：

因为线性检测的数据是直接往后堆的，所以而对于那些因为冲突而把数据放在后面的位置来说，他们不仅仅只放同义词的，他也会放非同义词，这样就会大大的影响我们查找数据的速度。