Java Hashmap实现原理及扩容机制详解_for (int bincount = 0; ; ++bincount)

HashMap基础
HashMap继承了AbstractMap类，实现了Map，Cloneable，Serializable接口

HashMap的容量，默认是16

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
HashMap的加载因子，默认是0.75

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
当HashMap中元素数超过容量*加载因子时，HashMap会进行扩容。

 

HashMap实现原理
 

Node和Node链
首先来了解一下HashMap中的元素类型

HashMap类中的元素是Node类，翻译过来就是节点，是定义在HashMap中的一个内部类，实现了Map.Entry接口。

Node类的定义如下：

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    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;
        }
 
        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;
        }
    }
可以看到，Node类的基本属性有：

hash：key的哈希值

key：节点的key，类型和定义HashMap时的key相同

value：节点的value，类型和定义HashMap时的value相同

next：该节点的下一节点

值得注意的是其中的next属性，记录的是下一个节点本身，也是一个Node节点，这个Node节点也有next属性，记录了下一个节点，于是，只要不断的调用Node.next.next.next……，就可以得到：

 Node-->下个Node-->下下个Node……-->null

这样的一个链表结构，而对于一个HashMap来说，只要明确记录每个链表的第一个节点，就能顺序遍历链表上的所有节点。

 

拉链法
HashMap使用拉链法管理其中的每个节点。

由Node节点组成链表之后，HashMap定义了一个Node数组：

transient Node<K,V>[] table;
这个数组记录了每个链表的第一个节点，于是最终形成了HashMap下面这样的数据结构：

这种数组+链表的数据结构，使得HashMap可以较为高效的管理每一个节点。

 

关于Node数组 table
对于table的理解，对后面关于扩容的理解很有帮助。

table在第一次往HashMap中put元素的时候初始化。

如果HashMap初始化的时候没有指定容量，那么初始化table的时候会使用默认的DEFAULT_INITIAL_CAPACITY参数，也就是16，作为table初始化时的长度。

如果HashMap初始化的时候指定了容量，HashMap会把这个容量修改为2的倍数，然后创建对应长度的table。

table在HashMap扩容的时候，长度会翻倍。

所以table的长度肯定是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;
    }
所以要注意，如果要往HashMap中放1000个元素，又不想让HashMap不停的扩容，最好一开始就把容量设为2048，设为1024不行，因为元素添加到七百多的时候还是会扩容。

 

散列算法
当调用HashMap.put()方法时，经历了以下步骤：

1，对key进行hash值计算

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
2，hash值和table.length取模

取模的方法是(table.length - 1) & hash，算法直接舍弃了二进制hash值在table.length以上的位，因为那些位都代表table.length的2的n次方倍数。

取模的结果就是Node将要放入table的下标。

比如，一个Node的hash值是5，table长度是4，那么取余的结果是1，也就是说，这个Node将被放入table[1]所代表的链表（table[1]本身指向的是链表的第一个节点）。

3，添加元素

如果此时table的对应位置没有任何元素，也就是table[i]=null，那么就直接把Node放入table[i]的位置，并且这个Node的next==null。

如果此时table对应位置是一个Node，说明对应的位置已经保存了一个Node链表，则需要遍历链表，如果发现相同hash值则替换Node节点，如果没有相同hash值，则把新的Node插入链表的末端，作为之前末端Node的next，同时新Node的next==null。

如果此时table对应位置是一个TreeNode，说明链表被转换成了红黑树，则根据hash值向红黑树中添加或替换TreeNode。（JDK1.8）

4，如果添加元素之后，Node链表的节点数超过