189 8069 5689
这篇文章给大家分享的是有关Java中HashMap的案例分析的内容。小编觉得挺实用的，因此分享给大家做个参考。一起跟随小编过来看看吧。
HashMap 是数组和链表组合组成的复杂结构，哈希值决定了键值在数组的位置，当哈希值相同时则以链表形式存储，当链表长度到达设定的阈值则会对其进行树化，这样做是为了保证数据安全和数据相关操作的效率
HashMap 性能表现取决于哈希码的有效性，所以 hashCode 和 equals 的基本约定规则尤为重要，如：equals 相等，hashCode 一定要相等；重写了 hashCode 也要重写 equals；hashCode 需要保持一致性，状态改变返回的哈希值仍然要一致；equals 的对称、反射、传递等特性
HashMap 与 Hashtable、TreeMap 的区别
HashMap：基于数组的非同步哈希表，支持 null 键或值，是键值对存取数据场景的选
Hashtable：基于数组的同步哈希表，不支持null键或值，因为同步导致性能影响，很少被使用
TreeMap：基于红黑树提供顺序访问的 Map，比 HashMap 节省空间，但它的数据操作（查、增、删）时间复杂度均为：O（log(n)），这点与 HashMap 不同。支持空值，当键为空时且未实现 Comparator 接口，会出现 NullPointerException ，实现了 Comparator 接口并对 null 对象进行判断可实现正常存入
HashMap、Hashtable、TreeMap 均以键值对形式存储或操作数据元素。HashMap、TreeMap 继承自 AbstractMap 类，Hashtable 继承自 Dictionary 类，三者均实现 Map 接口
HashMap 源码解析
HashMap()
public HashMap(int initialCapacity, float loadFactor){
// ...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}初始化 HashMap 时仅设置了一些初始值，但在开始处理数据时，如 .put() 方法内渐渐开始复杂起来
HashMap.put()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 定义新tab数组及node对象
Node[] tab; Node p; int n, i;
// 如果原table是空的或者未存储任何元素则需要先初始化进行tab的初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 当数组中对应位置为null时，将新元素放入数组中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 若对应位置不为空时处理哈希冲突
else {
Node e; K k;
// 1 - 普通元素判断： 更新数组中对应位置数据
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 2 - 红黑树判断：当p为树的节点时，向树内插入节点
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// 3 - 链表判断：插入节点
else {
for (int binCount = 0; ; ++binCount) {
// 找到尾结点并插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判断链表长度是否达到树化阈值，达到就对链表进行树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 更新链表中对应位置数据
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果存在这个映射就覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 回调以允许LinkedHashMap后置操作
afterNodeAccess(e);
return oldValue;
}
}
// 更新修改次数
++modCount;
// 检查数组是否需要进行扩容
if (++size > threshold)
resize();
// 回调以允许LinkedHashMap后置操作
afterNodeInsertion(evict);
return null;
} 当 table 为 null，会通过 resize() 初始化，且 resize() 有两个作用，一是创建并初始化 table ，二是在 table 容量不满足需求时进行扩容：
if (++size > threshold)
resize();具体的键值对存储位置计算方法为：
if ((p = tab[i = (n - 1) & hash]) == null)
// 向数组赋值新元素
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
// 如果新插入的结点和table中p结点的hash值，key值相同的话
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果是红黑树结点的话，进行红黑树插入
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 代表这个单链表只有一个头部结点，则直接新建一个结点即可
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度大于8时，将链表转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 及时更新p
p = e;
}
}
// 如果存在这个映射就覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 回调以允许LinkedHashMap后置操作
return oldValue;
}
} 留意 .put() 方法中的 hash 计算，它并不是 key 的 hashCode ，而是将 key 的 hashCode 高位数据移位到低位进行异或运算，这样一些计算出来的哈希值主要差异在高位时的数据，就不会因 HashMap 里哈希寻址时被忽略容量以上的高位，那么即可有效避免此类情况下的哈希碰撞
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}HashMap.resize()