Java数据结构之HashMap

HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

数据结构

整体为数组，数组的元素是一个个链表，每个链表当中串有若干node。

为什么是链表？

数组的容量是有限个数的。插入键值对实例时使用哈希算法，先基于哈希函数计算键值的索引（数组的下标），然后插入对应的位置。当发生碰撞时，对比键值是否相等，相等则覆盖，不相等则将新键值对插入到对应位置的链表中。

扩容机制

当元素个数大于阈值时扩容，使用2倍大小的新数组代替旧数组，将原数组拷贝到新数组。这个阈值是根据数组长度和loadFactor（负载因子）决定的，默认为0.75。

红黑树转化（JDK 1.8）

当链表长度大于8且数组长度大于64时，链表会转化为红黑树。转化的目的是为了改善查找的时间复杂度。

当位于同一个链表中的元素很多（哈希值相等但键值不同）时，通过遍历查找键值比较低效。

为什么hashMap是线程不安全的？

数据覆盖（JDK 1.8）

两个线程同时进行put操作时，A线程冲突检测后未完成插入就挂起，B线程正常完成插入，那么A线程在被唤起继续插入后可能会覆盖B线程插入的值。

ConcurrentHashMap

Quote

详细理解HashMap数据结构，太齐全了！