数据结构-hash表

hash表功能

hash表是一种表，用于快速查找。在程序运行时，可以通过空间来换取时间，hash表就是这样一种，使用空间来换取时间的数据结构。hash表通过<key-value>的键值对的方式来访问数据。通过key值来访问数据，实现最快的访问。
hash表本质上，就是数组。链表也是可以用数组的方式来实现的，本质也是数组。

hash表的构成

思考一下，如果hash表的key就是从1、2、3的方式排序，那么查找value值是不是很简单。然而实际使用的时候并不容易这么刚好的情况，如果可以把key的值转换为1、2、3这样的中间值，通过中间值来进行排序，再去数组的对应位置找数据岂不是更快了呢。
即将原本的key-value，加一个中间商 hash值，对应关系就变为

hash函数.jpg

hash值是为了更快查找到目标数据而来的。

hash表的查找

hash表的查找.jpg

这是一个简单的hash表，hash函数为取十位作为hash值，通过这样的hash转换后，每个值都有一个更容易查找的位置。

hash表冲突

由于hash值是通过hash函数转换而来的，无法保证每个key都会有独一无二的hash值，可能有多个key对应同一个hash值，这种情况就叫做hash冲突，hash冲突有多种解决方案。

后移法

如果想要放置的key位置被放置了，则将当前的key对应数据放在后面最近的一个位置上。记住，hash的本质就是数组，此时的数组并不是每个位置都是满的，会有空位，这个位置被占了，就往后面一个位置挪就好了。

hash表-后移法.jpg

链表法

将对应同一个hash值的key都放在同一个节点后续，使用链表的方式进行保存。

hash-链表法.jpg

hash表查找

hash查找，最终目的是通过key查找到目标value，先通过hash值快速定位大概位置。如果hash值位置的key值与查找key是一致的，则查找到了。如果不对，则根据保存方法，去下一个节点查找，直到对应key的位置，就找到了对应value。
以链表法的hash方式为例，如要查找key为15的数据
第一步，先去hash值为1的位置查找。发现此处key不为15，则去下一个链表节点查找。
第二步，查找到此处key为15，查找完成，否则继续去链表下一个节点查找。

hash表的扩容

hash本质是数组，这个数组大小是变化的，不能够让这个数组塞得满满的，数组不够大的话，每个位置下面链表很长，那还是需要一个个遍历，就无法达到快速查找的目的了。HashMap的扩容方式，是当负载因子达到0.75的时候，将数组扩大为原来的两倍，再重新排列hash表。负载因子表示占用位置/总位置的比例，比如数组大小10，被占用7个，则负载因子为0.7。