哈希表-hash

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

Hash表-散列表

   Hash表被称作哈希表，也叫做散列表。哈希表是一种比较特殊的数据结构，它遵循函数映射的思想，以Key: Value的方式存储数据。哈希表最大的特点是可以快速定位到要查找的数据，查询的时间复杂度接近O(1）

哈希表的设计原理

假如我们有一组数据,某位工程师每年的收入情况

2017 -- 100000 

2018 -- 130000

2019 -- 140000

2020 -- 200000

      如果我们用普通的链表来存储这些数据，当我们查询2019年的收入情况时，需要从链表的初始节点开始对整张链表进行遍历，直到找到2019，然后取出对应的数据。这种查找的时间复制度是O(n)，即使当我们顺序存储使用二分查找时，时间复杂度也是O(logn)。如果我们可以知道年份，也就是key值，可以直接取出对应的收入数据，时间复杂度就是O(1)，而如果将数据存储在哈希表中，我们就可以实现这种查找。

      哈希表的原理并不复杂，简而言之就是根据Key来计算出存储位置，然后将数据放入该空间，查询时同样根据Key计算出存储位置后直接将相应的值取出。

    哈希函数

    根据Key来计算存储位置的计算规则我们称之为哈希函数，还是用这个例子，我们取一个最简单的哈希函数H(x) = x。

      在上面的这个例子中，虽然我们实现了一个简单的哈希表，但是可以很明显的看出，其中有大量的空间被浪费，长度为2020的数组我们只用到了4个空间，下面我们对这个哈希表进行改良。

     通过观察需要存储的数据，我们选择一个新的哈希函数H(x) = x - 2000

在这个例子中，可以看到空间的浪费比优化前大幅减小。从中可以看出，根据数据特点选定合适的表大小和哈希函数是哈希表这种数据结构实现的关键。

下面介绍几种通用的哈希函数

除留取余

直接定址

折叠

平方取中

数学分析

冲突

    哈希表还要解决的一个问题就是冲突，当选择了一个哈希函数之后，有可能不同的数据会计算出相同的key,比如H(x) = x % 5 这种算法，6 和 11 都会计算出1,此时就会产生冲突。如果不解决冲突，哈希表就无法构建出来。解决冲突的办法有以下几种：

1、链接地址法将有冲突的数据放在一个链表里，当查询时会根据key查到链表的第一个节点，然后遍历整个链表，找到相应的值。

2、开放定址法

最具代表性的一种是线性探测法

H(x) = x % 5

数据样本:

计算Key: { 0, 1, 3, 2, 1}

存储数组 [0, 1, 2, 3, 4, 5, 6, 7 .....]    

[5, 6, 12, 8, 11] 当存储11的时候，发现下标是1的位置以及被占据了，此时根据线性探测法的规则依次往后遍历，直到找到空的位置，所以在下标为4的位置填入11。

线性探测法最大的问题是冲突累计，解决一个冲突的同时会占据别的key的位置，又造成了新的冲突。

改良的方法有二次方探测法和随机数探测法