每日一句

有望得到的要努力，无望得到的不介意，则无论输赢姿态都会好看。

概念回顾

• HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null），那么对于查找，添加等操作很快，仅需一次寻址即可；

• 如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。

• 所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

不同JVM版本HashMap的展现形式

本章内容主要为介绍JDK7的版本文章学习。

JDK7

HashMap的数据结构为：数组 + 链表

JDK8

可以查看相关对应的另外一篇【JDK8的HashMap源码分析】

HashMap的数据结构为：数组 + 链表 + 红黑树

基本简介

哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，而HashMap的实现原理就是基于此。

数据结构的分析

针对于多种数据结构进行分析为什么会选择Hash表的方式进行存储和查询。

数组

采用一段连续的存储单元来存储数据。

查询操作场景

• 对于指定下标的查找，时间复杂度为O(1)；

• 通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)。

• 对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；

插入删除场景

• 对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)。

对应到集合类是ArrayList。

线性链表

查询操作场景

• 查找操作需要遍历链表逐一进行比对，复杂度为O(n)。

插入删除场景

• 链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)。

对应的集合类是LinkedList。

二叉树

• 对一棵相对平衡的有序二叉树。

• 对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

对应的集合类有TreeSet和TreeMap。

哈希表

相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。

对应的集合类就是HashMap。

哈希表的主干就是数组。我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。

即：存储位置 = hash(关键字)

其中，这个函数hash一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。这会涉及到哈希冲突。

• 哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀。

Hash冲突机制

当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。

• 数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？

  • 哈希冲突的解决方案有多种：开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）、再散列函数法、链地址法。

而HashMap即是采用了链地址法，也就是数组+链表的方式。

HashMap的源码实现

存储结构

Hash桶（bucket）

• 当实例化一个HashMap时，系统会创建一个长度为Capacity的Entry数组，这个长度被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。

• 每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。

Entry

HashMap的基本组成单元，每一个Entry包含一个key-value键值对。 Entry是HashMap中的一个静态内部类。代码如下：

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
       //存储指向下一个Entry的引用，单链表结构
        Entry<K,V> next;
      //对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
        int hash;
        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

经过以上分析，HashMap的存储结构图如下：

• 一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。

• 一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。

  • 比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
• 在存储一对值时（Key ->Value对），实际上是存储在一个Entry的对象e中，程序通过key计算出Entry对象的存储位置。
  • Key->Value的对应关系是通过key—-Entry—-value这个过程实现的，所以就有我们表面上知道的key存在哪里，value就存在哪里。

重要属性

先看HashMap中的几个重要属性：

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

//最大容量，即2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态
static final Entry<?,?>[] EMPTY_TABLE = {};

//空的存储实体
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//实际存储的key-value键值对的个数
transient int size;

//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold
int threshold;

//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;

//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;

//默认的threshold值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

//计算Hash值时的key种子值
transient int hashSeed = 0;

构造方法

HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值。initialCapacity默认为16，loadFactory默认为0.75。

    //通过初始容量和状态因子构造HashMap
    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;
        threshold = initialCapacity;
        // init方法在HashMap中没有实际实现，不过在其子类如 
        // linkedHashMap中就会有对应实现
        init();
    }

    //通过扩容因子构造HashMap,容量去默认值，即16
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    //装载因子取0.75，容量取16，构造HashMap  
    public HashMap() { 
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }  

    //通过其他Map来初始化HashMap，
   // 容量通过其他Map的size来计算，装载因子取0.75  
    public HashMap(Map<? extends K, ? extends V> m) {  
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        inflateTable(threshold);//初始化HashMap底层的数组结构
        putAllForCreate(m);//添加m中的元素
    }

从上面这段代码我们可以看出，在常规构造器中，并没有马上为数组table分配内存空间（有一个入参为指定Map的构造器例外），事实上是在执行第一次put操作的时候才真正构建table数组。

put操作

• 如果两个key通过hash%Entry[].length得到的index相同，为了解决这个问题，HashMap里面用到链式数据结构的一个概念。

  • 上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做：Entry[0] = A。

  • 一会后又进来一个键值对B，通过计算其index也等于0，HashMap会这样做:B.next = A,Entry[0] = B，如果又进来C，index也等于0,那么C.next = B,Entry[0] = C；

• 这样我们发现index=0的地方其实存取了A,B,C三个键值对，他们通过next这个属性链接在一起。

• 也就是说数组中存储的是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。

public V put(K key, V value) {
        //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(=16)
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);//分配数组空间
        }
       //如果key为null，存储位置为table[0]或table[0]的冲突链上
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
    //对key的hashcode进一步计算，确保散列均匀
        int i = indexFor(hash, table.length);//获取在table中的实际位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);//调用value的回调函数，其实这个函数也为空实现
                return oldValue;
            }
        }
        modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
        addEntry(hash, key, value, i);//新增一个entry
        return null;
    }

putForNullKey 方法

• key为null的时候，只会放在hashMap的0位置（即key的hashCode为0，对数组长度取余后的下标也是0），不会有链表

• 在HashMap源码中对put方法对null做了处理，key为null的判断后进入putForNullKey(V value)这个方法，里面for循环是在talbe[0]链表中查找key为null的元素，如果找到，则将value重新赋值给这个元素的value，并返回原来的value。如果没找到则将这个元素添加到talbe[0]链表的表头

/**
 * Offloaded version of put for null keys
 */
private V putForNullKey(V value) {
    // for循环处理key为空的情况
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

inflateTable的源码如下：

private void inflateTable(int toSize) {
//capacity一定是2的次幂
        int capacity = roundUpToPowerOf2(toSize);
//此处为threshold赋值，取capacity*loadFactor和  MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1
        threshold = (int) Math.min(capacity * loadFactor,
                                   MAXIMUM_CAPACITY + 1);
        //分配空间
        table = new Entry[capacity];
        //选择合适的Hash因子
        initHashSeedAsNeeded(capacity);
}

inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16；to_size=16，capacity=16；to_size=17,capacity=32。

二次幂其实现如下：

private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值。

在对数组进行空间分配后，会根据hash函数计算散列值，其实现如下：

//用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀

final int hash(Object k) {
        int h = hashSeed;
        //这里针对String优化了Hash函数，是否使用新的Hash函数和Hash
        // 因子有关  
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

• 从上面的操作看以看出，影响HashMap元素的存储位置的只有key的值，与value值无关。

• 通过hash函数得到散列值后，再通过indexFor进一步处理来获取实际的存储位置

其实现如下：

    //返回数组下标
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

• h &（length-1）保证获取的index一定在数组范围内，举个例子，默认容量16，length-1=15，h=18,转换成二进制计算为

最终计算出的index=2。有些版本的对于此处的计算会使用取模运算，也能保证index一定在数组范围内，不过位运算对计算机来说，性能更高一些（HashMap中有大量位运算）。

• 通过以上分析，我们看到，要得到一个元素的存储位置，需要如下几步：
  1. 获取该元素的key值
  2. 通过hash方法得到key的散列值，其中需要用到key的hashcode值。
  3. 通过indexFor计算得到存储的下标位置。
  4. 最后，得到存储的下标位置后，我们就可以将元素放入HashMap中，具体通过addEntry实现：

 void addEntry(int hash, K key, V value, int bucketIndex) {
        //当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容，新容量为旧容量的2倍
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            //扩容后重新计算插入的位置下标
            bucketIndex = indexFor(hash, table.length);
        }
        //把元素放入HashMap的桶的对应位置
        createEntry(hash, key, value, bucketIndex);
    }
    //创建元素
    void createEntry(int hash, K key, V value, int bucketIndex) {  
        //获取待插入位置元素
        Entry<K,V> e = table[bucketIndex];
        //这里执行链接操作，使得新插入的元素指向原有元素。
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        //这保证了新插入的元素总是在链表的头
        //元素个数+1
        size++; 
}

• 通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候并且对应的key对应的table桶的首地址元素不为null的情况下：需要进行数组扩容

• 扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。

扩容操作

扩容操作通过resize操作实现：

 //按新的容量扩容Hash表
void resize(int newCapacity) {
        Entry[] oldTable = table;//老的数据
        int oldCapacity = oldTable.length;//获取老的容量值
        //老的容量值已经到了最大容量值
        if (oldCapacity == MAXIMUM_CAPACITY) {
            //修改扩容阀值
            threshold = Integer.MAX_VALUE;
            return;
        }
        //新的结构
        Entry[] newTable = new Entry[newCapacity];
        //将老的表中的数据拷贝到新的结构中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        //修改HashMap的底层数组
        table = newTable;
        //修改阀值  
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}  

如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法。

//将老的表中的数据拷贝到新的结构中
    void transfer(Entry[] newTable, boolean rehash) {  
        int newCapacity = newTable.length;//容量  
        for (Entry<K,V> e : table) { //遍历所有桶
            while(null != e) {  //遍历桶中所有元素（是一个链表）
                Entry<K,V> next = e.next;
                //如果是重新Hash，则需要重新计算hash值.
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //定位Hash桶
                int i = indexFor(e.hash, newCapacity);
                //元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
                e.next = newTable[i];
                //newTable[i]的值总是最新插入的值
                newTable[i] = e;
                e = next;//继续下一个元素  
            }  
        }  
    }  

这个方法将老数组中的数据逐个链表地遍历，重新计算后放入新的扩容后的数组中，我们的数组索引位置的计算是通过对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置。

• 注意：HashMap数组元素长度的设计

• 通过源码可以发现，hashMap的数组长度一定保持2的次幂，这样做有什么好处呢？

//根据Hash值和Hash表的大小选择合适的Hash桶  
    static int indexFor(int h, int length) {  
        return h & (length-1);  
    }  

• 如果length为2的次幂，其二进制表示就是100….0000；则length-1 转化为二进制必定是0111….11的形式，在于h的二进制与操作效率会非常的快，而且空间不浪费；如果length不是2的次幂，比如length为15，则length-1为14，对应的二进制为1110，再于h与操作。

• 最后一位都为0，所以0001，0011，0101，1001，1011，0111，1101这几个位置永远都不会存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

get操作

    //获取key值为key的元素值  
    public V get(Object key) {  
        if (key == null)//如果Key值为空，则获取对应的值，这里也可以看到，HashMap允许null的key，其内部针对null的key有特殊的逻辑  
            return getForNullKey();  
        Entry<K,V> entry = getEntry(key);//获取实体  

        return null == entry ? null : entry.getValue();//判断是否为空，不为空，则获取对应的值  
    }  

    //获取key为null的实体  
    private V getForNullKey() {  
        if (size == 0) {//如果元素个数为0，则直接返回null  
            return null;  
        }  
        //key为null的元素存储在table的第0个位置  
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
            if (e.key == null)//判断是否为null  
                return e.value;//返回其值  
        }  
        return null;
    }  

get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法：

//获取键值为key的元素  
    final Entry<K,V> getEntry(Object key) {  
        if (size == 0) {//元素个数为0  
            return null;//直接返回null  
        }  

        int hash = (key == null) ? 0 : hash(key);//获取key的Hash值  
        for (Entry<K,V> e = table[indexFor(hash, table.length)];//根据key和表的长度，定位到Hash桶  
             e != null;  
             e = e.next) {//进行遍历  
            Object k;  
            if (e.hash == hash &&  
                ((k = e.key) == key || (key != null && key.equals(k))))//判断Hash值和对应的key，合适则返回值  
                return e;  
        }  
        return null;  
    }  

• get方法的实现相对简单，key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。

• 在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。

HashMap中的hashcode怎么生成

调用对象key的hashCode方法，再对这个hashcode方法进行一些右移以及异或运算（使的hashCode的高位和低位都参与到运算中）；通过右移和异或运算可以使hashMap的散列化更强，提高hashMap的get方法的效率

为什么使用HashCode

HashCode的存在主要是为了查找的快捷性，HashCode是用来在散列存储结构中确定对象的存储地址的 ( 用hashcode来代表对象在hash表中的位置 ) , hashCode存在的重要的原因之一就是在HashMap（HashSet其实就是HashMap）中使用（其实Object类的hashCode方法注释已经说明了）。

equals方法和hashcode的关系

• 若重写了equals(Object obj)方法，则有必要重写hashCode()方法

• 若两个对象equals(Object obj)返回true，则hashCode()有必要也返回相同的int数

• 若两个对象equals(Object obj)返回false，则hashCode()不一定返回不同的int数

• 若两个对象hashCode()返回相同int数，则equals(Object obj)不一定返回true

• 若两个对象hashCode()返回不同int数，则equals(Object obj)一定返回false

同一对象在执行期间若已经存储在集合中，则不能修改影响hashCode值的相关信息，否则会导致内存泄露问题

总结

HashMap之所以速度快，因为他使用的是散列表，根据key的hashcode值生成数组下标（通过内存地址直接查找，不需要判断，但是需要多出很多内存，相当于以空间换时间）