jdk版本：1.8

数据结构：

HashMap的底层次要基于数组+链表/红黑树实现，数组长处就是查问块，HashMap通过计算hash码获取到数组的下标来查问数据。同样也能够通过hash码失去数组下标，存放数据。

哈希表为了解决抵触，HashMap采纳了链表法,增加的数据寄存在链表中，如果发送抵触，将数据放入链表尾部。

上图左侧局部是一个哈希表，也称为哈希数组（hash table）：

// table数组transient Node<K,V>[] table;

table数组的援用类型是Node节点，数组中的每个元素都是单链表的头结点，链表次要为了解决下面说的hash抵触,Node节点蕴含：

  • hash hash值
  • key 键
  • value 值
  • next next指针

Node节点构造如下:

 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;    }    // 省略 get/set等办法}

次要属性

// 贮存元素数组Node<K,V>[] table;// 元素个数int size;// 数组扩容临界值，计算为：元素容量*装载因子int threshold// 装载因子，默认0.75float loadFactor;// 链表长度为 8 的时候会转为红黑树int TREEIFY_THRESHOLD = 8;// 长度为 6 的时候会从红黑树转为链表int UNTREEIFY_THRESHOLD = 6;
  • size记录元素个数
  • threshold 扩容的临界值，等于元素容量*装载因子
  • TREEIFY_THRESHOLD 8 链表个数减少到8会转成红黑树
  • UNTREEIFY_THRESHOLD 6 链表个数缩小到6会进化成链表
  • loadFactor 装载因子，默认为0.75
loadFactor 装载因子等于扩容阈值/数组长度，示意元素被填满的程序，越高示意空间利用率越高，然而hash抵触的概率减少，链表越长，查问的效率升高。越低hash抵触缩小了，数据查问效率更高。然而示空间利用率越低，很多空间没用又持续扩容。为了平衡查问工夫和应用空间，零碎默认装载因子为0.75。

获取哈希数组下标

增加、删除和查找办法，都须要先获取哈希数组的下标地位，首先通过hash算法算出hash值，而后再进行长度取模，就能够获取到元素的数组下标了。

首先是调用hash办法,计算出hash值：

static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

先获取hashCode值，而后进行高位运算,高位运算后的数据，再进行取模运算的速度更快。

算出hash值之后，再进行取模运算：

(n - 1) & hash

下面的n是长度，计算的后果就是数组的下标了。

构造方法

HashMap()

     /**     * default initial capacity (16)     *  the default load factor (0.75).      */    public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR;    }

设置默认装载因子0.75，默认容量16。

HashMap(int initialCapacity)

// 指定初始值大小public HashMap(int initialCapacity) {    this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 指定初始值和默认装载因子 0.75public 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);}

HashMap(int initialCapacity) 指定初始容量，调用HashMap(int initialCapacity, float loadFactor) 其中loadFactor为默认的0.75。

首先做容量的校验，小于零报错，大于最大容量赋值最大值容量。而后做装载因子的校验，小于零或者是非数字就报错。

tableSizeFor应用右移和或运算，保障容量是2的幂次方，传入2的幂次方，返回传入的数据。传入不是2的幂次方数据，返回大于传入数据并靠近2的幂次方数。比方：

  • 传入10返回16。
  • 传入21返回32。

# HashMap(Map<? extends K, ? extends V> m)

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

将汇合m的数据增加到HashMap汇合中，先设置默认装载因子，而后调用putMapEntries增加汇合元素到HashMap中，putMapEntries是遍历数组，增加数据。

总结

本文基于jdk1.8解析HashMap源码，次要介绍了：

  • HashMap 是基于数组+链表/红黑树构造实现。采纳链表法解决hash抵触。
  • Node 节点记录了数据的key、hash、value以及next指针。

  • HashMap次要属性：

    • size 元素个数
    • table[] 哈希数组
    • threshold 扩容的阈值
    • loadFactor 装载因子
    • TREEIFY_THRESHOLD 8，链表个数为8转成红黑树。
    • UNTREEIFY_THRESHOLD 6 ，链表个数为6红黑树转为链表。
  • 增加、删除以及查找元素，首先要先获取数组下标，HashMap先调用hasCode办法，hashCode()的高16位异或低16位，大大的减少了运算速度。而后再对数组长度进行取模运算。实质就是取key的hashCode值、高位运算、取模运算。

  • HashMap几个构造方法：

    • HashMap()设置默认装载因子0.75和默认容量16。
    • HashMap(int initialCapacity)设置初始容量，默认装载因子0.75，容量是肯定要是2的幂次方，如果不是2的幂次方，减少到靠近2的幂次方数。
    • HashMap(Map<? extends K, ? extends V> m)次要是遍历增加的汇合，增加数据。

参考

深入浅出HashMap的设计与优化

Java 8系列之重新认识HashMap

感觉不错的话，就点个赞吧！