前言

《架构师的自我修养》

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

从hash表的结构来看：

hash表是基于数组和链表来实现的，存储数据是使用的是余数法，即使用hash表的长度(8)对key的hashCode(101)求余，余数(5)就是数组的下标。

但是，余数法存在一个问题，就是不同key可能存在相同的下标，比如：101%8=5和109%8=5得到相同的下标（5），这就造成了hash冲突。

为了解决hash冲突，常用的方法就是链表法，hash表将冲突的下标退化成一条链表，链表的时间复杂度为O(N)，所以hash表单的时间复杂度就是O(1)