数据结构对比（HashMap，ConcurrentHashMap

一、概论

    这篇文章的目的只有一个就是对日常开发中遇到的一些数据结构对其特点，进行归纳总结，具体的细节再后续的文章再一一解释。

二、特点分析

2.1 ArrayList

• 基于动态数组实现，当创建一个 ArrayList 对象时，实际上是创建了一个 Object 类型的数组，初始容量为 10
• 当添加元素时，如果数组已满，ArrayList 会自动扩容，它会创建一个新的数组，并将原数组中的元素复制到新数组中。
• 使用了快速失败机制 (Fail-Fast)
  指的是在多线程环境下，如果一个线程修改了ArrayList的结构（增加、删除或修改元素），那么其他线程在访问ArrayList时，如果发现modCount属性（记录ArrayList结构修改次数的属性）与自己持有的modCount属性不一致，就会抛出ConcurrentModificationException异常，从而防止多个线程同时修改ArrayList的结构，导致数据不一致的情况发生。

2.2 LinkedList

• 优点：
  链表的主要优点是在插入和删除节点时具有较低的时间复杂度。因为链表中的节点可以在内存中非连续地分布，插入和删除操作只涉及到修改指针的指向，而不需要移动其他节点。这使得链表在动态数据结构、频繁的插入和删除操作以及不需要事先知道数据大小的情况下非常有用。

• 缺点：
  然而，链表的缺点是访问特定位置的节点需要遍历整个链表，时间复杂度为O(n)。与数组相比，链表的随机访问效率较低。此外，链表需要额外的内存来存储指针或引用。

• LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。

• 底层的数据结构是基于双向链表的，该数据结构我们称为节点

• 允许所有元素为null

• 它的查找是分两半查找，先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可找到

链表的特点就是在指定位置插入和删除元素的效率较高，但是查找的 效率就不如数组那么高了

2.3 HashMap

HashMap 内部维护了一个数组，称为哈希表，每个元素都是一个链表的头结点，该链表被称为桶（bucket）。当我们向 HashMap 中添加一个元素时，首先会根据该元素的键值（key）计算出一个哈希值（hash code），然后根据哈希值确定该元素在数组中的位置，如果该位置上已经存在了元素，则将该元素添加到该位置上对应的桶中，如果该位置上没有元素，则创建一个新的桶，并将该元素添加到该桶中。

在查找元素时，HashMap 会根据 key 的哈希值确定其在数组中的位置，然后遍历该位置上的链表，查找是否存在对应的 key。如果存在，则返回其对应的 value；如果不存在，则返回 null。由于哈希值可能会发生冲突，因此同一个桶上可能会有多个元素，需要遍历链表才能找到对应的元素。

• HashMap 是非线程安全的，因为它不是同步的，多个线程同时对 HashMap 进行操作可能会导致数据不一致的问题。
• HashMap的实现原理是通过将键对象的哈希码映射到哈希表的索引位置来存储和获取值对象。当多个键对象的哈希码映射到同一个索引位置时，会使用链表或红黑树等数据结构来解决冲突问题。

优点：

• 高效的插入、删除和查找操作：由于使用哈希表来存储键值对，HashMap提供了快速的插入、删除和查找操作
• 可以存储null键和null值：HashMap允许存储null键和null值，这在某些场景下非常有用
• 动态扩容：HashMap会根据当前存储的元素数量动态调整内部数组的大小，以提高性能

缺点：

• 不保证元素的顺序：HashMap不保证元素的顺序，如果需要有序的键值对集合，可以考虑使用LinkedHashMap
• 线程不安全：HashMap是非线程安全的，如果在多线程环境下使用，需要进行额外的同步处理，或者使用线程安全的ConcurrentHashMap。

2.4 ConcurrentHashMap

ConcurrentHashMap是Java中的一种线程安全的哈希表实现，它是HashMap的一个线程安全版本。与HashMap不同的是，ConcurrentHashMap可以在多线程环境下进行并发操作而不需要额外的同步措施。它提供了高效的并发读取和更新操作，并且保证了线程安全性。

ConcurrentHashMap的实现原理是将整个哈希表分成多个小的子哈希表（称为段），每个段都可以独立地进行读写操作。每个段内部使用了与HashMap类似的哈希桶和链表（或红黑树）的数据结构来存储键值对。当多个线程同时访问不同的段时，它们可以并发地进行读写操作，从而提高了并发性能。

优点：

• 高效的并发读取和更新操作：ConcurrentHashMap允许多个线程同时进行读取和更新操作，提供了较好的并发性能。
• 线程安全性：ConcurrentHashMap通过使用锁分段技术来保证线程安全性，不需要额外的同步措施。
• 动态扩容：ConcurrentHashMap可以根据需要动态调整大小，以适应不同的并发访问情况。

缺点：

• 内存占用较大：由于ConcurrentHashMap需要维护多个段，因此相对于HashMap来说，它的内存占用会更大一些。

• 迭代性能较低：由于ConcurrentHashMap的内部结构是分段的，因此在迭代操作时性能可能会受到一定的影响。
  ConcurrentHashMap在实际开发中常用于需要高并发读写操作的场景，例如缓存、并发任务处理和并发计算等。它提供了一种线程安全的哈希表实现，可以有效地处理多线程环境下的并发访问问题。

2.5 HashTable

• Hashtable底层也采用数组+链表的数据结构进行实现，当哈希冲突发生时，使用链表来解决冲突。与HashMap不同的是，Hashtable在JDK 8及以前没有使用红黑树解决哈希冲突，这导致了其效率相对较低。

• Hashtable是线程安全的类，即多个线程同时操作Hashtable中的元素也不会产生错误的结果或者抛出ConcurrentModificationException异常。

• Hashtable不允许存储null值和null键，否则将会抛出NullPointerException异常。

• Hashtable在JDK 8及以前没有使用红黑树解决哈希冲突，相对于HashMap而言，Hashtable的效率比较低。另外，由于Hashtable不支持null键和null值，因此对其进行操作时要额外小心。Hashtable的查找、插入和删除操作平均时间复杂度为O(1)，但是在极端情况下，因为哈希冲突的原因，可能会退化到O(n)。

参考文献
ArrayList 的底层原理和源码分析
深入理解Array、List、Map集合框架底层实现原理
ArrayList的底层实现原理
LinkedList 的实现原理
LinkedList原理解析
hashmap & hashtable 区别
hashmap hashtable学习笔记
ConcurrentHashMap 底层原理
深入理解ConcurrentHashMap
深度解析Hashtable