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

@TOC

要了解 Hash 表，需要先从数组说起

数组

数组会在内存中申请连续的地址空间，且数组中各元素类型必须一致

上图假设数组元素为整型，由于整形占据4各字节的内存空间，所以上图每个数组的内存地址从下标0开始，下标每增加1，地址就增加4 所以只要知道了数组的下标，就可以计算得到数组的地址，比如元素4，我们知道数组起始地址后，只要用起始地址+下标*4就可以知道元素4的地址，所以访问指定下标的数组元素的时间复杂度为O（1） 如果只知道数组的值反查数组下标，则需要遍历真个数组，时间复杂度为O（N） 链表 不同于数组必须要连续的内存空间，链表可以使用零散的内存空间存储数据。不过，因为链 表在内存中的数据不是连续的，所以链表中的每个数据元素都必须包含一个指向下一个数据 元素的内存地址指针。如下图，链表的每个元素包含两部分，一部分是数据，一部分是指向