Map.HashMap
Map.HashMap

Map.HashMap
• 发表于 10个月前
• 阅读 8
• 收藏 0
• 评论 0

# HashMap jdk8

• 构造函数，负载因子默认0.75F，影响map扩容//TODO，提供根据参数计算负载因子
• 继承`AbstractMap`，实现`Map`，大部分API都在`AbstractMap`抽象类中模板方法实现
``````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;
}
``````
• put，hashMap中维护了一个数组，其中存放链表。超过8则转换为红黑树。
``````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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据table的长度位算法（i = (n - 1) & hash）分配一个index，空则填入node
//@one
if ((p = tab[i = (n - 1) & hash]) == null)
//没有hash碰撞的情况下，put完毕
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//新k-v全等于已有元素，进入@four覆盖
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);
else {
//
for (int binCount = 0; ; ++binCount) {
//@two，相同hash值，添加为链表下一节点
//有hash碰撞的情况下，put完毕
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 = e;
}
}
//@four 覆盖已有值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//防止foreach异常//TODO
++modCount;
if (++size > threshold)
//重新分配map
resize();
afterNodeInsertion(evict);
return null;
}
``````
• get
``````    public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//同put算法(n - 1) & hash，定位数组中相同hash的链表
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//这里always check是，可能大部分情况hashMap碰撞情况很小
if (first.hash == hash && // always check first node
((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 {
//开始遍历相同hash的链表，直到找到为止
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
``````
• EntrySet
• entrySet返回`Set<Node>`结构，真正在遍历map时，会遍历`HashMap``table[]`，Node链表。见`nextNode();`
``````public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size()                 { return size; }
public final void clear()               { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
//table[]赋值
if ((next = (current = e).next) == null && (t = table) != null) {
//真正遍历table[] ，链表
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
``````
• KeySet,values，同理，`nextNode();`遍历节点，取值
``````final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
``````
• TODO map扩容

×