美团好像比较看重计算机基础，所以在二面的一上来就问了我 TCP/UDP 相关的一些东西，回答的也都还蛮顺利的，不过后面问了一些 HashMap 相关的问题，就整的我有些红温了。

面试官：“你知道 HashMap 插入的时间复杂度是多少？”

我：“O(1)吧”

面试官：“那你知道 HashMap 查找的时间复杂度是多少？”

我：“还是 O(1)吧”

面试官：“那你知道 HashMap 在插入上时间复杂度相比于数组要低一些，那你知道 HashMap 在哪些地方做的不好嘛？”

我：“额......”

这个应该来说是学数据结构的时候学的知识，但有些忘记了，所以在这里打算拿出来整理一下：

接下来我将比较 “链表”、“数组”、“哈希表” 这三个数据结构，分别从 查询时间、插入时间、各自性质来聊聊。

HashMap 的问题

哈希表的潜在问题：

• 哈希冲突：有时候，不同的 key 可能有相同的 hash 值，就会出现冲突，需要单独去处理，实现复杂度上会提升。
• 扩容成本：当哈希表的元素数量超过一定阈值时，需要扩容以保持操作效率。扩容过程涉及重新计算所有元素的哈希值并将它们重新插入到新的哈希表中。比较好的解决办法是一开始就选择恰当的容量，还是需要根据使用场景来看。
• 线程安全：在多线程环境中，哈希表可能需要额外的同步机制来保证线程安全。解决办法可能是使用锁、原子操作或其他并发控制机制来管理并发访问。

查询

• 在查询这个维度，我们一般有两种查询方式，第一种是通过索引查询，第二种是通过元素值查询，我们分别来聊聊～

数组

1. 通过索引查询：时间复杂度：O(1)。描述：数组支持通过索引直接访问元素，这是一个常数时间的操作，因为数组在内存中是连续存储的，所以可以通过计算内存地址来直接定位到元素。
2. 通过元素值查询：时间复杂度：O(n)。描述：如果需要查找数组中是否存在某个特定的元素值，我们通常需要遍历整个数组，这是一个线性时间的操作。

链表

1. 通过索引查询：时间复杂度：O(n)。描述：要访问链表中特定索引的节点，需要从头节点开始遍历链表，直到到达所需索引的节点。
2. 通过元素值查询：时间复杂度：O(n)。描述：要查找链表中包含特定值的节点，我们同样需要从头节点开始遍历链表，直到找到具有该值的节点或遍历完整个链表。

HashMap

1. 平均情况：时间复杂度：O(1)。描述：在没有哈希冲突的情况下，HashMap 可以通过哈希函数将键映射到一个特定的桶（bucket），然后直接访问该桶来获取值。
2. 最坏情况：时间复杂度：O(n)。描述：当所有元素都映射到同一个桶中时（即发生哈希冲突），HashMap 会退化为链表，此时查找操作需要遍历整个链表。

所以其实我前面答的时间复杂度也没有那么正确，答的都是最优答案。

插入

数组

1. 在数组末尾插入：时间复杂度：O(1)（平均情况），O(n)（最坏情况）。描述：如果数组未达到其最大容量，可以在数组末尾直接添加新元素。这是常数时间的操作，因为不需要移动其他元素。
2. 在数组中间或开始插入：时间复杂度：O(n)。描述：在数组的中间或开始插入元素通常需要移动插入点之后的所有元素，以腾出空间。这个操作需要遍历数组中的每个元素，因此时间复杂度是线性的。

链表

1. 在链表末尾插入：时间复杂度：O(1)（如果已知末尾节点），O(n)（如果不知道末尾节点）。描述：如果已知末尾节点，可以直接在其后插入新节点，这是常数时间的操作。如果不知道末尾节点，需要从头节点开始遍历链表，直到找到末尾节点。
2. 在链表中间插入：时间复杂度：O(1)（如果已知插入位置的前一个节点），O(n)（如果不知道插入位置的前一个节点）。描述：如果已知插入位置的前一个节点，可以直接在其后插入新节点。如果不知道，需要从头节点开始遍历链表，直到找到插入位置的前一个节点。

HashMap

1. 平均情况：时间复杂度：O(1)。描述：在没有哈希冲突的情况下，HashMap 可以通过哈希函数将键映射到一个特定的桶（bucket），然后直接在该桶插入新的键值对。
2. 最坏情况：时间复杂度：O(n)。描述：当所有元素都映射到同一个桶中时（即发生哈希冲突），且冲突解决策略是使用链表，那么在链表的尾部插入一个新元素的时间复杂度为O(n)，因为最坏的情况是需要遍历整个链表。