HashMap是Java中使用频率最高处理键值对的集合，本文将对HashMap的源码进行理解学习（基于JDK1.8）。

 

在学习HashMap之前，先需要理解什么是哈希表。

哈希表，也称为散列表。是一种使用非常频繁的数据结构，它能根据键（Key）直接访问内存的存储位置。本质上维护了一种键值对关系。

Hash表的做法其实很简单，它通过某种Hash算法计算出键（Key）的hash值，然后对存储值（Value）的数组进行取模运算，取模结果就作为数组下标，将值（Value）存储在计算出的位置。因而也和数组一样，通过数组下标就可以直接操作，速度很快。

 

HashMap的底层是用的就是哈希表，在JDK1.8中HashMap的底层存储结构是：数组+链表+红黑树，如下图所示：

 

 

通过读源码，可以知道HashMap中使用一个静态内部类来保存哈希表中键值对的关系：

//哈希桶数组，存储键值对    transient Node
     
      [] table;        static class Node
      
        implements Map.Entry
       
         {        final int hash;     //用来定位数组索引位置        final K key;        V value;        Node
        
          next;     //链表下个节点的引用    }
        
       
      
     

其中最后一个属性，指向了链表的下一节点。

 

下面，再来看一下HashMap的hash算法：

static final int hash(Object key) {        int h;        //key为null的时候，hash为0        //1、h为key的hashCode值        //2、h >>> 16        //3、将1和2中的结果进行异或运算        //hash值高16位不变，低16位与高16位异或作为key的最终hash值        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }

这个方法就决定了一个Entry键值对在哈希桶数组中的存储位置。

 

在1.8版本的HashMap中，

/**     * 返回一个比给定整数大且最接近的2的幂次方整数     * 这个算法不断的把第一个1开始后面的位变成1     */    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的构造方法：

 

HashMap的put方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node
     
      [] tab; Node
      
        p; int n, i;        //将当前hash桶指向tab，判断tab是否为null        //计算hash桶的长度n，判断n是否为0        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;            //对hash桶进行扩容，并将新的长度指向n        if ((p = tab[i = (n - 1) & hash]) == null)  //计算元素存放位置p，并判断hash桶该索引处是否为null            tab[i] = newNode(hash, key, value, null);   //将需要存储的k-v对存放在该hash桶第i个位置        else {      //计算出的存储位置处已经有了元素，转为链或者树            Node
       
         e; K k;            //校验链表首节点元素key的hash值是否与插入值相等，key是否相等            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))                e = p;                      //将p赋给e            else if (p instanceof TreeNode) //树                e = ((TreeNode
        
         )p).putTreeVal(this, tab, hash, key, value);            else {                          //链表                //循环，                for (int binCount = 0; ; ++binCount) {                    //依次判断下一节点是否为null，为null时，就将k-v数据插入到链表末尾                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        if (binCount >= TREEIFY_THRESHOLD - 1)  //当插入第8个节点的时候，结构转化为树                            treeifyBin(tab, hash);                        break;                    }                    //判断此处链表是否存在此key，如果存在，将e指向它                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            //链表或树中已经存在了此key，条件符合时替换value            if (e != null) { // existing mapping for key                V oldValue = e.value;                //onlyIfAbsent为true表示不修改已经存在的值                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;        //判断是否需要扩容        if (++size > threshold)            resize();        afterNodeInsertion(evict);        return null;    }
        
       
      
     

 

HashMap的扩容：

final Node
     
      [] resize() {        Node
      
       [] oldTab = table;        int oldCap = (oldTab == null) ? 0 : oldTab.length;      //旧hash桶长度        int oldThr = threshold;                                 //旧阈值        int newCap, newThr = 0;        if (oldCap > 0) {       //旧hash桶长度大于0时            if (oldCap >= MAXIMUM_CAPACITY) {                threshold = Integer.MAX_VALUE;                return oldTab;            }            //如果就hash桶长度的2倍小于最大容量，并且旧容量大于默认初始容量16，就将新hash桶长度扩为以前的2倍            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)                newThr = oldThr << 1; // double threshold       //新阈值为旧阈值的2倍        }        //旧阈值大于0，新hash桶容量就是阈值        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
       
        [] newTab = (Node
        
         [])new Node[newCap];     //新创建一个数组        table = newTab;         //将新数组作为hash桶        if (oldTab != null) {            for (int j = 0; j < oldCap; ++j) {                Node
         
           e;        //声明一个节点e                if ((e = oldTab[j]) != null) {          //循环整个hash桶数组，将非空元素进行复制                    oldTab[j] = null;                    if (e.next == null)                 //这条链上只有一个节点元素时                        newTab[e.hash & (newCap - 1)] = e;  //确定该节点元素在新的hash桶的位置                    else if (e instanceof TreeNode)     //如果hash桶数组此处是红黑树                        ((TreeNode
          
           )e).split(this, newTab, j, oldCap); else { // preserve order //hash桶数组此处是链表 // 进行链表复制 // 方法比较特殊： 它并没有重新计算元素在数组中的位置 // 而是采用了 原始位置加原数组长度的方法计算得到位置 Node
           
             loHead = null, loTail = null; Node
            
              hiHead = null, hiTail = null; Node
             
               next; do { //循环链表 next = e.next; if ((e.hash & oldCap) == 0) { //e.hash & oldCap计算节点e是否需要移动 if (loTail == null) //链表尾巴为bull，则链表为null loHead = e; //设置首节点 else loTail.next = e; loTail = e; //否则就将节点e作为链表尾节点 } else { //需要移动 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //循环条件为e节点的下一节点不为null if (loTail != null) { //源链表尾巴不为null时 loTail.next = null; //将尾节点的下一节点设为null newTab[j] = loHead; //首节点赋值 } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; //hash桶数组新增链表元素的首节点赋值 } } } } } return newTab; }
             
            
           
          
         
        
       
      
     

 

JDK1.7中HashMap在多线程环境下可能发送死循环问题：

 

 

HashMap小结：