【原创】HashMap复习精讲 (3)

当链表转为红黑树后，什么时候退化为链表?
为6的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

(5)HashMap的并发问题?

此题可以组成如下连环炮来问

HashMap在并发编程环境下有什么问题啊?

在jdk1.8中还有这些问题么?

你一般怎么解决这些问题的？

HashMap在并发编程环境下有什么问题啊?

(1)多线程扩容，引起的死循环问题

(2)多线程put的时候可能导致元素丢失

(3)put非null元素后get出来的却是null

在jdk1.8中还有这些问题么?

在jdk1.8中，死循环问题已经解决。其他两个问题还是存在。

你一般怎么解决这些问题的？

比如ConcurrentHashmap，Hashtable等线程安全等集合类。

(6)你一般用什么作为HashMap的key?

此题可以组成如下连环炮来问

健可以为Null值么?

你一般用什么作为HashMap的key?

我用可变类当HashMap的key有什么问题?

如果让你实现一个自定义的class作为HashMap的key该如何实现？

健可以为Null值么?
必须可以，key为null的时候，hash算法最后的值以0来计算，也就是放在数组的第一个位置。

你一般用什么作为HashMap的key?
一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。

(1)因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。

(2)因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。

我用可变类当HashMap的key有什么问题?
hashcode可能发生改变，导致put进去的值，无法get出，如下所示

HashMap<List<String>, Object> changeMap = new HashMap<>(); List<String> list = new ArrayList<>(); list.add("hello"); Object objectValue = new Object(); changeMap.put(list, objectValue); System.out.println(changeMap.get(list)); list.add("hello world");//hashcode发生了改变 System.out.println(changeMap.get(list));

输出值如下

java.lang.Object@74a14482 null

如果让你实现一个自定义的class作为HashMap的key该如何实现？
此题考察两个知识点

重写hashcode和equals方法注意什么?

如何设计一个不变类

针对问题一，记住下面四个原则即可
(1)两个对象相等，hashcode一定相等
(2)两个对象不等，hashcode不一定不等
(3)hashcode相等，两个对象不一定相等
(4)hashcode不等，两个对象一定不等
针对问题二，记住如何写一个不可变类
(1)类添加final修饰符，保证类不被继承。
如果类可以被继承会破坏类的不可变性机制，只要继承类覆盖父类的方法并且继承类可以改变成员变量值，那么一旦子类以父类的形式出现时，不能保证当前类是否可变。

(2)保证所有成员变量必须私有，并且加上final修饰
通过这种方式保证成员变量不可改变。但只做到这一步还不够，因为如果是对象成员变量有可能再外部改变其值。所以第4点弥补这个不足。

(3)不提供改变成员变量的方法，包括setter
避免通过其他接口改变成员变量的值，破坏不可变特性。

(4)通过构造器初始化所有成员，进行深拷贝(deep copy)
如果构造器传入的对象直接赋值给成员变量，还是可以通过对传入对象的修改进而导致改变内部变量的值。例如：

public final class ImmutableDemo { private final int[] myArray; public ImmutableDemo(int[] array) { this.myArray = array; // wrong } }

这种方式不能保证不可变性，myArray和array指向同一块内存地址，用户可以在ImmutableDemo之外通过修改array对象的值来改变myArray内部的值。
为了保证内部的值不被修改，可以采用深度copy来创建一个新内存保存传入的值。正确做法：

public final class MyImmutableDemo { private final int[] myArray; public MyImmutableDemo(int[] array) { this.myArray = array.clone(); } }

(5)在getter方法中，不要直接返回对象本身，而是克隆对象，并返回对象的拷贝
这种做法也是防止对象外泄，防止通过getter获得内部可变成员对象后对成员变量直接操作，导致成员变量发生改变。

总结

这篇文章能概括大部分HashMap的面试题了，希望大家有所收获！