java容器----HashMap

ゞ浴缸里的玫瑰 2021-09-22 07:50 327阅读 0赞

现在java的源码版本一个比一个复杂，人老了直接看别人的源码介绍，接着我再大概讲讲hashMap具体的存放规则。

[java1.8 hashmap源码说明][java1.8 hashmap]

--------------------

java1.8中hashmap增加了红黑树结构，不过这里我们就讲讲比较原始的**数组加链表**结构。

如下图所示，hashmap有一个数组，每个数组元素都是一个链表，在同一个链表的元素的hash值都是相同的。

![这里写图片描述][SouthEast]

//initialCapacity是初始化大小，loadFactor叫负载因子
        public HashMap(int initialCapacity, float loadFactor) {
    
            //初始容量不能<0
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    
            //初始容量不能 > 最大容量值，HashMap的最大容量值为2^30 
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
    
            //负载因子不能 < 0
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
            this.loadFactor = loadFactor;
    
            //设置HashMap的容量极限
            //当HashMap的容量达到该极限时就会进行扩容操作 
            this.threshold = tableSizeFor(initialCapacity);
        }

一、每次大小n都会被扩充为小于的那个最近的2的n次方，及power-of-two,例如初始化大小为10，那么大小就会被改为16，因为2的4次方为16，然后threshold=16\*075（默认负载因子大小）=12；所以只要放超过12个数就会resize()扩充一倍大小。

然后为什么要2的n次方?

我们这里先看看怎么得到元素在数组中的位置，即通过下面的indexFor()函数：

/** * Returns index for hash code h. */  
        static int indexFor(int h, int length) {  
            return h & (length-1);  
        }

可以看到 **return h & (length-1);**

当length=15时(非n^2)，根据上面计算方式，得到2和3、4和5、6和7…的结果一样，这样表示他们在table存储的位置是相同的，也就是产生了碰撞，2和3、4和5…就会在一个位置形成链表，这样就会导致查询速度降低。

![这里写图片描述][EFE6EB0523974F1EAEA5A93E1573630A]

从上面的图表中我们看到总共发生了8此碰撞，同时发现浪费的空间非常大，有1、3、5、7、9、11、13、15处没有记录，也就是没有存放数据。这是因为他们在与14进行&运算时，得到的结果最后一位永远都是0，即0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的，空间减少，进一步增加碰撞几率，这样就会导致查询速度慢。

而当length = 16时，length – 1 = 15 即1111，那么进行低位&运算时，值总是与原来hash值相同，而进行高位运算时，其值等于其低位值。所以说当length = 2^n时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。

二、 hash函数  
上面我们知道索引的值为**return h & (length-1);**，  
那么h是怎么得来的？

1.8之前的h是由如下方式得来：

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

1.8：

static int hash(int h) {  
          // This function ensures that hashCodes that differ only by 
          // constant multiples at each bit position have a bounded 
          // number of collisions (approximately 8 at default load factor). 
            h ^= (h >>> 20) ^ (h >>> 12);  
            return h ^ (h >>> 7) ^ (h >>> 4);  
        }

两者都是一样都是要吧hash值的高位去影响低位

正如java doc对hash方法的描述：将hash函数作为已给定的hashCode的一个补充，可以提高hash函数的质量。hash质量的好坏是非常重要的，因为HashMap用2的次幂作为表的hash长度，这就容易产生冲突，因为hashCodes在低位不是不同的（hashCodes that do not differ in lower bits）。注意：Null 的key的hash值总是0，即他在table的索引为0。  
让我们通过例子来帮助我们理解一下上面的话。加入说key object的hashCode()只返回三个值：31、63和95.31、63和95都是int型，所以是32位的。  
31=00000000000000000000000000011111  
63=00000000000000000000000000111111  
95=00000000000000000000000001011111  
现在加入HashMap的table长为默认值16(2^4,HashMap的长度总是2的次幂)  
假如我们不用hash函数，indexFor将返回如下值：  
31=00000000000000000000000000011111 => 1111=15  
63=00000000000000000000000000111111 => 1111=15  
95=00000000000000000000000001011111 => 1111=15  
为什么会这样？因为当我们调用indexFor函数的时候，它将执行31&15，,63&15和95&15的与操作，比如说95&15得出一下结果：  
00000000000000000000000001011111 &00000000000000000000000000001111  
也就是说(2^n-1)总会是一个1的序列，因此不管怎样，最后会执行0&1的于然后得出0.  
上面的例子，也就解释了凡是在末尾全是1111的都返回相同的index，因此，尽管我们有不同的hashcode，Entry对象却讲都被存在table中index为15的位置。  
倘若我们使用了hash函数，对于上面每一个hashcode，经过hash作用作用后如下：  
31=00000000000000000000000000011111 =>  
00000000000000000000000000011110  
63=00000000000000000000000000111111 =>  
00000000000000000000000000111100  
95=00000000000000000000000001011111 =>  
00000000000000000000000001011010  
现在在通过新的hash之后再使用indexFor将会返回：  
00000000000000000000000000011110 =>1110=14  
00000000000000000000000000111100 =>1100=12  
00000000000000000000000001011010 =>1010=10  
在使用了hash函数之后，上面的hashcodes就返回了不同的index，因此，hash函数对hashmap里的元素进行了再分配，也就减少了冲突同时提高了性能。  
hash操作最主要的目的就是在最显著位的hashcode的差异可见，以致于hashmap的元素能够均匀的分布在整个桶里。  
有两点需要注意：  
如果两个key有相同的hashcode，那他们将被分配到table数组的相同index上  
如果两个key不具有相同的hashcode，那么他们或许可能，或许也不可能被分配到table数组相同的index上。

三、threshold为容量乘以负载因子，如果bucket满了(超过load factor\*current capacity)，就要resize。  
在resize的过程，就是把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中。

扩充是很消耗时间和资源的，因为需要把全部东西都弄回来，而因为节点所在位置是和数组大小有关的，所以需要全部重新计算放在i，即计算放在哪里。

[java1.8 hashmap]: http://www.jianshu.com/p/59240407fd9a
[SouthEast]: /images/20210920/f4b3bfce9259458fba534965125aea8d.png
[EFE6EB0523974F1EAEA5A93E1573630A]: http://note.youdao.com/yws/res/1256/EFE6EB0523974F1EAEA5A93E1573630A