面试之HashMap

1.什么是集合框架

Java的集合主要有两个根接口Collection和Map派生出来的，Collection派生出来了三个子接口：List,Queue,Set。因此Java集合大致可分为List,Queue,Set,Map四种体系结构。

2.HashMap与TreeMap

HashMap是直接实现Map接口，而TreeMap是实现SortedMap接口的，所以两个还是有不同点。

3.HashSet与TreeSet

4.HashMap的底层数据结构

在jdk1.7和jdk1.8中底层实现是有所区别的。

在jdk1.7中，由“数组 + 链表”组成，数组是HashMap的主体，链表主要为了解决哈希冲突而存在的。

在jdk1.8中，由“数组 + 链表 + 红黑树”组成，当链表过长，会严重影响HashMap的性能，红黑树搜索的时间复杂度为O(logn),而链表为O(n)，因此在jdk1.8引入了红黑树，在达到一定条件之后会进行转换：

• 当链表超过8且数据总量超过64才会转红黑树
• 将链表转换成红黑树前会进行判断，如果当前数组的长度小于64，那么会选择先进性扩容，而不是转为红黑树，以减少搜索时间。 

5.HashMap插入数据的原理

1. 首先根据key值计算哈希值，找到该元素在数组中存储的下标
2. 如果数组为空，则首先调用resize初始化数组
3.  如果没有哈希冲突，则直接放在对象下标的位置
4. 如果冲突了，且key值存在，则直接覆盖掉value值
5. 如果冲突之后发现该节点是红黑树，就将这个节点挂在红黑树上
6. 如果冲突后是链表，判断该链表是否大于8，如果大于8并且数组容量小于64，就进行扩容；如果链表大于8并且数组容量大于64，则将这个结构转为红黑树；否则，链表插入键值对，如果key存在，就覆盖掉value.

 6.Hash初始容量大小的设置以及扩容

6.1初始容量的大小

在new 一个HashMap时候，因为它使用的是懒加载的方式，所以并不会立即初始化数组。而是等到第一次添加元素的时候，才会初始化数组。一般如果不传入参数，初始默认大小为16，负载因子为0.75，但是如果我们传入参数时，并不会按照所传入的参数进行初始化，首先判断所传入的参数是不是2的n次方，如果是则按照所传参数初始化，如果不是2的n次方，那么就会按照大于你设置的那个值但是最接近你设置的那个值的2的n次方进行设置。例如：传入10，不是2的n次方，2^4刚好是大于10且为2的n次方，所以初始化大小为16.

6.2扩容

在什么时候进行扩容呢？

threshold = 容量 * 加载因子。所以当键值对的数量大于threshold时候，此时需要扩容，扩容是是将原来数组扩大2倍，并将原来数组的对象放入到新的数组当中。

7.HashMap和HashTable

HashMap不是线程安全的：

HashMap是map接口的子类，是将键映射到值的对象，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap允许null key和null value，而hashtable不允许。

HashTable是线程安全。

HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，效率上可能高于Hashtable。

最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步。 Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差。

8.ConcurrentHashMap

虽然jdk提供了HashMap和HashTable但是如何同时满足线程安全和效率高呢，显然这两个都无法满足，所以就诞生了ConcurrentHashMap神器，让我们应用于高并发场景。

该神器采用了分段锁策略，通过把整个Map分成N个Segment（类似HashTable），可以提供相同的线程安全，效率提升N倍，默认提升16倍。ConcurrentHashMap的优点就是HashMap和HashTable的缺点，当然该神器也是不支持键值为null的

9.解决hash冲突的方法有哪些，HashMap用的哪种方法

解决hash冲突的方法有：开放定址法，再哈希法，链地址法，建立公共溢出区，HashMap采用的是链地址法。

• 开放定址法：也称为再散列法，基本思想就是，如果p = H(key)出现冲突时，则以p为基础，再次hash，p1 = H(p),如果p1再次冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址。因此开放定址法所需要的hash表长度大于等于所需要存放的元素。
• 再哈希法：称为双重散列或者多重散列，提供多个不同的hash函数，p1 = H1(key)发生冲突时，再使用不同的哈希函数计算p2  = H2(key),直到没有冲突位置。此方法虽然不会产生堆积，但是计算时间比较长
• 链地址法：将hash值相同的额元素构成一个单链表，并将单链表的头指针放在哈希表的第i个单元，查找，插入和删除主要在链表中进行。适用于频繁的插入和删除
• 建立公共溢出区：将哈希表分为公共表和溢出表，当发生溢出时，所有的溢出数据放在溢出表

10.一般用什么作为HashMap的key

一般使用Integer,String 这种不可变类型作为HashMap的kay，而且String最为常用。

• 因为字符串是不可变的，所在在它被创建的时候hashcode就已经被缓存了，不需要重新计算，这就是String常用作key的原因
• 因为获取对象的时候要用到equals()和hashcode()方法，那么键对象正确的重写这两个方法非常重要，这些类已经很规范的重写了hashcode()和equals();

11HashMap为什么线程不安全

• 多线程下扩容死循环：在jdk1.7中的HashMap使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环；因此在jdk1.8中，使用尾插法插入元素，在扩容时候会保持链表元素的原本顺序，不会出现环形链表的问题
• 多线程下put可能导致元素丢失：多线程同时执行put元素时候，如果计算出来的索引值是相同的，那会造成前一个put操作会被后一个put操作所覆盖，从而导致元素的丢失
• put和get并发，可能为空：在线程1执行put操作时候，需要扩容，扩容之后元素拥有了新的位置，导致线程2在执行get操作的时候可能获取为Null值。