JDK1.8HashMap源码分析
HashMap和Hashtable的主要区别是： 1. Hashtable是线程安全，而HashMap则非线程安全，Hashtable的实现方法里面大部分都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些，在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。
2. HashMap的键和值都可以为null，而Hashtable的键值都不能为null。
3. HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75。HashMap扩展容量是当前容量翻倍即:capacity*2，Hashtable扩展容量是容量翻倍+1即:capacity*2+1（关于扩容和填充因子后面会讲）
4. 两者的哈希算法不同，HashMap是先对key(键)求hashCode码，然后再把这个码值得高位和低位做异或运算，源码如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
i = (n - 1) & hash然后把hash（key）返回的哈希值与HashMap的初始容量(也叫初始数组的长度)减一做&（与运算）就可以计算出此键值对应该保存到数组的那个位置上(hash&（n-1）)。
而Hashtable计算位置的方式如下：
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;直接计算key的哈希码，然后与2的31次方做&（与运算），然后对数组长度取余数计算位置。
hashMap的一些重要属性：
/默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转成红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
//红黑树转为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//存储方式由链表转成红黑树的容量的最小阈值
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap中存储的键值对的数量
transient int size;
//扩容阈值，当size>=threshold时，就会扩容
int threshold;
//HashMap的加载因子
final float loadFactor;接下来是HashMap的put和remove源码分析
HashMap结构就是Node数组，Node源码：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V 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; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(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;
}
}put源码分析：
final V putVal ( int hash, K key, V value,boolean onlyIfAbsent,
boolean evict){
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//第一次调用的时候，数组长度为零，调用resize(),此时数组长度变为16
if ((p = tab[i = (n - 1) & hash]) == null)//根据传入的hash值，算出Node所在的数组标，拿出Node,如果为空表示当前数组还没有链表，创建新的节点放在数组这个位置
tab[i] = newNode(hash, key, value, null);
else {//若取出的节点p不为空
HashMap.Node<K, V> e;
K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//只有当取出的节点hash值与Key都与传参一样时才认为两个Node为同一个
e = p;// e指向原有的Node
else if (p instanceof HashMap.TreeNode)//如果找到的当前节点不是key对应的Node,且为TreeNode，执行treeNode的put逻辑
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {// binCount 用来记录当前链表长度
if ((e = p.next) == null) {//如果当前Node 不是我们要找的，遍历这个链表数据
p.next = newNode(hash, key, value, null);//如果节点的下一个节点为空，创建新的节点，放在现有的节点后面
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st，如果链表长度 >= 8 ,则将链表转换为红黑树
treeifyBin(tab, hash);//转换为红黑树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//如果当前节点的下一个节点就是我们要找的元素，直接跳出for循环，e是最终要找的Node
break;
p = e;
}
}
if (e != null) { // existing mapping for key,如果e不为空，表示找到了对应的节点
V oldValue = e.value;//oldValue 用户存储老的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;//将新值覆盖原有的值
afterNodeAccess(e);
return oldValue; // 找到对应的节点以后，返回值为旧value
}
}
//以下代码为只有当e为空，也就是没有找到相匹配的key值得地方，这是就创建了一个新的Node，添加到某个链表后面
++modCount;// modCount 用于记录map 被修改了多少次
if (++size > threshold)// size 表示当前map 有多少个 Node,添加一个元素Node
resize();//当添加了一个Node以后 size 如果大于 承载量 则进行扩容
afterNodeInsertion(evict);
return null;//如果没有找到你对应的节点，执行新增操作，返回null
}remove源码分析：
final HashMap.Node<K, V> removeNode ( int hash, Object key, Object value,
boolean matchValue, boolean movable){
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {//根据hash值定位到要移除的元素位置
HashMap.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;//如果找到了对应的元素，让临时变量node指针指向被删除元素
else if ((e = p.next) != null) {//如果当前节点没有找到，则向下遍历链表
if (p instanceof HashMap.TreeNode)//如果是TreeNode ，将节点强制转换为TreeNode
node = ((HashMap.TreeNode<K, V>) p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {//遍历整个链表，如果找到要删除的节点就将node指针指向该节点
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//如果node不为空，则表示找到了要删除的节点
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {//该节点值与要删的节点value一致，执行删除动作
if (node instanceof HashMap.TreeNode)//如果当前节点是treeNode，则执行treeNode的删除逻辑
((HashMap.TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
else if (node == p)//如果当前节点就是要删除的节点，则把节点的下一个节点放在数组位置，类似于把头给掐断
tab[index] = node.next;
else//如果要删除节点不在头部的话，这种情况下，p始终为要删除节点的前一个节点
p.next = node.next;//将p节点的next指针指向node的下一个节点，即将node节点删除
++modCount;//统计map被修改的次数
--size;//map的 Node 个数减一
afterNodeRemoval(node);
return node;//返回被删除的Node节点
}
}
return null;//如果没找到被删除节点 ，返回null
}扩容源码分析：
final HashMap.Node<K,V>[] resize() {
HashMap.Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧的容量，即数组长度
int oldThr = threshold;//旧的承载量
int newCap, newThr = 0;//声明两个变量存储新的容量和装载量
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {//如果旧的容量大于容量最大值，不进行扩容，将Integer最大值给装载容量
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)//将原有容量扩容一倍，但不能超过最大容量
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;//如果容量为零（数组为空）但承载量不为0，表示map中以前有过元素,将承载量赋值给容量
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;// 第一次调用方法的时候初始化容量，16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//初始化承载量，容量*0.75（承载因子）
}
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"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
table = newTab;//将原有节点数组指向根据新的容量创建新的节点数组
if (oldTab != null) {//如果原有数组不为空，则将数组上的每一个链表都拆分为两份，一份存储在原有数组位置，一部分存储在新扩容的数组位置，让节点元素保持均匀分布
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode)
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.Node<K,V> next;
do {
next = e.next;
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;
}其中，为什么扩容耗时就很明显了，扩容的流程是将原有数组扩大一倍，将数组上的每一个链表一分为二，均匀地分布在数组上，而java8有引进了红黑树，当链表长度大于8时，将链表转换为红黑树，这样大大加快了get（key）的速度。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018/10/16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读