HashMap 源码解读
前言
HashMap相较于之前的ArrayList和LinkedList，其理解上还是稍微有一些难度，其底层的实现是散列表, 散列表对于哈希冲突的解决方式有如下两种(开放寻址法, 链表法)：
开放寻址法
以下为一些常用的开放寻址法。
有线性探测法
hash(key)+0、hash(key)+1、hash(key)+2…
二次探测（平方探测法）
hash(key)+0, hash(key)+1^2, hash(key)+2^2…..
双重散列
第一次根据hash()函数计算得到的存储位置已经被占用，再用第二个hash()函数计算
链表法
对于不同的关键字可能会通过散列函数映射到同一个地址。为了避免发生分歧，将同样的哈希结果，但是不同关键字的元素，可以将它们存储在一个线性链表中。
HashMap中的解决哈希冲突的方式就是链表法
概述
HashMap主要用来存放键值对, 其基于哈希表的Map接口实现, 是常用的Java集合之一.JDK1.8之前HashMap由数组+链表组成, 其使用的是数组进行存储, 之后使用链接法解决哈希冲突. JDK1.8之后HashMap在解决哈希冲突时, 与之前不同的是, 当链表长度大于阈值(默认是8), 将链表转化为红黑树, 避免过长的链表从而降低性能(过长的话, 就相当于使用的是链表存储的了,每次的查找都会导致O(n)的时间), 同时转化为红黑树的时候也会进行判断（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间
HashMap的源码中，充斥个各种位运算代替常规运算的地方，以提升效率：
- 与运算替代模运算。用 hash & (table.length-1) 替代 hash % (table.length)
- 用if ((e.hash & oldCap) == 0)判断扩容后，节点e处于低区还是高区。
形象理解:
HashMap的底层为数组, 可以将其称之为哈希桶 每个桶里放的是链表.
其是线程不安全的允许key为null, value为null遍历时无序.
依赖
- 实现了
Serializable接口 - 实现了
Cloneable接口 - 实现了
Map接口，并继承了AbstractMap类
阅读套路
按照正常的逻辑， 首先基础的数据构造, 然后了解其构造方法， 之后了解常用的API(CRUD)操作即可。
- [x] 增
- [x] 删
- [x] 改
- [x] 查
从节点的构造开始
HashMap整体的构造
在添加元素的时候, 会先根据hash值计算出其应在的位置, 若是没有冲突, 则直接放入, 若是有冲突, 则将该元素以俩表的形式插入到链表尾部
若是链表的长度超过阀值(默认是8), 则将链表转化为红黑树, 提高效率
数组的查询为$O(1)$ , 链表的查询为$O(k)$, 红黑树的查询为$O(logk)$, $k$表示为桶中的元素的个数, 所以当元素很多的时候, 转化为红黑树能提高查询效率
单个节点的构造
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 哈希值
final K key; // key
V value; // value
Node<K,V> next; // 链表中该元素指向的下一个节点
// 单个节点包含的信息
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
// 哈希函数
// 一个节点的hash值是将key的哈希值和value的哈希值异或得到
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// 设置新的value 同时返回旧的value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
总结:
- 一个节点的hash值是将key的哈希值和value的哈希值异或得到
- 单个节点包含的信息有
- key
- value
- hash值
- next指针（指向下一个节点）
红黑树节点的构造
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 默认为红色， 原因为红黑树的性质四
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
类的属性
//初始容量为16 注释中说明了 必须为2的幂次
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子0.75(若是构造函数中未说明)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 桶中的节点数量大于8时转为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 桶中的节点数量小于6时 转为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 哈希桶 存放链表 总是2的倍数
transient Node<K,V>[] table;
// 存放具体元素的集
transient Set<Map.Entry<K,V>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// threshold = 哈希桶.length * loadFactor; 当桶的使用数量操作该值, 进行扩容
int threshold;
// 装载因子，用于计算哈希表元素数量的阈值。
final float loadFactor;
总结：
最为重要的属性为：
table、size、threshold、loadFactor
构造方法
HashMap()
public HashMap() {
// 默认构造方法 将负载因子设置为默认值 0.75, 其他的属性均为默认
// 假设默认初始化空间大小为16, 则元素数量达到16*0.75=12时, 会进行扩容.
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
这是一个默认构造器，潜在的问题是初始容量16太小了，可能中间需要不断扩容的问题，会影响插入的效率。
HashMap(int)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
用这种构造函数创建HashMap的对象，如果知道map要存放的元素个数，可以直接指定容量的大小， 减除不停的扩容，提高效率
内部调用下述的构造方法
HashMap(int , float)
public HashMap(int initialCapacity, float loadFactor) {
// 检查输入初始容量是否合法
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// MAXIMUM_CAPACITY = 1 << 30;
// 传入的初始化容量 <=最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 检查输入加载因子是否合法
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// 取与cap最近的且大于cap的2的次方值
static final int tableSizeFor(int cap) {
int n = cap - 1;
// 执行或运算
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
先是对初始化容量、装载因子的合理性检测，之后进行赋值，loadFactor: 自定义值， 默认为0.75，threshold: 取与cap最近的且大于cap的2的次方值
总结
1. 为什么 threshold 要返回大于等于 initialCapacity 的最小 2 的 N 次方？
计算元素table中的位置的时候，概述中有讲，使用的是hash & (table.length-1) 而不是我们认为的 hash % table.length，而这两个方式在table.length是2的N次方的时候是等价的，从性能上而言，&性能更好，所以，仅需要满足数组的容量n尽可能为2的N次方即可。
2. 为什么给的是初始化容量， 计算的却是阀值，而不是容量？
1.8中， 将table的初始化放入了resize()中，并且在类属性中也注意到了没有capacity这个属性， 所以这里只能重新计算threshold，而resize()后面就会根据threshold来重新计算capacity，来进行 table数组的初始化，然后再重新按照装载因子计算threshold。
HashMap(Map<?extends K, ?extends V>)
// 将已有map m里的所有元素加入当前的map中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 核心 批量添加到table中
putMapEntries(m, false);
}
putMapEntries(m, false)
// 其实就是一个一个取出m中的元素调用putVal,一个个放入table中的过程。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// ① table为空。说明还没初始化，适合在构造方法的情况
if (table == null) { // pre-size
// +1.0F 的目的，是因为下面 (int) 直接取整，避免不够。
float ft = ((float)s / loadFactor) + 1.0F;
// 修正，防止超出
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 如果计算出来的 t 大于阀值，则计算新的阀值
if (t > threshold)
threshold = tableSizeFor(t);
}
// ② 如果 table 非空，说明已经初始化，需要不断扩容到阀值超过 s 的数量
else if (s > threshold)
resize();
// ③ 正常情况
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// 添加元素
putVal(hash(key), key, value, false, evict);
}
}
}
整体的意思就是必须保证新的map的table容量够，如何保证？确保原map的元素数量小于新map的threshold。
构造方法总结
- 若是不知道需要创建的map的容量大小，使用默认构造方法
- 默认的容量大小为16
- 若是能确定map的容量大小，可使用第二种构造方法
threshold的值为最小的大于输入容量的2的指数
- 将原
oldMap放入另一个newMap- 若
oldMap为空（没有元素） - 若是
oldMap不是新建的，其自身有一定容量- 确保
newMap能够容下oldMap， 不行进行扩容
- 确保
- 若
增、改
put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash(key)
static final int hash(Object key) {
int h;
//为了使计算出的hash更分散
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
JDK1.8哈希计算， 取得key的hashcode后，高16位与整个Hash异或运算重新计算hash值
putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 对应table数组
Node<K,V>[] tab;
// 对应位置的 Node 节点
Node<K,V> p;
// n table的长度
// 原tab中对应放入Node的位置
int n, i;
// 如果 table 未初始化，或者容量为 0 ，则进行扩容
// (第一次见这种赋值和判断融合的操作，学到了学到了)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果对应的位置的Node节点为空，则直接创建 Node 节点即可。
// (n-1)&hash 获取所在table的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 哈希冲突解决
// key 在 HashMap 对应的老节点
Node<K,V> e;
K k;
// hash相等 key相等 执行覆盖
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 为红黑树的节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 为Node节点，则说明是链表，且不是覆盖操作。需要遍历查找
else {
// 判断什么时候进行链表转红黑树，什么时候红黑树转链表
for (int binCount = 0; ; ++binCount) {
// 如果链表遍历完了都没有找到相同key的元素，说明该key对应的元素不存在，则在链表 // 最后插入一个新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表的长度如果数量达到 TREEIFY_THRESHOLD（8）时，则进行树化。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果待插入的key在链表中找到了，则退出循环
if (e.hash == hash&&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 覆盖操作， 也就是相同的key的value进行覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent进行判断是否需要覆盖oldValue
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果超过阀值，则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
总结
一下图片为putVal方法的总体逻辑
摘自 Hashmap源码解析
putAll(Map<? extends K, ? extends V> m)
public void putAll(Map<? extends K, ? extends V> m) {
this.putMapEntries(m, true);
}
putMapEntries在构造方法四中已经讲解了。
扩容机制
resize()
// 扩容方法
final Node<K,V>[] resize() {
// oldTab 表示当前的哈希桶
Node<K,V>[] oldTab = table;
// oldCap表示当前哈希桶的容量 length
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 当前哈希桶的阀值
int oldThr = threshold;
// 初始化新的容量和阀值
int newCap, newThr = 0;
// 1. 如果当前的容量不为空
if (oldCap > 0) {
// 如果当前的容量已经达到了上限
if (oldCap >= MAXIMUM_CAPACITY) {
// 阀值为2^32-1
threshold = Integer.MAX_VALUE;
// 返回当前的哈希桶不再扩容
return oldTab;
}
// 否者新的容量为原先容量的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)// 如果旧的容量大于等于默认的初始容量 16
// 新的阀值也为原先的两倍
newThr = oldThr << 1; // double threshold
}
// 2. 如果当前表是空的，但是有阈值。代表是初始化时指定了容量、阈值的情况(上述的第三种构造方法)
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr; // 新的容量为旧的阀值
// 3. 此处的判断用于初始化
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的阈值是0，对应的是 当前表是空的，但是有阈值的情况
if (newThr == 0) {
//根据新表容量 和 加载因子 求出新的阈值
float ft = (float)newCap * loadFactor;
// 进行越界修复
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新阀值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 更新哈希桶的引用
table = newTab;
// 如果以前的哈希桶有元素
// 以下执行将原哈希桶中的元素转入新的哈希桶中
if (oldTab != null) {
// 遍历老的哈希桶
for (int j = 0; j < oldCap; ++j) {
// 取出当前的节点e
Node<K,V> e;
// 如果当前桶中有元素, 则将链表复制给e
if ((e = oldTab[j]) != null) {
// 将原哈希桶置空以便GC
oldTab[j] = null;
// 当前链表中只有一个元素, 没有发生哈希碰撞
if (e.next == null)
//直接将这个元素放置在新的哈希桶里。
//注意这里取下标 是用 哈希值 与 桶的长度-1 。
//由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高
newTab[e.hash & (newCap - 1)] = e;
// 发生碰撞, 而且节点的个数超过8, 则转化为红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//发生碰撞, 节点个数＜8 则进行处理, 依次放入新的哈希桶对应的下标位置
//因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下 //标,即low位， 或者扩容后的下标，即high位。 high位=low位+原哈希桶容量
else { // preserve order
//低位链表的头结点、尾节点
Node<K,V> loHead = null, loTail = null;
//高位链表的头结点、尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成高位链表和低位 链表以完成rehash
do {
next = e.next;
//这里又是一个利用位运算 代替常规运算的高效点： 利用哈希值与旧的容量，
//可以得到哈希值取模后，是大于等于oldCap还是小于oldCap，等于0代表小于 //oldCap，应该存放在低位，否则存放在高位
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结
步骤:
- 如果使用的是默认构造方法, 则第一次插入元素的时候初始化为默认的容量16, 扩容阀值为12
- 如果使用的是非默认方法, 则第一次插入元素时初始化容量为扩容阀值, 扩容的阀值为初始化的时候, 扩容门槛在构造方法里等于传入容量向上最近的2的n次方
- 如果旧容量＞0, 则新容量为旧容量的2倍, 但不超过最大容量($2^{30}$), 新的扩容阀值为旧的扩容阀值2倍
- 创建新的容量桶
- 搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置
删
remove(Object key)
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// 这些和增里面是差不多的
// tab：桶数组 p：待删除节点的前驱节点 n: 桶数组大小 index: 桶数组第i个位置
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null&&(n = tab.length)>0 &&(p=tab[index=(n-1)&hash])!= null) {
// node为需要删除的节点
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 找到对应的key进行remove核心
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 如果node == p，说明是链表头是待删除节点
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
除去复杂的判断，也就是单链表删除指定的节点，共有两种情况： 1.删除的为头结点。2. 删除的为中间节点
remove(Object key, Object value)
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
查
get(Object key)
public V get(Object key) {
HashMap.Node e;
return (e = this.getNode(hash(key), key)) == null ? null
}
// 根据key获取对应的节点
final HashMap.Node<K, V> getNode(int hash, Object key) {
HashMap.Node[] tab;
HashMap.Node first;
int n;
if ((tab = this.table) != null && (n = tab.length) > 0 && (first = tab[n - 1 & hash]) != null) {
Object k;
if (first.hash == hash && ((k = first.key) == key || key != null && key.equals(k))) {
return first;
}
HashMap.Node e;
if ((e = first.next) != null) {
if (first instanceof HashMap.TreeNode) {
return ((HashMap.TreeNode)first).getTreeNode(hash, key);
}
do {
if (e.hash == hash && ((k = e.key) == key || key != null && key.equals(k))) {
return e;
}
} while((e = e.next) != null);
}
}
return null;
}
使用
first.hash == hash && ((k = first.key) == key || key != null && key.equals(k))判断是否为同一个key(因为相同的hash可能并不是同一个key，因为先是使用(n - 1) & hash寻找桶的位置，之后再依次查找key)
Note
负数的二进制表示:
- 取绝对值求二进制 获得原码
- 之后各个位取反获得反码
- 反码在最后一位＋1获得补码
- 补码极为负数的表示
>>>和>>的区别
>>>适合高位的运算低位运算两者无区别
hashCode与equals的深入理解
>
>
hashCode 的常规协定是：
在 Java 应用程序执行期间，在同一对象上多次调用 hashCode 方法时，必须一致地返回相同的整数，==前提是对象上 equals 比较中所用的信息没有被修改。==从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。
==如果根据 equals(Object) 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。==
以下情况不是必需的：如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是，程序员应该知道，为不相等的对象生成不同整数结果可以提高哈希表的性能。
实际上，由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。（这一般是通过将该对象的内部地址转换成一个整数来实现的，但是 JavaTM 编程语言不需要这种实现技巧。）==当equals方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。==
- hashCode的存在主要是用于查找的快捷性,如HashTable, HashMap等. 用来在散列存储数据结构中确定对象的存储地址的.
若是两个对象相同,那么equals(java.lang.Object)方法为true, 那么两个对象的hashCode必须相同.
如果对象的equals方法被重写，那么对象的hashCode也尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违反上一条.
两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里”。
==hashCode是用于查找使用的，而equals是用于比较两个对象的是否相等的==
底层数据结构分析
一些操作符号解析
- ^ 异或
- >>> 向右移动xxx位, 无视符号, 高位填0，不能左移
- >> 同理右移xxx位, 能左移
总结&面试相关问题
HashMap是一种散列表, 使用(数组+链表+红黑树)的结构
HashMap的默认初始容量为16, 默认装载因子为0.75, 且容量总是$2^n$
正常情况下, 扩容为原来的两倍
桶的长度小于64 时, 不会进行树化
桶的长度大于64且链表长度大于8时, 进行树化
当单个桶中的元素小于6时, 进行反树化(转化为链表)
查询时间为$O(1)$ 添加时间$O(1)$
1.判断key，根据key算出索引。
2.根据索引获得索引位置所对应的键值对链表。
3.遍历键值对链表，根据key找到对应的Entry键值对。
4.拿到value。
分析：
以上四步要保证HashMap的时间复杂度O(1)，需要保证每一步都是O(1)，现在看起来就第三步对链表的循环的时间复杂度影响最大，链表查找的时间复杂度为O(n)，与链表长度有关。我们要保证那个链表长度为1，才可以说时间复杂度能满足O(1)。但这么说来只有那个hash算法尽量减少冲突，才能使链表长度尽可能短，理想状态为1。因此可以得出结论：HashMap的查找时间复杂度只有在最理想的情况下才会为O(1)，HashMap是非线程安全的
HashMap的线程不安全在哪儿
- 在JDK1.7之前的版本会出现死循环的问题
- 数据覆盖问题
- A, B两个线程都需要put操作, 然后当A, B线程都获得了尾节点之后, A的时间片用完了, B开始执行尾插, 之后A再执行, 这时A获取的还是旧的尾部节点 , 所以就会导致数据被覆盖, B插入的数据丢失
解决线程安全问题:
Collections.SynchronizedMap()Map<String, Integer> testMap = new HashMap<>(); ... // 转为线程安全的map Map<String, Integer> map = Collections.synchronizedMap(testMap);
- 使用ConcurrentHashMap
references
- 数据结构与算法之美
- Java-Guid
- jdk-source-analysis
