HashMap原理机制自问自答

时间:2021-12-31 19:12:48

关于hashmap在平时写代码的时候经常用,但是hashmap的一些原理貌似知道的不是很多,翻了下代码,得出如下结论。

 

(1)HashMap是啥?

HashMap是基于哈希表的Map实现,能够满足所有的Map操作,同时支持空的key和空的value,非线程安全的,

不保证map中键值的顺序,特别是不保证顺序是不变的(翻译自java 源代码)。

 

(2)如果Map<K,V> map = new HashMap<K,V>()这种情况,容器默认参数是啥?

源代码查看,有三个常量,

 static final int DEFAULT_INITIAL_CAPACITY = 16;

 static final int MAXIMUM_CAPACITY = 1 << 30;

 static final float DEFAULT_LOAD_FACTOR = 0.75f;

三个常量中可以看出,默认的容器大小是16,最大长度是2的30次方,load factor默认是0.75,扩充的临界值是16*0.75=12

 

(3)如果已经知道Map的大小,如何提升性能?

 

HashMap的实例有两个参数影响着他的性能,

一个是initial capacity

(初始化容量,容量是哈希表中的空间数,初始化容量是HashMap创建的时候的大小,当然,后面是会自动扩容的);

一个是load factor

(负荷系数,当目前的容量达到负荷系数的时候,重新build,扩充到原来的两倍)。

通用的规则,laod factor默认是0.75,在空间和时间上面一个不错的权衡。

如果确定有很多mapping的数据放在HashMap的实例里面,初始化的时候创建一个大一点的容量比hashmap自己去扩容要有效的多。

因为在数组扩充的时候,会重新new一个数组出来,然后老数组数据重新赋值到新数组,转换成本消耗资源。

 

(4)如果自定义initial capacity的大小,如果保证Map大小是2的指数次方?

这个看HashMap的构造行数,

如下,通过while循环,初始值1的移位来使大小始终是2的指数次,初始化的数组大小是小于入参的最大的2的指数次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)){ //如果laodFactor小于等于零或者不是number,抛异常
            throw  new  IllegalArgumentException( "Illegal load factor: "  + loadFactor);
        }
        /**
         * 这里设计比较巧妙了,保证HashMap的大小始终是2的指数次
         * 经过这个while处理后,初始化的数组是大于这个值的最小的2的指数
         * 例子:如果initialCapacity=13,则2进制数值有2、4、8、16,大约13的是16,则此时初始化的数组大小是16
         */
        int  capacity =  1 ;
        while  (capacity < initialCapacity){
             capacity <<=  1 ;
        }
        this .loadFactor = loadFactor;
        threshold = ( int )(capacity * loadFactor);
        table =  new  Entry[capacity];
        init();
    }

 

(5)为什么HashMap的大小要是2的指数次呢?

key经过hash后,可以取模来进行放入数组,也不会出现越界的情况,

之所以没有使用取模,而是按位与的形式,是因为计算机的二进制运算效率比取模效率高。

如果Map的大小不是2的进制,我们设置为7

7的二进制是:111,(length-1)大小是6,按位与是和6进行,6的二进制是:110

结果如下,有些数组中的位置没有被设置,有些重复了,一是导致空间浪费,同时增加了碰撞的几率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for ( int  i= 0 ;i< 10 ;i++){
     System.out.println
     ( "数值i=" +i+ ", 二进制=" +Integer.toBinaryString(i)+ "(" +Integer.toBinaryString( 6 )+ ")" + " ,和6按位与=" +(i& 6 ));
}
   
数值i= 0 , 二进制= 0 110 ) ,和 6 按位与= 0
数值i= 1 , 二进制= 1 110 ) ,和 6 按位与= 0
数值i= 2 , 二进制= 10 110 ) ,和 6 按位与= 2
数值i= 3 , 二进制= 11 110 ) ,和 6 按位与= 2
数值i= 4 , 二进制= 100 110 ) ,和 6 按位与= 4
数值i= 5 , 二进制= 101 110 ) ,和 6 按位与= 4
数值i= 6 , 二进制= 110 110 ) ,和 6 按位与= 6
数值i= 7 , 二进制= 111 110 ) ,和 6 按位与= 6
数值i= 8 , 二进制= 1000 110 ) ,和 6 按位与= 0
数值i= 9 , 二进制= 1001 110 ) ,和 6 按位与= 0

然后我们设置8,(length-1)大小是7,7的二进制是111,打印看结果,空间充分利用,并且减少了碰撞的几率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for ( int  i= 0 ;i< 10 ;i++){
       System.out.println(
         "数值i=" +i+ ", 二进制=" +Integer.toBinaryString(i)+ "(" +Integer.toBinaryString( 7 )+ ")" + " ,和7按位与=" +(i& 7 ));
}
数值i= 0 , 二进制= 0 111 ) ,和 7 按位与= 0
数值i= 1 , 二进制= 1 111 ) ,和 7 按位与= 1
数值i= 2 , 二进制= 10 111 ) ,和 7 按位与= 2
数值i= 3 , 二进制= 11 111 ) ,和 7 按位与= 3
数值i= 4 , 二进制= 100 111 ) ,和 7 按位与= 4
数值i= 5 , 二进制= 101 111 ) ,和 7 按位与= 5
数值i= 6 , 二进制= 110 111 ) ,和 7 按位与= 6
数值i= 7 , 二进制= 111 111 ) ,和 7 按位与= 7
数值i= 8 , 二进制= 1000 111 ) ,和 7 按位与= 0
数值i= 9 , 二进制= 1001 111 ) ,和 7 按位与= 1

 

(6)HashMap的整体结构啥样?

整体情况见下图,包括继承实现关系以及属性等。

1、HashMap中包含了一个Entry的数组,是存放数据的地方,每一个数组元素是一个Entry对象,Entry中有属性next,

如果两个key经过hash后,在数组中index相同,则会保存在同一个位置,通过next属性来形成链表结构。

2、size是数组的大小,threshold是数组扩充的阀值,modCount是table被修改的次数,这个在迭代器中有用,

loadFactor是数组扩充阀值系数,threshold=loadFactor*table.length。


HashMap原理机制自问自答

 

(7)HashMap的添加属性以及扩容是如何进行的?

废话少说,直接上代码。

1、添加属性的时候,如果两个key的index位置相同,则会通过链表保存在同一个数据元素中,而后添加的在链表的前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void  addEntry( int  hash, K key, V value,  int  bucketIndex) {
        /**
         * 首先把index中的值赋予一个对象e,
         * 从这里能够看出,如果两个key的hash值相同,那么在数组中的位置index会相同,
         * 那此时这两个key就需要组成链条来同时保存在这一个位置中,
         * 后一个添加的Entry总是在链条的第一个
         */
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] =  new  Entry<K,V>(hash, key, value, e);
        //如果目前数组的长度大于阀值,则进行resize,扩充为原来的2倍
        if  (size++ >= threshold){
                resize( 2  * table.length);
        }
    }

2、在添加属性的时候,每次都会判断一下是否需要扩容,若果达到了阀值,则进行扩容,

扩容的时候会重新new一个table出来,然后新老数据数据进行转换,

调用transfer方法,transfer方法通过循环遍历的形式记性数据的“交接”,

注意一点,while里面的代码会造车在多线程并发下put出现死循环情况,如果涉及到多线程put情况,不要使用HashMap。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void  resize( int  newCapacity) { //table的数组容量大于了阀值threshold,则进行扩充,变为原来的2倍;
        Entry[] oldTable = table;
        int  oldCapacity = oldTable.length;
        if  (oldCapacity == MAXIMUM_CAPACITY) { //如果已经达到了最大值,则threshold为Integer最大值,数组不进行扩充
            threshold = Integer.MAX_VALUE;
            return ;
        }
                               
        Entry[] newTable =  new  Entry[newCapacity];
        //新老数组数据转换,将老数组中的数据赋予新的table
        transfer(newTable);
        //将新的table赋值给引用,每次扩充,需要重新new一个数组,抛弃原先的数组
        table = newTable;
        threshold = ( int )(newCapacity * loadFactor);
    }
                               
    void  transfer(Entry[] newTable) {
        Entry[] src = table;
        int  newCapacity = newTable.length;
        //循环遍历数组中的每个Entry
        for  ( int  j =  0 ; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if  (e !=  null ) {
                src[j] =  null ;
                /**
                 * while循环遍历一个数组元素的链表,把原来链表的顺序反置了
                 * 多线程并发put下,在进行扩充的时候,会造成死循环;
                 * Entry1-->Entry2-->null   正常情况下,顺序反置回事Entry2-->Entry1-->null
                 * 多线程下会出现:Entry1-->Entry2,Entry2-->Entry1的情况,在while处造成死循环
                 */
                do  {
                    Entry<K,V> next = e.next;
                    //从这里看出,元素在数组中的位置重新进行了计算
                    int  i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                while  (e !=  null );
            }
        }
    }

 

(8)hash碰撞问题HashMap如何解决的?

传入的数据,会出现key经过hash后,hash值相同,这就是hash碰撞问题,

HashMap如何解决这种碰撞问题的呢,看代码可以得出结论。

每个数组元素是一个Entry对象,对象中有个next的应用,指向下一个,对于hash值相同,则在Entry中以链表的形式进行存储。

见put函数代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public  V put(K key, V value) {
       //如果key是null,则调用单独的方法
      if  (key ==  null ){
           return  putForNullKey(value);
       }
       //获取key的hash值,通过key值的hashCode值来进行高位转换
      int  hash = hash(key.hashCode());
       //通过hash值和数组长度进行按位与,获取这个key值在数据中的位置
      int  i = indexFor(hash, table.length);
        /**
         * 获取数组中index为i的Entry,如果entry不为空,则进行判断是否相同,如果相同则新老value进行替换;
         * 这里有个for循环,因为一个数据元素中可能保存了一个Entry的链表
         */
      for  (Entry<K,V> e = table[i]; e !=  null ; e = e.next) {
          Object k;
          //hash值相同,并且==或者equals,则表明两个对象相同
          if  (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
              V oldValue = e.value;
              e.value = value;
              e.recordAccess( this );
              return  oldValue;
          }
      }
      //如果index为i的数组中是null,则调用addEntry来添加新的Entry
      modCount++;
       //传入这个entry的hash值,KV,以及在数组中的位置
      addEntry(hash, key, value, i);
      return  null ;
  }