# 哈希表原理刨析
- 哈希表查找的时间复杂度为什么是O(1)呢？
- 哈希冲突到底是什么？
- hashMap为什么有这么多面试官问他的底层实现是什么？
如果你自己有怎么样的疑问那么恭喜你依据超越50%的人了。因为你有求知欲。你想搞清楚事情的真相。以及算法的底层原理。那你以后的前途是不可限量的。
# 哈希表查找的时间复杂度为什么是O(1)呢？
O(1)是一个什么？这个表示算法的一个时间复杂度。它其实就是一个大O加上一个（），括号里面是一个expr的表达式。那么什么是时间复杂度呢？简单来讲就是衡量你这个算法它效率高低的一个指标。如果里面的数值越大。说明你这算法效率越低。如果数值越小说明算法越高效。这里面的数值可以是1、n、n平方就体到底是什么要根据你代码来确定。
代码案例1：
int cnt = 0;
for(int i = 0; i < n; ++i){
cnt + = i;
}
2
3
4
这是一个循环。循环内部有一个累加操作。那么请问上面代码的时间复杂度是多少？答：O(n)
因为随着n的增大它消耗的时间会越来越多嘛。而且和这个n会呈一个线性的关系。所以是O(n)。
如果嵌套二个循环呢？那么是不是O(n^2)
int cnt = 0;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
cnt + = i*j;
}
2
3
4
5
没有循环案例：
int cnt = 0;
cnt = cnt + 1;
2
从1个循环到2个循环O(n^1)到O(n^2),指数从1到2.那么从1个循环到0个循环就是1到0.如O(n^0)
n^0就是1.
总结
一个简单的赋值操作、一个简单的运算操作都叫O(1)。
如果涉及到循环那么就会引入和n相关的变量。几层循环就是n的几次。
如果这里还能看懂你已经超于60%的人。说明你高中数学没有问题。
如我有一个数组。我要获取它的第个元素。那么我们应该这么获取呢？如果有c语言基础对数组应该不会陌生。
int a[6] = {1,2,3,4,5,6};
int x = a[4];
2
这个获取的操作时间复杂度是多少呢？答：O(1)。原因就是数组下标操作其实就是地址偏移。
地址偏移不就是加法的事情。所以就是一个简单的操作就是O(1)。那么为什么哈希表的查找也是O(1)呢？因为哈希表底层物理结构就是一个数组。如果听到这里还能听懂。说明你已经超越了世界上70%的人了。
那么哈希表作为一种数据结构它肯定是要存东西的。它怎么存东西呢？因为哈希表它是一个数组。然后这个数组它有一个长度。假设它的长度是8。然后我有一个数字5.我想存储到哈希表里面去。这个5怎么存进去呢？和数组一样直接赋值。
插入、查找都是通过下标操作。所以时间复杂度都是O(1)。
如果听到这里还能听懂。说明你已经超越了世界上80%的人了。
这个时候数组长度是8，如果数组满了。在来一个8、9这些数怎么存呢？
答：一个操作可以把一个非常大的数变成一个固定范围的数。——取模。也就是小学学的取余数。让8对数组长度进行取余。数组长度是8。8/8 = 1余数为0。把8放到数组下标为0的位置上。
我要查找哈希表里面有没有8这个元素。只需要对8进行取余数。得到0后再通过数组下标0的位置获取查找的数与待查找的数是否相同。相同说明哈希表里面里面有这个数。为什么有这个比较呢？为什么有这个比较的过程呢？答：为什么不是下标取余数之后直接获取呢？因为16对8取余数也是0。32对8取余数也是0。——这个在数学上叫同余。
我们实际上找的是8。不是16、32。到这个里如果还能听懂。说明你已经超越了世界上90%的人了。
# 哈希冲突概念
8、16、32这3个数对数组长度8进行取余以后得到的都是0。所以不能放在同一个位置上。这样会产生冲突。这个种冲突就叫哈希冲突。这个时候我们怎么办呢？有好几种方法。
最经典的一种方法解决：只需要把取模相同的数串联在一个链表中。比如原本数组0下标的位置上已经有了一个8了。当我要插入一个16的时候只需要采用链表的头插入法把16插入进来就可以了。这样0的位置上就有16和8二个元素。这时候你会发现哈希表升级了。它变成了一个链表数组。
什么是链表数组呢？答：本质还是一个数组，只不过数组的每一个元素从原来的数值变为了一个指针。也就是变为了一个链表头。
到这个里如果还能听懂。说明你已经超越了世界上95%的人了。
当然链表对于绝大多数的大学生来说它是一个门槛。链表的增、删、改、查。
这个哈希表的长度是8，那么当我放进去的所有元素都是8的倍数的时候，你就会发现问题来了。什么问题呢？答：就是数组下标0的位置上密密麻麻。而其他位置上空空如也。——当我要查找的时候虽然找下标是O(1)。但是比较链表中每一个元素是否和要查找的元素相等时需要在链表进行遍历。链表遍历就是O(n)。链表没有取下标操作。它必须每一个元素往下遍历。——这个时候我们引入一个新的概念。这个概念叫做负载因子。
# 负载因子概念
什么是负载因子？
答：元素个数/数组长度。
举例子：
哈希表里面已经有100个元素了。数组长度是8。那么这个负载因子是多少呢？100/8 = 12.5。所有我们人为规定一个数字。当负载因子大于5的时候我们要采取一些措施。可以让原本这个链表被打散。变成多个小链表。这个措施我们叫它rehash（重新哈希）。
rehash操作是什么？
答：rehash操作非常简单。就是把原有的数组进行扩容操作。变成原来的二倍。变成二倍之后所有的元素进行一次重新映射。这就是原来是对8进行取余。现在变为对16进行取余。——这就导致在一个链表上的数，被分散到了其它的位置上。
那么这个负载因子控制的足够好。我就能保证这个链表长度它不会很长。而且能把他控制在这个链表。
如果我在扩容的过程中我需要把之前所有的元素都重新进行一次映射的话。那这个时候时间复杂度不就变为O(n)吗？
如果你能提出这样的问题。恭喜你已经超越了98%的人了！
因为你对时间复杂度已经有了非常强劲的概念了。所有说这个时候呢？我采用一种优化。——这个优化叫渐进式rehash。
# 渐进式rehash是什么？
就是不是一次性把所有的元素都进行重新映射。而是这个程序他在运行过程中每一帧我移动一些。就分散cpu的时间。让这个程序不知不觉帮我们把这个rehash的过程给做掉。——所以这个就叫渐进式rehash。到这个里如果还能听懂。说明你已经超越了世界上99%的人了。
还有最后的1%是什么呢？就是我们在设计哈希表的时候这个哈希表的长度要设计层2的幂。我们知道取模效率比较底。所以取模的时候不采用取余数的方式而是采用位与的方式。这个位与就是位运算里面那个位与。
因为任何一个数x。的对2的n次幂进行取模等价于2的n次幂减1.