天天看点
返回

java基础-Java集合框架-Map接口-HashMap原理（jdk1.7和jdk1.8）Java集合框架-Map接口-HashMap原理和源码

Java集合框架-Map接口-HashMap原理和源码

HashMap底层实现原理

  • HashMap的put操作以jdk7为例说明
    • HashMap map = new HashMap():
    • 在实例化之后，底层创建了一个长度为16的一维数组Entry[] table。
    • …可能已经执行过多次put…
    • map.put(key1,value1);
    • 步骤：
      • 首先调用，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算后，得到在Entry数组中的存放位置。
      • 如果此位置上的数据为空，此时key1-value1添加成功。—情况1
      • 如果此位之上的数据不为空，（意味着此位置上存在一个或多个数据（以链表形式存在）），则比较key1和已经存在的一个或多个数据的哈希值（逐个比较链表上的key）：
        • 如果key1的哈希值与已经存在的数据的哈希值都不同，此时key1-value1添加成功。—情况2
        • 如果key1的哈希值和已经存在的某一个书序的哈希值相同，则继续比较：调用key1所在类的equals()方法，比较：
          • 如果equals()方法返回false，则key1-value1添加成功.—情况3
          • 如果equals()方法返回true，则将value1去替换相同key的vlaue值（修改操作了）
      • 补充：关于情况2和情况3，此时key1-value1和原来的数据以链表的方式存储
      • 在不断的添加过程中，会涉及到扩容问题，默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来
  • jdk8相较于jdk7在底层实现方面的不同：
    • new HashMap()：底层没有创建一个长度为16的数组
    • jdk 8 底层的数据时：Node[],而非Entry();
    • 首次调用put()方法时，底层创建长度为16的数组
    • jdk7底层结构只有：数组+链表。jdk8中底层结构：数据+链表+红黑树。
      • 当数组的某一个索引位置上的元素以链表形式存在的数据个数大于8
      • 且当前数组长度大于64时
        • 此时索引位置上的所有数据改为使用红黑树存储

HashMap的源码

HashMap源码中的重要常量

  • DEFAULT_INITIAL_CAPACITY:HashMap的默认容量，16
  • MAXIMUM_CAPACITY：HashMap的最大支持容量，2^30
  • DEFAULT_LOAD_FACTOR：HashMap的默认加载因子
  • TREEIFY_THRESHOLD：Buck中链表长度大于该默认值，转化为红黑树（树化阈值）
  • UNTREEIFY_THRESHOLD：Buck中红黑树存储的Node小于该默认值，转化为链表（去树化阈值）
  • MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。（当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行resize扩容操作。这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍）
  • table：存储元素的数组，总是2的n次幂
  • entrySet：存储具体元素的集
  • size：HashMap中存储的键值对的数量
  • modCount：HashMap扩容和结构改变的次数。
  • threshold：扩容的临界值，=“容量”填充因子
  • loadFactor：填充因子

具体构造器源码

  • jdk1.7 
  • /**
 * hashMap底层数组默认的初始化长度-必须是2的几次幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * hashMap底层数组的最大长度，取值范围在 2 - 2^30之间
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认负载因子值，用于计算hashMap底层数组扩容的扩容阈值，扩容阈值=数组长度*负载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 常量，一个空的长度为0的Entry数组
 */
static final Entry<?,?>[] EMPTY_TABLE = {};

/**
 * hashMap用于存储元素的底层数组，数组元素类为Entry<?,?>,数组长度必须，在HashMap类加载时
 * table初始化为EMPTY_TABLE,初始化是一个空的长度为0的Entry数组
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/**
 * map中的元素总个数
 */
transient int size;

/**
 * 扩容阈值，扩容阈值=负载因子*HashMap底层数组的长度 threshold=loadFactor * capacity
 */
int threshold;

/**
 * 负载因子，用于计算扩容阈值
 */
final float loadFactor;

/**
 * 表示hashmap扩容和结构改变次数
 */
transient int modCount;

/**
 *
 */
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
  • jdk1.8 
  • /**
     * hashMap底层数组默认的初始化长度-必须是2的几次幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * hashMap底层数组的最大长度，取值范围在 2 - 2^30之间
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认负载因子值，用于计算hashMap底层数组扩容的扩容阈值，扩容阈值=数组长度*负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 链表树化的阈值
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 红黑树退化成链表的阈值
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * HashMap中被树化时Node的最小容量
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * hashMap的底层数组，用于存储key-value对，在jdk1.8中用Node作为table的元素类型
     */
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * map中的元素总个数
     */
    transient int size;

    /**
     * 表示hashmap扩容和结构改变次数
     */
    transient int modCount;

    /**
     * 扩容阈值，扩容阈值=负载因子*HashMap底层数组的长度 threshold=loadFactor * capacity
     */
    int threshold;

    /**
     * 负载因子，用于计算扩容阈值
     */
    final float loadFactor;
  • HashMap的构造器
    • jdk1.7 
    • 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;
    threshold = initialCapacity;
    init();
}


public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}


public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);

    putAllForCreate(m);
}
    • jdk1.8 
    • 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() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

HashMap的对象创建和调用put方法源码流程

  • hashMap在jdk1.7版本下的对象创建和调用put方法的流程及源码
    • 创建HashMap对象
      • HashMap map = new HashMap<>();//使用空参的构造器创建 
      • public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
      • hashmap空参的构造器会调用HashMap(int initialCapacity, float loadFactor)构造器，传入的值为initialCapacity=DEFAULT_INITIAL_CAPACITY=16， loadFactor=DEFAULT_LOAD_FACTOR=0.75f
      • 在HashMap(int initialCapacity, float loadFactor)构造器中会先判断底层数组初始化容量initialCapacity是否小于0，如果小于0则抛出异常IllegalArgumentException("Illegal initial capacity: " +initialCapacity)
      • 然后判断初始化容量是否大于HashMap最大支持容量2^30，如果大于则将最大容量MAXIMUM_CAPACITY赋值给初始化容量initialCapacity
      • 接下来判断负载因子是否小于0，且是Float类型，如果不满足条件则抛出异常new IllegalArgumentException("Illegal load factor: " + loadFactor);
      • 然后将入参负载因子的赋值给属性loadFactor
      • 属性threshold扩容阈值为初始化容量initialCapacity
      • 接着调用init()方法，该方法在HashMap中为空方法 
      • 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;
    threshold = initialCapacity;
    init();
}
    • 调用put(K key, V value)调用逻辑
    • put方法调用链：
      • put(K key, V value)-> inflateTable(int toSize)->roundUpToPowerOf2(int number)->initHashSeedAsNeeded(int capacity)
      • put(K key, V value)->putForNullKey(V value)->addEntry(int hash, K key, V value, int bucketIndex)
      • put(K key, V value)->hash(Object k)->indexFor(int h, int length)->addEntry(int hash, K key, V value, int bucketIndex)
    • 步骤解析：
      • 调用put(K key,V value)方法，先判断当前底层数组是否为空
        • 如果为空则调用 inflateTable(int toSize)方法扩容底层数组
        • 在inflateTable(int toSize)方法内，
          • 先调用roundUpToPowerOf2(int number)，这里计算一个2的n次方的数组容量，默认为2的4次方，为16。赋值为capacity
          • 然后设置扩容阈值threshold为capacity * loadFactor, MAXIMUM_CAPACITY + 1两者的较小数，初始化hashmap底层数组table为new Entry[capacity]
          • 最后在inflateTable方法内调用initHashSeedAsNeeded()初始化hashSeed，用于计算hash值
        • 然后判断所添加的key-value键值对的key是否为null
          • 如果为null则调用putForNullKey(V value)方法
            • 在putForNullKey(V value)方法中，遍历hashmap数组索引0的位置下的链表（默认key=null的键值对，由于null无法调用hashcode取hash值，所以将0作为null的哈希值），存在table[0]的位置，循环链表下的元素，如果对比key是否等于null
            • 如果在table[0]下找到key==null的元素则，将新的value替换原来的值。返回旧值
            • 如果在table[0]下未找到key == null的元素，则调用addEntry(0,null,value,0);方法将新的key=null的Entry添加到table[0]的数组索引处
              • addEntry(int hash, K key, V value, int bucketIndex)方法中，先判断当前元素数量是否大于等于扩容阈值threshold，并且判断当前要添加的table[bucketIndex]位置上的元素是否不为空（如果不为空，则表示存在hash冲突），如果两个条件都满足调用resize(2 * table.length)将hashmap底层数组扩容原来的两倍
              • 在resize(int newCapacity)方法中先获取旧底层数组table赋值给变量Entry[] oldTable
              • 获取oldTable的长度，赋值给oldCapacity作为旧底层数组的长度，如果oldCapacity等于MAXIMUM_CAPACITY（hashmap的最大容量），则将扩容阈值赋值成Integer.MAX_VALUE，直接返回不进行扩容了。
              • 如果oldCapacity不等于MAXIMUM_CAPACITY，继续接下去的逻辑根据newCapacity创建新的Entry数组赋值给newTable变量
              • 接着调用transfer(Entry[] newTable, boolean rehash) 方法
              • 在transfer(Entry[] newTable, boolean rehash) 方法中两层循环遍历旧的hashmap底层数组，将旧数组+链表下的所有元素重新根据hash值调用indexFor(int h, int length) 方法，
              • indexFor(int h, int length) 方法内部是h & (length -1) 等同于h%length取余运算，目的是获取将不同哈希值都能映射到数组上
              • 将旧元素赋值到新元素后，将newTable变量赋值给hashmap对象的table作为新的hashmap，并且根据newCapacity * loaderFactor计算新的扩容阈值
              • 返回到addEntry方法的if ((size >= threshold) && (null != table[bucketIndex]))逻辑块中，根据key，调用hash(Object k)获取新的hash值,调用indexFor(int h, int length)计算key在新的bucket中的位置
              • 接着调用createEntry(int hash, K key, V value, int bucketIndex) 方法，
              • 在jdk7中createEntry(int hash, K key, V value, int bucketIndex使用头插法，将新元素Entry放入table[bucketIndex]位置，新元素Entry的next属性指向原来的table[bucketIndex]下的Entry。
        • 返回到put(K key, V value)方法中，如果key != null，则调用hash(Object o)方法计算key的hash值赋值给hash变量
        • 然后调用indexFor(int h, int length) 计算key在bucket中的位置。赋值给i
        • 循环hashmap底层数组table[i]的位置下的所有元素
          • 如果table[i]下没有元素，则跳出循环
          • 如果table[i]下有一个或多个元素，则遍历对比table[i]下的所有元素的key与添加的key是否相等
            • 循环中判断表中的元素e的hash值是否与添加的key的hash值相等，如果相等再判断两个key的值是否相等，如果key相等，则表示这是一次修改操作，将新的value值替换原来的value 值，最后返回oldValue结束
        • 如果在table[i]位置下未找到相同的key，则调用addEntry(hash, key, value, i);把新元素Entry放置到table[i]的位置
        • addEntry(int hash, K key, V value, int bucketIndex)方法中，先判断当前元素数量是否大于等于扩容阈值threshold，并且判断当前要添加的table[bucketIndex]位置上的元素是否不为空（如果不为空，则表示存在hash冲突），如果两个条件都满足调用resize(2 * table.length)将hashmap底层数组扩容原来的2倍
          • 在resize(int newCapacity)方法中先获取旧底层数组table赋值给变量Entry[] oldTable
          • 获取oldTable的长度，赋值给oldCapacity作为旧底层数组的长度，如果oldCapacity等于MAXIMUM_CAPACITY（hashmap的最大容量），则将扩容阈值赋值成Integer.MAX_VALUE，直接返回不进行扩容了。
          • 如果oldCapacity不等于MAXIMUM_CAPACITY，继续接下去的逻辑根据newCapacity创建新的Entry数组赋值给newTable变量
          • 接着调用transfer(Entry[] newTable, boolean rehash) 方法
          • 在transfer(Entry[] newTable, boolean rehash) 方法中两层循环遍历旧的hashmap底层数组，将旧数组+链表下的所有元素重新根据hash值调用indexFor(int h, int length) 方法，
          • indexFor(int h, int length) 方法内部是h & (length -1) 等同于h%length取余运算，目的是获取将不同哈希值都能映射到数组上
          • 将旧元素赋值到新元素后，将newTable变量赋值给hashmap对象的table作为新的hashmap，并且根据newCapacity * loaderFactor计算新的扩容阈值
          • 返回到addEntry方法的if ((size >= threshold) && (null != table[bucketIndex]))逻辑块中，根据key，调用hash(Object k)获取新的hash值,调用indexFor(int h, int length)计算key在新的bucket中的位置
          • 接着调用createEntry(int hash, K key, V value, int bucketIndex) 方法，
          • 在jdk7中createEntry(int hash, K key, V value, int bucketIndex使用头插法，将新元素Entry放入table[bucketIndex]位置，新元素Entry的next属性指向原来的table[bucketIndex]下的Entry。
    • 源码 
      • public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
        ? MAXIMUM_CAPACITY
        : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
    • 总结hashMap在jdk1.7版本下的对象创建和调用put方法的总结
      • 在jdk1.7下，HashMap空参构造器调用HashMap(initialCapacity,loadFactor)构造器，初始化容量默认initialCapacity为16，loadFactor使用默认为0.75，threshold扩容阈值默认为16*0.75=12
      • 在jdk1.7下对hashMap的数组做了懒加载机制，创建hashmap对象的时候，其table属性值为长度为0的空的Entry[]数组
      • jdk1.7下的hashmap的put流程总结
        • 第一次put键值对会判断，hashmap的table是否为空，为空则初始化。默认初始化成长度为16的Entry[]数组，并且计算扩容阈值为loadfactor*capacity,默认为12
        • 接下去是判断key==null的情况的键值对插入或修改操作，如果key为null，由于null无法调用hashcode所以将null放在table[0]位置，如果此时table[0]不存在元素，则将新Entry放在table[0]位置上，如果此时table[0]已存在元素或元素链表，则循环对比链表中的Entry的key和添加的Entry的key的hashcode是否相同，如果相同则进行一次修改操作，如果不同则使用头插法，将添加的entry加载table[0]的位置，将新entry的next指向旧的链表的头节点
        • 在添加过程中会有是否需要扩容的判断，如果当前hashmap中的元素数量大于扩容阈值threshold，并且当前要插入的位置的table[index]的位置是否已存在Entry，如果不存在则不进行扩容，如果已存在则需要扩容，扩容操作是将hashmap扩容至当前table长度的两倍，并且将旧map中的元素根据hashcode重写计算在bucket中的位置，并将这些元素赋值到新的table中
        • 如果key!=null，则根据key的hashcode，使用算法计算新的hash值，然后根据hash值&数组长度-1，实际就是hash值与数组长度取余，这样能获取到hash值映射到数组中的位置i
        • 然后根据key最后得到的在数组中的位置i，判断table[i]是否已有元素存在，如果有则逐个遍历，对比已有元素和新添加元素的key的hashCode和key本身是否相同如果相同则是一次修改操作将新的值value替换旧的值oldValue，返回oldValue。如果不存在相同key，则新的Entry赋值到table[i]的位置，并将新元素Entry的next属性指向旧元素的链表首节点（头插法）
        • 添加新元素的方法中也会判断是否需要扩容
  • hashMap在jdk1.8版本下的对象创建和调用put方法的流程及源码
    • 在jdk1.8的hashMap中，使用Node表示key-value键值对
    • 创建HashMap对象
    • HashMap map = new HashMap<>();//使用空参的构造器创建
    • 在jdk1.8中如果调用无参的构造函数，则直接叫负载因子初始化为默认值DEFAULT_LOAD_FACTOR=0.75
    • 其他的属性都会在第一次put的时候初始化 
    • public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
    • 调用put(K key, V value)调用逻辑
    • put方法调用链：
      • put(K key, V value)->putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)->resize()
      • put(K key, V value)->putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)->newNode(int hash, K key, V value, Node<K,V> next)
      • put(K key, V value)->putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)->TreeNode.putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)
      • put(K key, V value)->putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)->newNode(int hash, K key, V value, Node<K,V> next)->treeifyBin(Node<K,V>[] tab, int hash)->replacementTreeNode(Node<K,V> p, Node<K,V> next)
    • 步骤解析：
      • 调用put(K key,V value)方法，在put(K key,V value)方法中调用putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
      • 在putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) 先将hashmap的table属性赋值给tab变量，判断tab是否为null，或者tab的length是否为0,（初始化操作）。
        • 如果tab为null或者tab数组的length长度为0，则调用resize进行hashmap数组扩容，实际为初始化操作。
          • 调用resize()方法进行初始化扩容
            • 在resize()方法中先获取table属性，根据table属性内容生成旧数组的长度oldCapacity，旧扩容阈值oldThr，初始化新的数组长度newCapacity为0，新的扩容阈值newThr为0
            • 判断旧数组bucket长度oldCapacity是否大于0,
            • 如果oldCapacity大于0，表示试一次扩容操作，则先做一个保障机制，判断oldCapacity是否大于hashmap数组最大值MAXIMUM_CAPACITY，如果oldCapacity大于等MAXIMUM_CAPACITY，则不进行扩容，将扩容阈值赋值成Integer.MAX_VALUE
            • 如果oldCapacity小于MAXIMUM_CAPACITY,则将新数组的容量newCap扩大至原来的两倍newCap = oldCap << 1
            • 这里有个判断如果扩容至两倍后的newCap小于MAXIMUM_CAPACITY并且原数组长度oldCap大于初始化数组长度DEFAULT_INITIAL_CAPACITY = 16,在这个条件下，将扩容阈值也直接扩大成原来的两倍newThr = oldThr << 1
            • 如果不满足上述条件，扩容后的newCap大于MAXIMUM_CAPACITY或者oldCap小于初始化数组长度16，那么会在后续操作中根据新的数组长度newCap计算新的扩容阈值
            • 接下去判断旧扩容阈值oldThr是否大于0，如果oldThr大于0，则将oldThr赋值给newCap
            • 如果oldCap <=0 并且oldThr <= 0，则这个场景为初始化场景那么新的数组长度和扩容阈值都使用初始化的参数，newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFUALT_INITIAL_CAPACITY)
            • 接下去的逻辑是判断newThr是否为0，如果newThr为0，表示在上面的逻辑中，newCap过大大于了MAXIMUM_CAPACITY，所以重新计算扩容阈值，并且判断如果扩容阈值过大，则直接取Integer.MAX_VALUE
            • 根据新的数组长度newCap生成新的Node<k,v> newTab[]数组，将table属性值赋值为newTab[]
            • 循环遍历oldTab将就数组中的元素，重新根据hashCode计算出在新数组中的位置，赋值到newTab的相应的位置下
            • 在循环中判断oldTab[j]位置上的元素是否为null，如果为null则继续取下一个元素
            • 如果不为null
            • 判断oldTab[i]的Node元素是否有后继节点，如果没有则根据hash值重新和newCap取余获取Node元素在新数组中的下标位置
            • 判断oldTab[i]的Node元素是否为TreeNode，如果是则表示当前oldTab[i]下的是一颗红黑树，此时需要调用TreeNode.split()，此处后续解释
            • 如果不满足上述两个条件，则表示当前插入的是链表的操作。这里将操作分成高位链表hiHead，hiTail（扩容后的新数组的位置=旧数组链表索引位置+旧数组长度）和低位链表（旧数组的链表索引位置）loHead，loTail。
            • 这里使用的方式是使用元素的hash & 旧数组长度oldCap，判断得出的结果是否为0
            • 如果为0，则元素应该在低位链表处，也就是旧链表索引位置
            • 如果为1，则元素应该在高位链表处，也就是扩容后，旧链表索引位置+旧链表的长度
            • 解释：这么操作的原因是因为，扩容后，重hash的数组索引只可能在“原索引位置”或者“原索引位置+oldCap”
            • 假设老表的长度为16，即oldCap为16，则新标的容量为16 * 2 =32。
            • 假设节点1的hash值为：0000 0000 0000 0000 0000 1111 0000 1010，节点2的hash值为0000 0000 0000 0000 0000 1111 0001 1010，oldCap-1的hash值为0000 0000 0000 0000 0000 0000 0000 1111，则节点1和节点2在旧表的索引位置为0000 0000 0000 0000 0000 0000 0000 1010（计算方法为&运算，两个同时为1，结果为1，否则为0）。
            • 然后扩容后数组长度newCap为32，对应的newCap-1的hash值为0000 0000 0000 0000 0000 0000 0001 1111，节点1的hash值为：0000 0000 0000 0000 0000 1111 0000 1010，节点2的hash值为0000 0000 0000 0000 0000 1111 0001 1010。最后节点1在新表的索引值为0000 0000 0000 0000 0000 0000 0000 1010，而索引2在新表的索引值为0000 0000 0000 0000 0000 0000 0001 1010。对比可以看出，如果两个节点在老表的位置相同，在新标的索引位置只取决于节点hash值的倒数第n位（n = log2（newCapacity)）,当前为第5位。而此位的值刚好是oldCapacity的值16，也就是0000 0000 0000 0000 0000 0000 0001 0000
            • 所以，由于结果值取决于节点hash值得倒数第n位（此时为第5位），而此位置刚好是老表容量值，因此此时新表索引位置的计算可以替换为，直接使用节点hash值与老表容量oldCap进行位与（&）运算，如果结果为0则该节点在新表的索引位置为原索引位置，否则该节点的新表索引位置为“原索引+oldCap（旧表的数组容量）”
            • 最后在resize()方法中，返回newTab
        • n为当前table的长度
        • 接下去在putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法中，先根据当前数组长度-1（n-1) & 元素key的hash值（实际是取模运算）获取到元素应该在table的索引位置
        • 判断元素计算后的索引位置在table处是否已存在元素
          • 如果不存在，则将新元素添加的table上，索引为(n-1)&hash
          • 如果在索引位置已存在元素则要分三个条件判断
          • 判断索引位置上已存在Node的key是否等于新添加的key，判断条件为先判断hash值，如果hash值相同，再调用key的equals方法判断两者是否相同，如果满足上述两个条件，则是一次替换操作，将新的value替换掉老的value，返回oldValue
          • 如果索引位置上已存在Node的key不等于新添加的key，接着判断当前索引位置上的节点是否为树节点TreeNode，如果是树节点，则进行树节点的添加或替换操作，调用TreeNode.putTreeVal()方法，（后续要补充）
          • 如果如果索引位置上已存在Node的key不等于新添加的key，并且当前索引位置上的节点不是树节点，那么此时需要进行链表的添加或替换操作（jdk1.8是尾插法）
            • 添加方法，判断链表上的节点的key是否等于新添加的key，判断条件为先判断hash值，如果hash值相同，再调用key的equals方法判断两者是否相同如果满足上述两个条件，则是一次替换操作，将新的value替换掉老的value，返回oldValue。
            • 如果没有找到相同key的节点，则是一次添加操作，找到链表上next属性为null的节点p，也就是尾结点，将p的next属性赋值为new Node（newNode(hash, key, value, null)）。添加完后，还要判断是否需要树化
            • 判断树化的条件是，当链表上的节点数操作了树化阈值TREEIFY_THRESHOLD=8，并且容器中的元素数量超过了最小树化元素总数MIN_TREEIFY_CAPACITY=64。
            • 如果当前链表上的节点数超过了树化阈值8，但是容器中的元素数量为超过最小树化元素总数64，此时进行的是一次resize()扩容操作。
            • 只有当链表上的节点数超过了树化阈值8，并且容器中的元素数量超过了最小树化元素总数是，才进行树化操作
            • 树化操作，先循环链表上所有节点，调用replacementTreeNode(Node<K,V> p, Node<K,V> next) 将Node节点转成TreeNode节点。将原来的单向链表变成双向链表。 
              p.prev = tl;
tl.next = p;
            • 然后调用TreeNode.treeify(Node<K,V>[] tab) 方法进行具体树化操作
    • 源码： 
      • 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;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        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 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;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        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;
}

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; // 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 = 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 { // 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 {
                            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;
}

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            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);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
集合 java hashmap
上一篇: Java集合在JDK1.7和JDK1.8中的不同——JDK1.7和JDK1.8中集合的对比研究——java集合深入理解1、ArrayList
下一篇: python的matplotlab绘图时中文乱码，报错的解决问题，设置默认字体

继续阅读