Hash表的时间复杂度为什么是O(1)?

本文是学习李智慧在极客时间的《后端技术面试38讲》课程内容的收获

这个问题看起来是对哈希表这一数据结构的理解，但其实是对其实现方式所使用的基本知识的理解，很好的反映了新技术都是建立在基础技术上这一理念。

        Hash表对外暴露的功能是通过Key值，在O(1)的时间复杂度内找到对应的Value（Key是去重的）。对应的唯一性是通过  + 保证。有意思的地方主要是看是通过什么样的方法去保证的唯一性和时间复杂度

1. Key值---》Hash函数---》Hash值（时间复杂度为O(1)）
2. 通过Hash值定位Value

        步骤1的时间复杂度是hash函数保证，重要的是步骤二的时间复杂度也要为O(1)，我知道的就是Hash表维护一个一维数组，通过将Hash值对数组长度取余，得到一个[0, 数组长度)的范围值，正好对应数组下标，通过数组下标可以在O(1)的时间复杂度内得到Value。会有取余后下标相同的情况，Value跟在之前的Value后面，遍历找到对应的元素。数组元素就变为链表首地址

这是一个 1 + 1 > 2的过程，面试碰到这一题如果能推出来真的是天才。但是这个分析过程帮助我们更能理解基础知识

1. 底层存储中，<内存地址, Value>是一一对应的，现在有Hash函数来保证是一一对应，理想化的话那么我们只要保证是一一对应的（这里只要保证此映射是O(1)的，就能保证Hash表的O(1)）
2. 理想化的情况要涉及到对内存的操作，不太现实，尽量利用已有的数据结构
3. 数组访问元素是通过内存地址 = 数组首地址 + 元素下标 * 元素占位占内存个数来访问，这个操作是O(1)，理想情况那只要保证是唯一的，并且映射过程是O(1)
   1. 数组的实际数据是分配在堆中（连续的内存块），栈帧中（函数调用底层结构）能计算数组元素位置需要数组首地址，这就反映出数组在声明时将数组内存首地址保存到了栈帧中，就是函数中的数组名
4. 如果碰到取余映射相同，就跟在后面形成一张链表

利用Hash值取余的话，极端情况下会退化成一张链表，通过Key查找一个Value时间复杂度就变为O(n)（步骤1-3的时间复杂度不变，最后遍历查找链表的时间为O(n)）。要保证Hash表的时间复杂度，就是的映射过程时间复杂度尽量低。盗张图，这张图并不是Hash表的全部，Hash表是一个类，包含了上述的流程，实现了相关需求，表只是一个抽象的概念。图中只是这个类中数组部分的数据结构