JDK1.8源码学习-HashMap

　　JDK1.8源码学习-HashMap

一、HashMap简介

HashMap 主要用来存放键值对，它是基于哈希表的Map接口实现的，是常用的Java集合之一。

我们都知道在JDK1.8 之前的HashMap是由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

为什么会有这种改变呢？

主要是因为之前HashMap在解决哈希冲突的时候默认是采用链表的方式，当出现哈希冲突时，以链表的方式来存储冲突的数据，但是链表的查询时间复杂度为O(N)，当链表过长时，就会发生查询效率过低的问题。而如果使用红黑树来存储的话，那查询时间复杂度直接降为O(log(n))，这样可以解决链表查询效率过低的问题，这就是为什么JDK1.8中的HashMap采用了链表和红黑树两种方式，这点也可以从下面的HashMap的数据结构中查看。

二、HashMap工作原理

HashMap 是基于 hashing 的原理

我们使用 put(key, value) 存储对象到 HashMap 中，使用 get(key) 从 HashMap 中获取对象。当我们给 put() 方法传递键和值时，我们先对键调用 hashCode() 方法，计算并返回的 hashCode 是用于找到 Map 数组的 bucket 位置来储存 Node 对象。

这里关键点在于指出，HashMap 是在 bucket 中储存键对象和值对象，作为Map.Node 。

HashMap的初始化

Node[] table = new Node[16]; // 散列桶初始化，table

class Node {

    hash; //hash值

    key; //键

    value; //值

    node next; //用于指向链表的下一层（产生冲突，用拉链法）

}

put过程

对 Key 求 Hash 值，然后再计算下标
如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的 Hash 值相同，需要放到同一个 bucket 中）
如果碰撞了，以链表的方式链接到后面
如果链表长度超过阀值（TREEIFY THRESHOLD==8），就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
如果节点已经存在就替换旧值
如果桶满了（容量16*加载因子0.75），就需要 resize（扩容2倍后重排）

get过程

　　当我们调用 get() 方法，HashMap 会使用键对象的 hashcode 找到 bucket 位置，找到 bucket 位置之后，会调用 keys.equals() 方法去找到链表中正确的节点，最终找到要找的值对象。

三、HashMap数据结构

上图展示了HashMap（JDK1.8）的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树的引入是为了提高效率。

当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

四、HashMap源码分析

4.1、继承关系分析

public class HashMap<K,V> extends AbstractMap<K,V>

    implements Map<K,V>, Cloneable, Serializable

HashMap继承自AbstractMap,实现了Map、Cloneable、Serializable接口，其中Map接口中定义了一些通用的操作，Cloneable接口可以使HashMap调用clone()方法，进行浅层次的拷贝，Serializable接口可以使HashMap实现序列化。

4.2、成员变量分析

//默认初始化map的容量：16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //左移运算，2的4次方

//map的最大容量：2^30

static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的填充因子：0.75，能较好的平衡时间与空间的消耗

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//将链表(桶)转化成红黑树的临界值

static final int TREEIFY_THRESHOLD = 8;

//将红黑树转成链表(桶)的临界值

static final int UNTREEIFY_THRESHOLD = 6;

//转变成树的table的最小容量，小于该值则不会进行树化

static final int MIN_TREEIFY_CAPACITY = 64;

//用来存储数组，长度总是2的幂次

transient Node<K,V>[] table;

//map中的键值对集合

transient Set<Map.Entry<K,V>> entrySet;

//map中键值对的数量，即存储节点的数量

transient int size;

//用于统计map修改次数的计数器，用于fail-fast抛出ConcurrentModificationException

transient int modCount;

//扩展后数组的长度，大于该阈值，则重新进行扩容，threshold = capacity(table.length) * load factor

int threshold;

//负载因子，可以进行指定，建议使用默认值0.75

final float loadFactor;

1.threshold

threshold = capacity(table.length) * load factor 当Size>=threshold的时候，就要考虑对数组的扩增了，这个值是衡量数组是否需要扩增的一个标准。

2.loadFactor负载因子

loadFactor负载因子是控制数组存放数据的疏密程度，loadFactor越趋于1，那么数组中存放的数据也就越多，也就越密，链表也会越长，loadFactor越小，也就是趋近于0。

当loadfactor太大则会导致查找元素的效率低下，太小则会导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个较好的临界值。

HashMap中是使用Node[]数组来存储数据的，每一个Node都指向下一个节点，采用的是链表结构。

// 继承自 Map.Entry<K,V>

static class Node<K,V> implements Map.Entry<K,V> {

       final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素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; }

        // 重写hashCode()方法

        public final int hashCode() {

            return Objects.hashCode(key) ^ Objects.hashCode(value);

        }

        public final V setValue(V newValue) {

            V oldValue = value;

            value = newValue;

            return oldValue;

        }

        // 重写 equals() 方法

        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;

        }

}

4.3、构造函数分析

4.3.1无参构造函数

只是初始化了负载因子，并没有初始化数组的大小。

  public HashMap() {

        this.loadFactor = DEFAULT_LOAD_FACTOR; //采用默认的0.75f

    }

4.3.2传入初始化容量构造函数（如果初始化时知道HashMap的容量大小，建议采用此种构造函数）

指定初始化数组的大小。

 public HashMap(int initialCapacity) {

        this(initialCapacity, DEFAULT_LOAD_FACTOR);

    }

4.3.3传入初始化容量及填充因子构造函数

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);

    }

4.3.4包含另一个Map的构造函数

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

        this.loadFactor = DEFAULT_LOAD_FACTOR;

        putMapEntries(m, false);

    }

tableSizeFor()方法：返回一个最小的且比用户给定参数（cap）大的或者等于的,并且是2的整数次幂的数值。

   /**

     * Returns a power of two size for the given target capacity.

     */

    static final int tableSizeFor(int cap) {

        int n = cap - 1;

        n |= n >>> 1;

        n |= n >>> 2;

        n |= n >>> 4;

        n |= n >>> 8;

        n |= n >>> 16;

        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

    }

putMapEntries()方法：

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {

        //获取m中键值对的数量

        int s = m.size();

        if (s > 0) {

            //判断table是否已经初始化

            if (table == null) {

                //计算map的容量，键值对的数量 = 容量 * 填充因子

                float ft = ((float)s / loadFactor) + 1.0F;

                int t = ((ft < (float)MAXIMUM_CAPACITY) ?

                        (int)ft : MAXIMUM_CAPACITY);

                //如果容量大于了阈值，则重新计算阈值。

                if (t > threshold)

                    threshold = tableSizeFor(t);

            }

            //如果table已经有，且键值对数量大于了阈值，进行扩容处理

            else if (s > threshold)

                resize();

            //将m中所有元素添加至HashMap中

            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {

                K key = e.getKey();

                V value = e.getValue();

                putVal(hash(key), key, value, false, evict);

            }

        }

    }

4.4、put()方法分析

HashMap只提供了put()方法用于添加元素，在put()方法中调用了putVal（）方法，这个方法没有提供给用户。

putVal()方法：

1.如果定位到的数组位置没有元素则直接插入新的元素。

2.如果定位到的数组位置有元素就要和插入的key进行比较，如果key值相同就直接覆盖，如果key值不相同，则判断p是否是一个树节点，如果是就将元素添加进去，否则遍历链表进行插入数据。

    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;

        //table未初始化或者长度为0,则扩容。注意这里的赋值操作，关系到下面

        if ((tab = table) == null || (n = tab.length) == 0)

            n = (tab = resize()).length;

        //(n - 1) & hash确定了元素放在哪个桶里面，如果tab对应的数组位置为空，则创建新的node，并指向它

        if ((p = tab[i = (n - 1) & hash]) == null)

            // newNode方法就是返回Node：return new Node<>(hash, key, value, next);

            tab[i] = newNode(hash, key, value, null);

        else {//桶中已经存在元素

            Node<K,V> e; K k;

            //如果比较hash值和key的值都相等，说明要put的键值对已经在里面，赋值给e

            if (p.hash == hash &&

                    ((k = p.key) == key || (key != null && key.equals(k))))

                //赋值,用e来进行记录

                e = p;

                //如果p节点是红黑树节点，则执行插入树的操作(hash值不相等,即key值不相等)

            else if (p instanceof TreeNode)

                //放入树中

                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

            else {//如果是链表节点

                for (int binCount = 0; ; ++binCount) {

                    //找到了最后一个都不满足的话，则在链表最后插入节点。注意这里的e = p.next，赋值兼具判断都在if里了

                    if ((e = p.next) == null)

                        //在末尾插入新节点

                        p.next = newNode(hash, key, value, null);

                    //之前field说明中的，如果节点的数量大于树化阈值，则转化成红黑树，第一个是-1

                    if (binCount >= TREEIFY_THRESHOLD - 1)

                        treeifyBin(tab, hash);

                    break;

                }

                //判断链表中节点的key值与插入元素的key值是否相等

                if (e.hash == hash &&

                        ((k = e.key) == key || (key != null && key.equals(k))))

                    //相等则跳出循环

                    break;

                //遍历桶中的链表,与前面的e=p.next组合,可以遍历链表

                p = e;

            }

        }

        //上面循环中找到了e,则根据onlyIfAbsent是否为true来决定是否替换旧值

        if (e != null) {

            V oldValue = e.value;

            if (!onlyIfAbsent || oldValue == null)

                e.value = value;

            //钩子函数，用于给LinkedHashMap继承后使用，在HashMap里是空的

            afterNodeAccess(e);

            return oldValue;

        }

    }

    //修改计数器+1

  ++modCount;

    //实际大小+1， 如果大于阈值，重新计算并扩容

  if (++size > threshold)

    resize();

    //钩子函数，用于给LinkedHashMap继承后使用，在HashMap里是空的

    afterNodeInsertion(evict);

  return null;

}

4.5、get()方法分析

    public V get(Object key) {

        Node<K,V> e;

        return (e = getNode(hash(key), key)) == null ? null : e.value;

    }

    final Node<K,V> getNode(int hash, Object key) {

        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

        //先是判断一通table是否为空以及根据hash找到存放的table数组的下标，并赋值给临时变量

        if ((tab = table) != null && (n = tab.length) > 0 &&

                (first = tab[(n - 1) & hash]) != null) {

            //总是先检查数组下标第一个节点是否满足key，满足则返回

            if (first.hash == hash &&

                    ((k = first.key) == key || (key != null && key.equals(k))))

                return first;

            //如果第一个与key不相等，则循环查看桶

            if ((e = first.next) != null) {

                //检查是否为树节点，是的话采用树节点的方法来获取对应的key的值

                if (first instanceof TreeNode)

                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);

                //do-while循环判断,在链表中进行查找

                do {

                    if (e.hash == hash &&

                            ((k = e.key) == key || (key != null && key.equals(k))))

                        return e;

                } while ((e = e.next) != null);

            }

        }

        return null;

    }

4.6、resize()方法分析

HashMap的扩容方法，会伴随着一次新的hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在HashMap的使用过程中尽量避免resize。

扩容的过程是依据存放的节点(Node)数量是否超过阈值来判断的，如果超过阈值则扩容一倍（即扩充为当前阈值的2倍）。

 final Node<K,V>[] resize() {

        //获取旧的table,cap,threshold

        //如果数组为空,则会创建一个默认容量为16的数组,threshold为12

        Node<K,V>[] oldTab = table;

        //扩容/缩容前的容量

        int oldCap = (oldTab == null) ? 0 : oldTab.length;

        //旧的阈值

        int oldThr = threshold;

        int newCap, newThr = 0;

        //说明之前已经初始化过map

        if (oldCap > 0) {

            //达到了最大的容量，则将阈值设为最大，并且返回旧的table(此时超过了最大值不再进行扩容，进行随机碰撞)

            if (oldCap >= MAXIMUM_CAPACITY) {

                threshold = Integer.MAX_VALUE;

                return oldTab;

            }

            //如果两倍的旧容量小于最大的容量(即没有超过最大值)且旧容量大于等于默认初始化容量，则旧的阈值也扩大两倍。

            //oldCap << 1,其实就是*2的意思,扩容至阈值的2倍。

            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

                    oldCap >= DEFAULT_INITIAL_CAPACITY)

                newThr = oldThr << 1; // double threshold

        }

        //旧容量为0且旧阈值大于0，则赋值给新的容量(应该是针对初始化的时候指定了其容量的构造函数出现的这种情况)

        else if (oldThr > 0)

            newCap = oldThr;

            //这种情况就是调用无参数的构造函数

        else {

            newCap = DEFAULT_INITIAL_CAPACITY;

            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

        }

        // 新阈值为0,则通过：新容量*填充因子 来计算resize的上限

        if (newThr == 0) {

            float ft = (float)newCap * loadFactor;

            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

                    (int)ft : Integer.MAX_VALUE);

        }

        threshold = newThr;

        //根据新的容量来初始化table，并赋值给table

        @SuppressWarnings({"rawtypes","unchecked"})

        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

        table = newTab;

        //如果旧的table里面有存放节点，则初始化给新的table(即将bucket移动到新的buckets中)

        if (oldTab != null) {

            for (int j = 0; j < oldCap; ++j) {

                Node<K,V> e;

                //将下标为j的数组赋给临时节点e

                if ((e = oldTab[j]) != null) {

                    //清空

                    oldTab[j] = null;

                    //如果e.next为null,说明当前节点只有一个值，则直接通过计算hash和新的容量来确定新的下标，更新当前值到newTab即可

                    if (e.next == null)

                        newTab[e.hash & (newCap - 1)] = e;

                        //如果为树节点，按照树节点的来拆分

                    else if (e instanceof TreeNode)

                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                        //e还有其他的节点，将该桶拆分成两份(不一定均分)

                    else {

                        //loHead是拆分后的,链表的头部,tail为尾部,以链表的方式来逐个添加数据到newTab

                        Node<K,V> loHead = null, loTail = null;

                        Node<K,V> hiHead = null, hiTail = null;

                        Node<K,V> next;

                        do {

                            next = e.next;

                            //根据e的hash值和旧的容量做位与运算是否为0来拆分，注意之前是 e.hash & (oldCap - 1)

                            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;

    }

4.7、remove()方法分析

   public V remove(Object key) {

        Node<K,V> e;

        //与之前的put、get一样，remove也是调用其他的方法(removeNode方法)

        return (e = removeNode(hash(key), key, null, false, true)) == null ?

                null : e.value;

    }

    final Node<K,V> removeNode(int hash, Object key, Object value,

                               boolean matchValue, boolean movable) {

        Node<K,V>[] tab; Node<K,V> p; int n, index;

        //还是先判断table是否为空之类的逻辑,根据key和hashCode来获取对应的索引的位置

        if ((tab = table) != null && (n = tab.length) > 0 &&

                (p = tab[index = (n - 1) & hash]) != null) {

            Node<K,V> node = null, e; K k; V v;

            //对下标节点进行判断,如果相同,则赋给临时节点

            if (p.hash == hash &&

                    ((k = p.key) == key || (key != null && key.equals(k))))

                node = p;

            else if ((e = p.next) != null) {

                //为树节点,则按照树节点的操作来进行查找并返回

                if (p instanceof TreeNode)

                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);

                else {//按照链表的方式进行节点遍历

                    do {

                        if (e.hash == hash &&

                                ((k = e.key) == key ||

                                        (key != null && key.equals(k)))) {

                            node = e;

                            break;

                        }

                        p = e;

                    } while ((e = e.next) != null);

                }

            }

            //如果找到了key对应的node，则进行删除操作

            if (node != null && (!matchValue || (v = node.value) == value ||

                    (value != null && value.equals(v)))) {

                //为树节点，则进行树节点的删除操作

                if (node instanceof TreeNode)

                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);

                //为链表节点,进行链表节点的删除操作

                else if (node == p)

                    //如果p == node，说明该key所在的位置为数组的下标位置，所以下标位置指向下一个节点即可

                    tab[index] = node.next;

                    //否则的话，key在桶中,p为node的上一个节点，p.next指向node.next即可

                else

                    p.next = node.next;

                //修改计数器

                ++modCount;

                --size;

                //钩子函数，与上同

                afterNodeRemoval(node);

                return node;

            }

        }

        return null;

    }

　　这里需要注意的是在进行是否是同一个节点进行判断的时候使用的是(p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))的方式，即首先判断两个元素的hash值是否相等，如果相等才会使用equals()方法进行比较，否则就说明这两个元素一定不是同一个对象，直接返回。如果hash值是一样的，则进行equals()判断key值，两个条件都成立时，认定两个元素是同一个值。

　　所以我们在修改对象的equals()方法的时候，也需要对hashCode()方法进行修改，如果不修改的话hash值可能相等，equal()方法也可能相等，同时成立的话会被认为是同一对象，直接进行覆盖操作。

　　使用remove()方法最常见的 java.util.ConcurrentModificationException异常，举例

Map<String, Integer> map = new HashMap<>();

map.put("GoddessY", 1);

map.put("Joemsu", 2);

for (String a : map.keySet()) {

  if ("GoddessY".equals(a)) {

    map.remove(a);

  }

}

抛出异常的源码

public Set<K> keySet() {

  Set<K> ks;

  return (ks = keySet) == null ? (keySet = new KeySet()) : ks;

}

final class KeySet extends AbstractSet<K> {

  public final Iterator<K> iterator()     { return new KeyIterator(); }

}

final class KeyIterator extends HashIterator implements Iterator<K> {

  public final K next() { return nextNode().key; }

}

abstract class HashIterator {

  //指向下一个节点

  Node<K,V> next;

  //指向当前节点

  Node<K,V> current;

  //迭代前的修改次数

  int expectedModCount;

  //当前下标

  int index;

  HashIterator() {

    //注意这里：将修改计数器值赋给expectedModCount

    expectedModCount = modCount;

    //下面一顿初始化。。。

    Node<K,V>[] t = table;

    current = next = null;

    index = 0;

    //在table数组中找到第一个下标不为空的节点。

    if (t != null && size > 0) {

      do {} while (index < t.length && (next = t[index++]) == null);

    }

  }

  //通过判断next是否为空，来决定是否hasNext()

  public final boolean hasNext() {

    return next != null;

  }

  //这里就是抛出ConcurrentModificationException的地方

  final Node<K,V> nextNode() {

    Node<K,V>[] t;

    Node<K,V> e = next;

    //如果modCount与初始化传进去的modCount不同，则抛出并发修改的异常

    if (modCount != expectedModCount)

      throw new ConcurrentModificationException();

    if (e == null)

      throw new NoSuchElementException();

    //如果一个下标对应的桶空了，则接着在数组里找其他下标不为空的桶，同时赋值给next

    if ((next = (current = e).next) == null && (t = table) != null) {

      do {} while (index < t.length && (next = t[index++]) == null);

    }

    return e;

  }

  //使用迭代器的remove不会抛出ConcurrentModificationException异常，原因如下：

  public final void remove() {

    Node<K,V> p = current;

    if (p == null)

      throw new IllegalStateException();

    if (modCount != expectedModCount)

      throw new ConcurrentModificationException();

    current = null;

    K key = p.key;

    removeNode(hash(key), key, null, false, false);

    //注意这里：对expectedModCount重新进行了赋值。所以下次比较的时候还是相同的

    expectedModCount = modCount;

  }

}

具体的详细原因和解决方法有兴趣的园友可以直接搜索concurrentmodificationexception异常，这里给出一篇参考地址： https://www.cnblogs.com/snowater/p/8024776.html

五、HashMap总结

1、非线程安全，无序，可以有一个key值为null或多个value为null。

2、默认大小是16，扩充为2的指数。

3、最好能够在初始化HashMap的时候指定其容量，这样能使效率比使其存储空间不够后自动增长更高。

4、除了使用迭代器的remove方法外使用其他方式删除，都会抛出ConcurrentModificationException。

参考链接

https://www.cnblogs.com/joemsu/p/7724623.html

http://www.importnew.com/31096.html

http://www.importnew.com/31278.html

https://tech.meituan.com/2016/06/24/java-hashmap.html

http://www.cnblogs.com/leesf456/p/5242233.html

http://www.pianshen.com/article/6104166010/

巴特西

JDK1.8源码学习-HashMap

HashMap 是基于 hashing 的原理

最新文章

热门文章