下面参考的文章比较详细，可以参考参考链接中的文章。
HashMap的简介
HashMap的数据结构是数组+链表，但是如果当链表的长度大于8的且数组大小大于64时，链表的结构转变为红黑树结构。
HashMap初始默认长度为16,超出时进行扩容2倍，填充因子。
HashMap支持动态扩容的数组，基于数组、链表、红黑树实现的结合。
HashMap支持键值对，克隆，序列化，元素无序，key不可重复Value可重复。都可以为null,但是key只能允许出现一次。
源码分析的内容
这次的源码分析只是对以下几部分的内容进行总结和分析，详情请参考参考链接。
put()的方法
get()的方法
扩容
put(K,V)方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
使用put函数添加元素时，调用的方法是上面的方法，可以看到上面通过一个hash()的方法对key进行处理，我们看一下这个hash()方法。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
该方法返回的是整型，从这个方法可以看出，当key为null时，在HashMap的数组结构中位置是0,这个方法返回的是整型，看一看到这个方法是如何进一步处理hashCode的值的，通过先对h进行右移16类，再进行异或的运算。HashMap中数组下标的计算方式是(n - 1) & hash。接下来我们继续看一下putVal（）。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//将tab赋值table，如果数组的长度为0，或者为空，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
//扩容，并且返回长度
n = (tab = resize()).length;
//计算出该元素在数组那个位置，计算方式i = (n - 1) & hash]
if ((p = tab[i = (n - 1) & hash]) == null)
//如果为空，直接方法在改位置
tab[i] = newNode(hash, key, value, null);
else {
//如果不为空的处理方法。
Node<K,V> e; K k;
//比较该位置的节点的key是否相等，在这个判断中主要的作用是判断该位置的节点的
//元素的key是否相等，这里将引用类型和值类型都比较了，如果两者中只要有一个是true的就说明
//key是相等的。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//用e记录原来位置的值
e = p;
else if (p instanceof TreeNode)
//如果是红黑树的处理方式
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果key与存在的元素不相等
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;
}
//如果下一个元素的key于存放的key相等，退出循环，并且e节点是要代替的位置
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//继续遍历
p = e;
}
}
//判断e不为null，说明需要代替值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//对值进行替代
e.value = value;
afterNodeAccess(e);
//返回旧的值
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
现在重新屡一下put函数的逻辑：
向HashMap中put元素时，通过hash()方法，计算Key的hash值，如果key为null返回的hash值为0，这个hash值的作用是决定元素在数组中的位置。如果数组在改位置上没有元素，则直接保存。如果有元素，还需要进一步比较数组该位置上的的元素的key是相等，如果相等的话，则对值进行替换。如果没有存在相同的Key则保存在链表尾部，先存在的保存在链头。
get()的方法
get的方法相对比较简单，接下来分析一下getNode()的方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
重点是要返回getNode(hash(key), key)的方法，返回需要找到的节点，接下来重点分析getNode(hash(key), key)的方法。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//通过计算到的Hash值，判断是数组中是否存在改元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//比较第一个节点，判断Key是否相等，如果相等的直接返回
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 {
//通过遍历该位置的链表找到相等的Key,然后进行返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
总结一下get方法的思路：
从HashMap中get元素 时，计算key的hash值，并且根据hash值找到数组的下标，如果该key与数组的中的链接第一个节点的key相同，则直接返回，如果发生冲突，则遍历链表寻找与Key相同的节点，并返回。
扩容
final Node<K,V>[] resize() {
//oldTab指向数组
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;
}
//如果oldCap的两倍比最大容量小，且oldCap大于了默认的长度，16
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;
else { // zero initial threshold signifies using defaults
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指向新建长度为newCap的数组。
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//设置为null，方便gc
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 { // preserve order
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 {
//原索引+oldCap的位置上。
if (hiTail == null)
hiHead = e;
else
//在尾部进行添加
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
//设置尾部的下一个节点为null
loTail.next = null;
//设置该位置的链表值
newTab[j] = loHead;
}
if (hiTail != null) {
//设置尾部的下一个节点null
hiTail.next = null;
//设置该位置的链表值
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap的反复扩容，复杂度会越来越大，影响性能效率，HashMap默认的负载因子是0.75，长度为16.如果数组的长度大于阀值（16x0.75）x12的时候候就好扩容，所以在初始化HashMap的时候如果大概知道长度的，可以设置初始长度。
网友评论