通读HashMap源码(JDK8)

Hashmap数据结构

数组+链表+红黑树，桶中可能是链表，也可能是红黑树，引入红黑树是为了提高效率。

源码中的属性定义

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    //***，序列化的时候使用。
    private static final long serialVersionUID = 362498820763181265L;
    /**默认容量，1向左移位4个，00000001变成00010000，也就是2的4次方为16，使用移位是因为移位是计算机基础运算，效率比加减乘除快。**/
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //最大容量，2的30次方。
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //加载因子，用于扩容使用。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //当某个桶节点数量大于8时，会转换为红黑树。
    static final int TREEIFY_THRESHOLD = 8;
    //当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
    static final int UNTREEIFY_THRESHOLD = 6;
    //当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
    static final int MIN_TREEIFY_CAPACITY = 64;
    //存储元素的数组，transient关键字表示该属性不能被序列化
    transient Node<K,V>[] table;
    //将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
    transient Set<Map.Entry<K,V>> entrySet;
    //元素数量
    transient int size;
    //统计该map修改的次数
    transient int modCount;
    //临界值，也就是元素数量达到临界值时，会进行扩容。
    int threshold;
    //也是加载因子，只不过这个是变量。
final float loadFactor;  

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() {  //空构造函数，默认负载因子0.75，默认初始容量16
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

Put实现添加元素

1. 建立一个空的Hash数组
2. 获取需要的长度，进行扩容
3. 若计算出的Hash桶的位置没有值，则把key-value放到该位置上，把首节点赋值给p
4. 若发生hash冲突
5. Hash值key值都相等，e=p，表示为首节点
6. Hash值不等于首节点，判断是否为红黑树节点
   是红黑树节点则在红黑树中进行添加，节点已存在返回节点，不存在put成功返回null
7. 既不是首节点，也不是红黑树，判断是链表节点
   遍历链表找是否有重复的key，如果找到尾部也没找到，就说明没有重复的，在链表尾部增加元素；如果链表中有重复的key，则p为当前重复的节点，结束循环
8. 总判断，若有重复的key，则用待插入值进行覆盖，返回旧值
9. 此时，若key没有重复，插入成功，修改次数+1，实际长度+1，根据实际长度判断是否扩容并按情况进行处置
10. 添加成功，返回null

扩容方法resize：

计算hashmap中元素个数，当个数超过 数组大小*负载因子 时，将数组的大小增加一倍，重新计算每个元素在数组中的位置

删除方法 remove

1. Node 要删除的节点
2. 如果是数组的下标节点，直接把节点赋值给node
3. 如果是红黑树节点，遍历得到节点并赋值
4. 如果是链表节点，遍历得到节点并赋值
5. 找到最终要删除的节点node
6. 如果是普通节点，直接删除
7. 如果是红黑树节点，红黑树中删除
8. 如果是链表节点，若在数组上(链表头结点)，让链表下一个元素作为头；若在链表上，让链表要删除的节点的下一个节点做为上一个节点的下一节点
9. 修改计数器(-1) 长度size(-1)
10. 删除成功返回删除的节点，删除失败(没有找到节点)返回值为null

获取元素方法get

头节点(数组内)直接返回；不是头节点，是红黑树或链表，遍历获取。

修改元素
也用put方法，直接根据key进行修改，新值覆盖旧值即可

源码可于idea查看