转载

HashMap源码剖析

Java7中的实现。

① 初始化桶大小，因为底层是数组，所以这是数组默认的大小。 ② 桶最大值。 ③ 默认的负载因子（0.75） ④ table 真正存放数据的数组。 ⑤ Map 存放数量的大小。 ⑥ 桶大小，可在初始化时显式指定。 ⑦ 负载因子，可在初始化时显式指定。

给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash 、 复制数据 等操作，所以非常消耗性能。

尽量提前预估 HashMap 的大小最好，可以减少扩容带来的性能损耗。

真正存放数据的是 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Entry 是 HashMap 中的一个内部类，从他的成员变量很容易看出：

① key 就是写入时的键。 ② value 自然就是值。 ③ next 开始的时候就提到 HashMap 是由数组和链表组成，所以这个 next 就是用于实现链表结构。 ④ hash 存放的是当前 key 的 hashcode。

Java7的Hash冲突问题

当 Hash 冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时的效率就会越来越低；时间复杂度为 O(N) 。

Base 1.8

1.8 中重点优化了这个查询效率。

1.8 HashMap 结构图：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  默认初始容量

static final int MAXIMUM_CAPACITY = 1 << 30;  // 最大容量

static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子 

static final int TREEIFY_THRESHOLD = 8; // >= 8, 转换为红黑树的阈值

static final int UNTREEIFY_THRESHOLD = 6; // <= 6，转换为链表的阈值 

static final int MIN_TREEIFY_CAPACITY = 64; // Entry[]数组的容量 >= 64 ,转换为红黑树的阈值 

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

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

transient int size; // map的有效 key 的数量
复制代码

Java8的HashMap的区别和改进

TREEIFY_THRESHOLD 用于判断是否需要将链表转换为红黑树的阈值。
HashEntry 修改为 Node，Node 的核心组成其实也是和 1.7 中的 HashEntry 一样，存放的都是 key value hashcode next 等数据。
HashMap 不会因为多线程 put 导致死循环（JDK 8 用 head 和 tail 来保证链表的顺序和之前一样；JDK 7 rehash 会倒置链表元素），但是还会有数据丢失等弊端（并发本身的问题）。因此多线程情况下还是建议使用 ConcurrentHashMap

HashMap的并发安全问题

为什么线程不安全 HashMap 在并发时可能出现的问题主要是两方面：

如果多个线程同时使用 put 方法添加元素，而且假设正好存在两个 put 的 key 发生了碰撞（根据 hash 值计算的 bucket 一样），那么根据 HashMap 的实现，这两个 key 会添加到数组的同一个位置，这样最终就会发生其中一个线程 put 的数据被覆盖
如果多个线程同时检测到元素个数超过数组大小 * loadFactor，这样就会发生多个线程同时对 Node 数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给 table，也就是说其他线程的都会丢失，并且各自线程 put 的数据也丢失

##hash方法为什么要有HashMap的hash()方法，难道不能直接使用KV中K原有的hash值吗？在HashMap的put、get操作时为什么不能直接使用K中原有的hash值。

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

从上面的代码可以看到key的hash值的计算方法。key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。）

为什么要这么干呢？这个与HashMap中table下标的计算有关。

n = table.length;
index = （n-1） & hash;
复制代码

因为，table的长度都是2的幂，因此index仅与hash值的低n位有关，hash值的高位都被与操作置为0了。假设table.length=2^4=16。

由上图可以看到，只有hash值的低4位参与了运算。这样做很容易产生碰撞。设计者权衡了speed, utility, and quality，将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了，而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

tableSizeFor方法

源码：

static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 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;
    }
复制代码

这个方法被调用的地方：

public HashMap(int initialCapacity, float loadFactor) {
        /**省略此处代码**/
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
复制代码

由此可以看到，当在实例化HashMap实例时，如果给定了initialCapacity，由于HashMap的capacity都是2的幂，因此这个方法用于找到大于等于initialCapacity的最小的2的幂（initialCapacity如果就是2的幂，则返回的还是这个数）。下面分析这个算法：首先，为什么要对cap做减1操作。 int n = cap - 1; 这是为了防止，cap已经是2的幂。如果cap已经是2的幂，又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。如果不懂，要看完后面的几个无符号右移之后再回来看看。下面看看这几个无符号右移操作：如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是1（最后有个n+1的操作）。这里只讨论n不等于0的情况。 第一次右移

n |= n >>> 1;
复制代码

由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如000011xxxxxx。 第二次右移

n |= n >>> 2;
复制代码

注意，这个n已经经过了 n |= n >>> 1; 操作。假设此时n为000011xxxxxx ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如00001111xxxxxx 。 第三次右移

n |= n >>> 4;
复制代码

这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中会有8个连续的1。如00001111 1111xxxxxx 。 以此类推 注意，容量最大也就是32bit的正数，因此最后 n |= n >>> 16; ，最多也就32个1，但是这时已经大于了 MAXIMUM_CAPACITY ，所以取值到 MAXIMUM_CAPACITY 。举一个例子说明下吧。

这个算法着实牛逼啊！

注意，得到的这个capacity却被赋值给了threshold。

this.threshold = tableSizeFor(initialCapacity);
复制代码

开始以为这个是个Bug，感觉应该这么写：

this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
复制代码

这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。但是，请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。

put方法

JDK 1.7实现

public V put(K key, V value) {
       //如果 key 为null,将会插入一个 NullKey
       if (key == null)
           return putForNullKey(value);             
       //得到 key 的hash值                                        
       int hash = hash(key);   
       //得到 key 要插入的数组索引                                                                        
       int i = indexFor(hash, table.length);     
       //遍历此索引节点下的链表元素                                        
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {                       
           Object k;
           // hash碰撞，则覆盖旧值
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }
 
       modCount++;      //修改次数 +1
       addEntry(hash, key, value, i); //在数组索引节点的头部插入新的元素
       return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
        //如果HashMap主干数组的大小已经 >= 设定阈值，并且头部元素不为Null
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //HashMap进行扩容 *2
            resize(2 * table.length);
            //得到要插入的key 的hash值
            hash = (null != key) ? hash(key) : 0; 
            //得到桶索引下标
            bucketIndex = indexFor(hash, table.length);
        }
        //执行添加元素的操作
        createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
        //链表的头部元素
        Entry<K,V> e = table[bucketIndex];    
        //在链表的头部添加了一个新元素（头插法），旧值的指针赋值给了 next 属性 
        table[bucketIndex] = new Entry<>(hash, key, value, e); 
        //map元素 +1
        size++;
}
static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
}     
static int indexFor(int h, int length) {
        return h & (length-1);
}
复制代码

JDK 1.8实现

public V put(K key, V value) {
      // 对key的hashCode()做hash
      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;
      // 步骤①：tab为空则创建
     if ((tab = table) == null || (n = tab.length) == 0)
         n = (tab = resize()).length;
     // 步骤②：计算index，并对null做处理 
     if ((p = tab[i = (n - 1) & hash]) == null) 
         tab[i] = newNode(hash, key, value, null);
     else {
         Node<K,V> e; K k;
         // 步骤③：节点key存在，直接覆盖value
         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);
                        //链表长度大于8转换为红黑树进行处理
                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                         treeifyBin(tab, hash);
                     break;
                 }
                    // key已经存在直接覆盖value
                 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;
}
复制代码

get方法

JDK 1.7实现

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        /**
          * 先定位到数组元素，再遍历该元素处的链表
          * 判断的条件是key的hash值相同，并且链表的存储的key值和传入的key值相同
          */
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
}
复制代码

JDK 1.8实现

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; // tab.length
        K k;  // 
        // table不为空，table长度大于0，目标索引链表头部元素不为空
        if ( (tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
            /**
             * 先查看数组的头部元素是否就是当前要查询的元素
             * always check first node
             */
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                return first;  // 如果是的话 ，直接返回该元素
            // 判断链表头部元素的下一节点元素不为 null
            if ((e = first.next) != null) {
                // 然后再判断 这个数组的桶 是 红黑树 还是链表
                // 红黑树的情况 
                if (first instanceof TreeNode)  
                    // 然后开始查找这棵树上的节点，返回node
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 不是红黑树 ，那肯定就是链表咯，那就遍历它吧
                do {
                    // 然后再链表中找到了 一个hash相同，并且 key也相同的元素，
                    // 就是它了，直接返回这个元素吧
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
}
复制代码

HashMap扩容的时候

JDK 1.7实现

// 用新的容量来给table扩容  
void resize(int newCapacity) {  
    // 旧数组
    Entry[] oldTable = table; 
    // 旧数组的长度
    int oldCapacity = oldTable.length;
    // 如果旧的容量已经是系统默认最大容量了(扩容前的数组大小如果已经达到最大(2^30)了 )，那么将阈值设置成整形的最大值，退出 ,  
    if (oldCapacity == MAXIMUM_CAPACITY) {  
        threshold = Integer.MAX_VALUE;  
        return;  
    }  
    // 初始化一个新的Entry数组  
    Entry[] newTable = new Entry[newCapacity];  
    // 将数据转移到新的Entry数组里 
    transfer(newTable, initHashSeedAsNeeded(newCapacity));  
    //HashMap的table属性引用新的Entry数组
    table = newTable;  
    //设置临界值  
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);  
}
复制代码

删除数据的时候

JDK 1.7实现

//根据指定的key删除Entry，返回对应的value  
public V remove(Object key) {  
    Entry<K,V> e = removeEntryForKey(key);  
    return (e == null ? null : e.value);  
}  
//根据指定的key，删除Entry,并返回对应的value  
final Entry<K,V> removeEntryForKey(Object key) {  
    if (size == 0) {  
        return null;  
    }  
    int hash = (key == null) ? 0 : hash(key);  
    int i = indexFor(hash, table.length);  
    Entry<K,V> prev = table[i];  
    Entry<K,V> e = prev;  
    while (e != null) {  
        Entry<K,V> next = e.next;  
        Object k;  
        if (e.hash == hash &&  
            ((k = e.key) == key || (key != null && key.equals(k)))) {  
            modCount++;   // 修改次数 +1
            size--;               // 元素个数 -1
            if (prev == e) //如果删除的是table中的第一项的引用  
                table[i] = next;//直接将第一项中的next的引用存入table[i]中  
            else  
                prev.next = next; //否则将table[i]中当前Entry的前一个Entry中的next置为当前Entry的next  
            e.recordRemoval(this);  
            return e;  
        }  
        prev = e;  
        e = next;  
    }  
    return e;  
}
复制代码