HashMap的一些面试点

数据结构

数组+链表

·tip：当某一个key长度超过8，则链表转化成红黑树存储。

Hash算法优化

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

【优化】对每个hash值，让高低十六位进行了异或运算，让它的低16位同时保持高低16位的特征，尽量避免一些hash值后续出现冲突，出现在同一个位置上。

eg:

1111  1111  1111  1111 1111 1010  0111 1100 ->(原hash值,没有优化的hash值)

0000 0000 0000 0000 1111 1111  1111  1111 ->(原hash值，右移16位)

1111  1111  1111 1111 0000 0101 1000  0011 ->(原hash值，同右移16位后，进行异或运算)

·tip： 与运算（逻辑乘），对应位全是1结果为1，否则为0；或运算（逻辑加），对应位全是0结果为0，否则为1；

           异或运算，参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为 0。

寻址算法优化：（n-1）& hash

【优化】用与运算替代取模，提升性能

假如n=16，n是数组长度

0000 0000 0000 0000 0000 0000 0000 1111 ->(n-1)

1111  1111  1111 1111  0000 0101 1000  0011 ->(异或后的hash)

0000 0000 0000 0000 0000 0000 0000  0011 ->(&结果)

如何解决hash碰撞问题

数组的一个位置存在多个值，就会变成一个链表，这个链表是红黑树结构；

时间复杂度由O(n)->O(logn)；

HashMap是如何进行扩容

底层是一个数组，当数组满了以后就会自动进行扩容，变成一个更大的数组。

数组长度=16；

eg1：

n-1    :   0000 0000 0000 0000 0000 0000 0000 1111

hash1:  1111  1111  1111  1111  0000 1111 0000 0101

&结果：0000 0000 0000 0000 0000 0000 0000 0101 =5（index=5的位置）

eg2：

n-1    :   0000 0000 0000 0000 0000 0000 0000 1111

hash2:  1111  1111  1111  1111  0000 1111 0001 0101

&结果：0000 0000 0000 0000 0000 0000 0000 0101 =5（index=5的位置）

数组长度为16的时候，他们俩个的hash值的位置是一样的，用链表来处理，出现一个hash冲突问题。

如果数组的长度扩容成32位，重新对每个hash值进行寻址，也就是每个hash值跟新数组的length-1进行与操作。

eg1：

n-1    :   0000 0000 0000 0000 0000 0000 0001 1111

hash1:  1111  1111  1111  1111  0000 1111 0000 0101

&结果：0000 0000 0000 0000 0000 0000 0000 0101 =5（index=5的位置）

eg2：

n-1    :   0000 0000 0000 0000 0000 0000 0001 1111

hash2:  1111  1111  1111  1111  0000 1111 0001 0101

&结果：0000 0000 0000 0000 0000 0000 0001 0101 =21（index=21的位置）