HashMap 源码分析

HashMap涉及到的东西还真是挺多的.看了几篇文章也算是个总结吧

前置知识

在分析HashMap之前先说一些基础的知识.

HashCode

它是一个int类型的值由jdk根据对象计算得出.每个对象都会有这个值.这里涉及到和equals方法的关系.在Java中规定,如果equals()方法返回true,那么比较的hashCode必须是相等的.因此重写equals方法必须要重写hashCode方法.

Map的存储结构

Map的内部有一个Entry类,,它是一个单链表,存放了key,value,以及下一个Entry.
Entry存储在一个数组上,一个位置放一个单链表.

Map的存储方式
通过key获取vlaue的过程,首先通过key的hash值获取到map数组存放的索引,然后再通过key的equals方法获取对应的值.

map的加载因子
默认为0.75 在hashMap中实际存储量是数组的size * 0.75 也就是size为16实际存储12以上元素的时候就会把数组尺寸扩大一倍为32.如果加载因子为1,那么数组上都会有链表.查询会非常耗时.如果数值偏小,那么会浪费空间.
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

源码分析

构造函数

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

并没有实际创建 一个Map,数组也没有创建.真正的创建是在put方法里调用的inflateTable()

hash方法

final int hash(Object k) {
int h = hashSeed;
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);
}

传入的对象获取hash值,然后进行异或运算.
h ^= (h >>> 20) ^ (h >>> 12);
h ^ (h >>> 7) ^ (h >>> 4);
为什么要经过这样的运算呢？这就是HashMap的高明之处。先看个例子，一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。

那这样有什么意义呢？
如果通过key获取value值,需要经过key的hash值来获取到map存放数组的索引,h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的位置.因此上面操作希望得到的索引更加的均匀.这样每个数组上的都尽量平均覆盖到单链表.

h&(length-1)为什么会比length小?
当 length 总是 2 的倍数时，h & (length-1) 将是一个非常巧妙的设计：假设 h=5,length=16, 那么 h & length - 1 将得到 5；如果 h=6,length=16, 那么 h & length - 1 将得到 6 ……如果 h=15,length=16, 那么 h & length - 1 将得到 15；但是当 h=16 时 , length=16 时，那么 h & length - 1 将得到 0 了；当 h=17 时 , length=16 时，那么 h & length - 1 将得到 1 了……这样保证计算得到的索引值总是位于 table 数组的索引之内。

put方法

在看put源码之前需hash方法作为支撑.现在再来看一下put方法

public V put(K key, V value) {
       if (table == EMPTY_TABLE) {
         //如果数组为空,则把数组扩容,扩容后的长度为2的n次方
           inflateTable(threshold);
       }
      //如果key为null,那么存放的位置是数组索引为0的位置
       if (key == null)
           return putForNullKey(value);
       //获取hash值
       int hash = hash(key);
       //获取索引
       int i = indexFor(hash, table.length);
      //遍历单链表,如果key的equals返回true则覆盖老的oldValue
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
       //如果重写了equals方法,不重写hashCode此时就会有问题了.
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }
     //修改了map的结构
       modCount++;
     //新增一个Entry
       addEntry(hash, key, value, i);
       return null;
   }

addEntry方法

这个方法主要是判断新增的Entry类是否会导致Map的尺寸.如果超过就将数组的长度扩展为当前的两倍.

void addEntry(int hash, K key, V value, int bucketIndex) {
//size代表在这个map中包含键值对映射数量.
//如果新增Entry类size是否大于阀值(默认是12),指定索引的数组是不为空,
        if ((size >= threshold) && (null != table[bucketIndex])) {
//map尺寸增加当前table长度两倍
//阀值是32*0.75
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

createEntry方法

新建一个Entry在单链表的头部.next指向下一个Entry对象

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
      //新的Entry指向当前存放的链表的头部
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

resize方法

Map当中设置map的最大尺寸
static final int MAXIMUM_CAPACITY = 1 << 30; 2的三十次方.
当指定的超过这个数时也Map的size也不会增加了.
此时阀值会变成int最大值,也就是2的三十一次方.
这部分我很疑惑,既然达到了2的三十次方不会再次增加了,那么阀值也就没有存在的意义了吧.何必还要符合规则是当前的两倍呢.设置为MAXIMUM_CAPACITY +1即可

 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];
        //原来的Entry放到新的数组中,所以hash值要重新计算.
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

以上基本是一个put的过程.取也类似.