1. HashMap 结构
HashMap 基于数组的形式存储节点,出现hash冲突后,以链表的形式存储元素。当链表的长度>8时,裂变为红黑树。
2. 重要字段
transient Node<K,V>[] table; Hash表结构transient int size; 元素个数,K,V个数int threshold; 下一次增容前的阈值。 超过将会扩容final float loadFactor; 加载因子threshold = size * loadFactorcapacity : 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; 链表转红黑树的阈值
2.1 补充
前提知识:
HashMap 是 一种 Map ,使用 HashCode 进行索引等相关操作,所以叫 HashMapHashCode 是一个 native 方法 ,详见 java.lang.Object#hashcode()不同的 JVM 对 native 方法 有不同的实现。
因此,当一个 HashMap 序列化后,被另外一个(不同的) JVM 进行反序列化时:
由于不同的JVM 的 HashCode 的策略有所不同,使用原来 JVM 上计算的 HashCode 值在另外一个 JVM 上计算会引起错误。
所以,如果要序列化一个 HashMap ,需要剔除 hashcode 的影响,所以属性标识成了 transient 类型。
3. 常用方法
3.1 构造方法
public HashMap(int initialCapacity
, float loadFactor
) {
if (initialCapacity
< 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity
);
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
);
}
public HashMap(int initialCapacity
) {
this(initialCapacity
, DEFAULT_LOAD_FACTOR
);
}
public HashMap(Map
<? extends K, ? extends V> m
) {
this.loadFactor
= DEFAULT_LOAD_FACTOR
;
putMapEntries(m
, false);
}
主要是完成容量和加载因子的赋值。采用懒加载的方式,只有第一次插入数据时才会被赋值。
3.2 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
) {
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
;
if ((p
= tab
[i
= (n
- 1) & hash
]) == null
)
tab
[i
] = newNode(hash
, key
, value
, null
);
else {
HashMap
.Node
<K, V> e
;
K k
;
if (p
.hash
== hash
&&
((k
= p
.key
) == key
|| (key
!= null
&& key
.equals(k
))))
e
= p
;
else if (p
instanceof HashMap.TreeNode)
e
= ((HashMap
.TreeNode
<K, V>) 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
);
if (binCount
>= TREEIFY_THRESHOLD
- 1)
treeifyBin(tab
, hash
);
break;
}
if (e
.hash
== hash
&&
((k
= e
.key
) == key
|| (key
!= null
&& key
.equals(k
))))
break;
p
= e
;
}
}
if (e
!= null
) {
V oldValue
= e
.value
;
if (!onlyIfAbsent
|| oldValue
== null
)
e
.value
= value
;、
afterNodeAccess(e
);
return oldValue
;
}
}
++modCount
;
if (++size
> threshold
)
resize();
afterNodeInsertion(evict
);
return null
;
}
3.3 get
public V
get(Object key
) {
Node
<K,V> e
;
return (e
= getNode(hash(key
), key
)) == null
? null
: e
.value
;
}
final Node
<K,V> getNode(int hash
, Object key
) {
Node
<K,V>[] tab
; Node
<K,V> first
, e
; int n
; K k
;
if ((tab
= table
) != null
&& (n
= tab
.length
) > 0 &&
(first
= tab
[(n
- 1) & hash
]) != null
) {
if (first
.hash
== hash
&&
((k
= first
.key
) == key
|| (key
!= null
&& key
.equals(k
))))
return first
;
if ((e
= first
.next
) != null
) {
if (first
instanceof TreeNode)
return ((TreeNode
<K,V>)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
;
}
3.4 resize
final Node
<K,V>[] resize() {
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
) {
threshold
= Integer
.MAX_VALUE
;
return oldTab
;
}
else if ((newCap
= oldCap
<< 1) < MAXIMUM_CAPACITY
&&
oldCap
>= DEFAULT_INITIAL_CAPACITY
)
newThr
= oldThr
<< 1;
}
else if (oldThr
> 0)
newCap
= oldThr
;
else {
newCap
= DEFAULT_INITIAL_CAPACITY
;
newThr
= (int)(DEFAULT_LOAD_FACTOR
* DEFAULT_INITIAL_CAPACITY
);
}
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
) {
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 TreeNode)
((TreeNode
<K,V>)e
).split(this, newTab
, j
, oldCap
);
else {
Node
<K,V> loHead
= null
, loTail
= null
;
Node
<K,V> hiHead
= null
, hiTail
= null
;
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
;
}
3.5 remove
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
) {
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
<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
);
}
}
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
);
else if (node
== p
)
tab
[index
] = node
.next
;
else
p
.next
= node
.next
;
++modCount
;
--size
;
afterNodeRemoval(node
);
return node
;
}
}
return null
;
}