注:文中源码都是基于jdk1.8

1、HashMap特性?

答:实现map接口;以KV的形式存储;不保证顺序;不是线程安全的;

2、HashMap与HashTable区别?

答:
1、hashTable是线程安全的,HashMap是线程不安全的。(这个回答出来就好了,其他点可以挑几个说)
2、HashMap的key、value都可以为null。Hashtable的key、value都不可以为null;
3、HashMap继承于AbstractMap,而Hashtable继承于Dictionary;
4、初始容量大小不一样,HashMap的容量为16;HashTable的容量为11;
5、扩容计算方式不一样,HashMap的扩容为:oldThr << 1 即2*老的容量大小;HashTable的扩容为:(oldCapacity << 1) + 1 即2*老的容量值+1;
6、HashMap的hashcode是自己实现的;HashTable的hashcode是object默认的;

3、HashMap线程不安全实际会如何体现?

答:
第一,如果多个线程同时使用put方法添加元素,假设正好存在两个put的key发生了碰撞(hash和key值一样),那么根据HashMap的实现,这两个key会添加到数组的同一个位置,这样最终就会发生其中一个线程的put的数据被覆盖。

第二,如果多个线程同时检测到元素个数超过数组大小*loadFactor;这样会发生多个线程同时对hash数组进行扩容,都在重新计算元素位置以及复制数据,但是最终只有一个线程扩容后的数组会赋给table,也就是说其他线程的都会丢失,并且各自线程put的数据也丢失。且会引起死循环的错误。

4、HashMap如何变成线程安全?

答:可以使用Collections.synchronizeMap();方法把map变成线程安全;因为这个方法会把所有的方法都加上synchronized;
imagepng
jdk1.5之后,也可以使用ConcurrentHashMap

5、HashMap的数据结构是什么?

答:数组+链表(红黑树)。
源码:
imagepng

链表实现:
imagepng

6、为什么String, Interger这样的wrapper类适合作为键?

答:String是不可变的,所以他的hashcode也是固定的,Integer的hashcode也是固定的;
因为map的put和get都是基于hash的,如果你的hash不固定,那么你存进去可能就获取不到了。

6.1、我们可以使用自定义的对象作为键吗?

答:可以的。
只要我们自己实现对象的hashcode和equals,保证put到map之后,他的hashcode不会变了,就可以。

7、HashMap初始化传入的容量参数的值就是HashMap实际分配的空间么?

答:不一定;
从源码看,
imagepng
imagepng
tableSizeFor方法会对传入的容量进行计算,经过多次无符号右移,找到大于等于initialCapacity的最小的2的幂。例如你传了7,那么initialCapacity为8;
如图打断点,可以看到输出结果。
imagepng

8、什么是hash?

答:把任意长度的输入,通过哈希算法,变换成固定长度的输出,所输出的称为哈希值。一般用于快速查找和加密算法
imagepng

8.1、什么是hash表?

哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
imagepng

9、HashMap中hash函数是怎么实现的?

答:
imagepng
对key的hashcode值先无符号右移16位,再与hashcode值进行亦或操作。
他的最终的目的是让散列分布地更加均匀。

10、HashMap中put的工作原理?

答:
1、对key进行hash函数计算;
2、获取链表的长度,并计算出hash在链表中的下标;
3、当前下标不存在Node,那么就创建一个新的Node;
4、如果当前下标存在Node,判断是否发生碰撞;
5、如果没有发生碰撞,就直接放到Node[]中;
6、如果发生了碰撞,以链表的形式放到Node[]的next中;如果链表的长度大于等于8,且Node[]的长度大于64,就把该链表切换为红黑树存储;
7、如果节点已经存在,就替换老的value;
8、如果Node[]超过阈值(LOAD_FACTOR*CAPACITY),就要进行扩容;

11、HashMap中get的工作原理?

答:
1、先对key的hashCode进行hash;
2、计算出hash所在的下标(n - 1) & hash,获取Node[]里的第一个Node;
3、总是比较第一个节点,如果hash和key都相等,那么直接返回;
4、如果发生了碰撞,那么需要判断是链表存储还是红黑树存储;
5、如果是红黑树存储,那么根据find来查找;
6、如果是链表存储,那么依次循环比较hash和key的值是否相等;

12、HashMap扩容机制是什么?

答:
1.扩容:容量扩充为原来的两倍(2 * table.length);
2.移动:对每个节点重新计算哈希值,重新计算每个元素在数组中的位置,将原来的元素移动到新的哈希表中。

13、HashMap什么时候扩?

答:
在put的时候,如图判断是否需要进行扩容。
imagepng
如果超过了负载因子的大小,那么会调用resize()方法,进行扩容。

14、HashMap每次扩多少?

答:
如图,每次扩容都是CAPACITY的2倍:
imagepng

15、重新调整HashMap大小存在什么问题吗?

答:
(当多线程的情况下,可能产生条件竞争(race condition))
当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。这个时候,你可以告诉面试官,在多线程的情况下,我会使用ConcurrentHashMap。

16、HashMap中如何解决碰撞问题?

答:
因为两个值的hashcode相同,所以他在Node[]里的下标相同,就发生碰撞了;HashMap使用链表的方式来存储那些碰撞的数据。jdk1.8之后如果链表太长,会使用红黑树。
imagepng

链表和红黑树结构:
imagepng

17、如何减少碰撞?

答:
使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。

18、HashMap中Entry链表太长,查找的时间复杂度可能达到 O(n),怎么优化?

答:
将链表转为红黑树,实现 O(logn) 时间复杂度内查找。JDK1.8 已经实现了。

19、如何提升性能?

答:
创建map的时候,尽量指定map的初始容量大小,这样就可以减少resize。

20、什么是Hash攻击?

答:
通过请求大量key不同,但是hashCode相同的数据,让HashMap不断发生碰撞,硬生生的变成了SingleLinkedList。这样put/get性能就从O(1)变成了O(N),CPU负载呈直线上升,形成了放大版DDOS的效果,这种方式就叫做hash攻击。在Java8中通过使用TreeMap,提升了处理性能,可以一定程度的防御Hash攻击。

可以加微信一起交流技术,记得备注:技术
不然通不过验证
_20181130175730jpg

本文为博主原创文章,未经博主允许不得转载。
更多内容请访问:IT源点

注意:本文归作者所有,未经作者允许,不得转载