【Android面试】Java| HashMap面试题整理

一、HashMap有用过吗？您能给我说说他的主要用途吗？

答：有用过，我在平常工作中经常会用到HashMap这种数据结构，HashMap是基于Map接口实现的一种键-值对 <key,value>的存储结构，允许null值，同时非有序，非同步(即线程不安全)。HashMap的底层实现是数组 + 链表 + 红黑树（JDK1.8增加了红黑树部分）。它存储和查找数据时，是根据键key的hashCode的值计算出具体的存储位置。 HashMap最多只允许一条记录的键key为null，HashMap增删改查等常规操作都有不错的执行效率，是ArrayList和 LinkedList等数据结构的一种折中实现。

二、您能说说HashMap常用操作的底层实现原理吗？如存储put(K key, V value)，查找get(Object key)，删除remove(Object key)，修改replace(K key, V value)等操作。

答：调用put(K key, V value)操作添加key-value键值对时，进行了如下操作： 判断哈希表Node<K,V>[] table是否为空或者null，是则执行resize()方法进行扩容； 根据插入的键值key的hash值，通过(n - 1) & hash当前元素的hash值 & hash表长度 - 1（实际就是 hash值 % hash表长度）计算出存储位置table[i]； 如果存储位置没有元素存放，则将新增结点存储在此位置table[i]； 如果存储位置已经有键值对元素存在，则判断该位置元素的hash值和key值是否和当前操作元素一致，一致则证明是修改value操作，覆盖value即可； 当前存储位置即有元素，又不和当前操作元素一致，则证明此位置table[i]已经发生了hash冲突，则通过判断头结点是否是treeNode，如果是treeNode则证明此位置的结构是红黑树，已红黑树的方式新增结点； 如果不是红黑树，则证明是单链表，将新增结点插入至链表的最后位置，随后判断当前链表长度是否 大于等于 8，是 则将当前存储位置的链表转化为红黑树。遍历过程中如果发现key已经存在，则直接覆盖value。插入成功后，判断当前存储键值对的数量大于阈值threshold 是则扩容。

三、hash冲突（或者叫hash碰撞）是什么？为什么会出现这种现象，如何解决hash冲突？

答：hash冲突： 当我们调用put(K key, V value)操作添加key-value键值对，这个key-value键值对存放在的位置是通过扰动函数(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)计算键key的hash值。随后将这个hash值 % 模上 哈希表 Node<K,V>[] table的长度 得到具体的存放位置。所以put(K key, V value)多个元素，是有可能计算出相同的存放位 置。此现象就是hash冲突或者叫hash碰撞。

hash冲突的避免：既然会发生hash冲突，我们就应该想办法避免此现象的发生，解决这个问题最关键就是如果生成元素的hash值。Java是使用“扰动函数”生成元素的hash值。

四、HashMap的容量为什么一定要是2的n次方？

答：因为调用put(K key, V value)操作添加key-value键值对时，具体确定此元素的位置是通过 hash值 % 模上哈希表Node<K,V>[] table的长度 hash % length 计算的。但是"模"运算的消耗相对较大，通过位运算h & (length-1)也可以得到取模后的存放位置，而位运算的运行效率高，但只有length的长度是2的n次方时，h & (length-1) 才等价于 h %length。 而且当数组长度为2的n次幂的时候，不同的key算出的index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

五、您能说说HashMap和HashTable的区别吗？

1）容器整体结构： HashMap的key和value都允许为null，HashMap遇到key为null的时候，调用putForNullKey方法进行处理，而对 value没有处理。Hashtable的key和value都不允许为null。Hashtable遇到null，直接返回NullPointerException。

2） 容量设定与扩容机制： HashMap默认初始化容量为 16，并且容器容量一定是2的n次方，扩容时，是以原容量 2倍 的方式 进行扩容。 Hashtable默认初始化容量为 11，扩容时，是以原容量 2倍 再加 1的方式进行扩容。即int newCapacity = (oldCapacity << 1) + 1;。

3） 散列分布方式（计算存储位置）： HashMap是先将key键的hashCode经过扰动函数扰动后得到hash值，然后再利用 hash & (length - 1)的方式代替取模，得到元素的存储位置。Hashtable则是除留余数法进行计算存储位置的（因为其默认容量也不是2的n次方。所以也无法用位运算替代模运算），int index = (hash & 0x7FFFFFFF) % tab.length;。由于HashMap的容器容量一定是2的n次方，所以能使用hash & (length - 1)的方式代替取模的方式计算元素的位置提高运算效率，但Hashtable的容器容量不一定是2的n次方，所以不能使用此运算方式代替。

4）线程安全（最重要）： HashMap 不是线程安全，如果想线程安全，可以通过调用synchronizedMap(Map<K,V> m)使其线程安全。但是使用时的运行效率会下降，所以建议使用ConcurrentHashMap容器以此达到线程安全。Hashtable则是线程安全的，每个操作方法前都有synchronized修饰使其同步，但运行效率也不高，所以还是建议使用ConcurrentHashMap容器以此达到线程安全。