1.概念解释
最近在看Java集合的底层源码实现，打算挑几个重要的内容写个小结，也对比学习了很多篇博客，如有错误，还望指出，不胜感激。
HashMap是一个数组+链表的实现，数组中存储了所有的头结点，每个头结点所在的一格称为一个桶，桶后面存放的每一个数据称为bin。
HashMap由数组+链表组成，数组是HashMap的主体，当添加一个元素时，通过key计算hash值，并确定插入数组中的位置。如果插入的位置已经有元素存在，则通过equals方法进一步判断，若返回true则覆盖该位置上的Node，若返回false则添加到该元素的后面形成了链表。当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。
JDK 1.8 以前的HashMapd的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。针对这种情况，JDK 1.8 引入了红黑树（查找时间复杂度为O(logn)）来优化这个问题，当同一个hash值的节点数不小于8时，不再采用单链表形式存储，而是采用红黑树的存储形式。
类的数据成员：
DEFAULT_INITIAL_CAPACITY：表示HashMap中桶的数量，即数组长度，默认值为16。每一次扩容都是原来的2倍，总之，容量都是2的幂。
/**
*The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
DEFAULT_LOAD_FACTOR：表示装载因子，用来衡量HashMap满的程度，其默认值为0.75f，计算装载因子的公式为：size / capacity，并非用占用桶的数量除以capacity。
/**
*The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
threshold：threshold表示临界值，当HashMap的size大于threshold时会执行resize操作。threshold = capacity * loadFactor。
size：表示HashMap中存放的key-value键值对的个数。
TREEIFY_THRESHOLD：当桶上的结点大于这个值时，链表就会转成红黑树。
UNTREEIFY_THRESHOLD：当桶上的结点小于这个值时，红黑树就会转回链表。
MIN_TREEIFY_CAPACITY：桶中结构转化为红黑树对应的table的最小大小。
transient Node<K,V>[] table：存放元素的数组，总是2的幂次倍。
transient Set<map.entry<K,V» entrySet：存放具体元素的值。
2.基本方法
public class HashMapTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
HashMap<String, String> hashMap = new HashMap<>();
//添加方法
hashMap.put("1", "string1");
//遍历方法1
Set<String> keys = hashMap.keySet();
for(String key :keys){
System.out.println(key + " = " + hashMap.get(key));
}
//遍历方法2
Set<Entry<String, String>> entrys = hashMap.entrySet();
for(Entry<String, String> entry : entrys){
String key = entry.getKey();
String value = entry.getValue();
System.out.println(key + " = " + value);
}
//遍历方法3(for和iterator实现原理相同)
Iterator iter = hashMap.keySet().iterator();
while (iter.hasNext()) {
String key = (String) iter.next();
String value = hashMap.get(key);
System.out.println(key + " = " + value);
}
//遍历方法4
Iterator<Entry<String, String>> iterator = hashMap.entrySet().iterator();
while(iterator.hasNext()){
Entry<String, String> entry = iterator.next();
String key = entry.getKey();
String value = entry.getValue();
System.out.println(key + " = " + value);
}
//查询方法
System.out.println(hashMap.get("1"));
//删除方法
hashMap.remove("1");
}
}
3.源码分析
1.HashMap<String, String> hashMap = new HashMap<>();
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能<0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子不能 < 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
class Node<K,V>是HashMap的一个内部类，实现了Map.Entry<K,V>接口。
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;
}
//判断两个Node是否相等，如果key和value都相等则返回true
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;
}
}
HashMap其实就是一个Entry（Node）数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。
2.红黑树
//红黑树
static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
TreeNode<k,v> parent; // 父节点
TreeNode<k,v> left; //左子树
TreeNode<k,v> right;//右子树
TreeNode<k,v> prev;// needed to unlink next upon deletion
boolean red;//颜色属性
TreeNode(int hash, K key, V val, Node<k,v> next) {
super(hash, key, val, next);
}
//返回当前节点的根节点
final TreeNode<k,v> root() {
for (TreeNode<k,v> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
红黑树比链表多了四个变量，parent父节点、left左节点、right右节点、prev上一个同级节点。
桶的树形化：
(1)根据哈希表中元素个数确定是扩容还是树形化；
(2)如果是树形化遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系；
(3)然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容。
//将桶内所有的链表结点替换成红黑树结点
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index;
Node<K,V> e;
//如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为64)，就去新建/扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//如果哈希表中的元素个数超过了树形化阈值，进行树形化
//e是哈希表中指定位置桶里的链表结点，从第一个开始
TreeNode<K,V> hd = null, tl = null;//红黑树的头、尾结点
do {
//新建一个树形结点，内容和当前链表结点e一致
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)//确定树头结点
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
3.hashMap.put(“1”,”string1”);
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
当我们调用put存值时，HashMap首先会获取key的哈希值，通过哈希值快速找到某个存放位置，这个位置可以被称之为bucketIndex。
对于一个key，如果hashCode不同，equals一定为false，如果hashCode相同，equals不一定为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;
//若table未初始化或长度为0，则进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//计算index,并对null做处理
//(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;
//比较桶中第一个节点的hash值和key值，若相等则覆盖
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;//将第一个元素赋值给e，用e来记录
else if (p instanceof TreeNode)//判断该链是否为红黑树
e = ((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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//判断链表中结点的key值与插入元素的key值是否相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//表示在桶中找到key值和hash值与插入元素相等的结点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//修改次数+1
//超过阈值则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
数据存储实现原理流程小结：
根据key计算得到key.hash = (h = k.hashCode()) ^ (h »> 16)；
根据key.hash计算得到桶数组的索引index = key.hash & (table.length - 1)，这样就找到该key的存放位置了：
① 如果该位置没有数据，用该数据新生成一个节点保存新数据，返回null；
② 如果该位置有数据是一个红黑树，那么执行相应的插入 / 更新操作；
③ 如果该位置有数据是一个链表，分两种情况一是该链表没有这个节点，另一个是该链表上有这个节点，注意这里判断的依据是key.hash是否一样：如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，返回null；如果该链表已经有这个节点了，那么找到该节点并更新新数据，返回老数据。
4.hashMap.get(“1”);
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n;
K k;
// table已经初始化，长度大于0，根据hash寻找table中的项也不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 桶中第一项(数组元素)相等
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 {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
说明：HashMap并没有直接提供getNode接口给用户调用，而是提供的get函数，而get函数就是通过getNode来取得元素的。