最近参与公司的实习生招聘工作，面试了几位实习生，我有一道每次面试都必问的题目【HasmMap的工作原理】，但很遗憾，至今还没遇到令我完全满意的回答。今天这篇文章就来回答下HashMap相关的面试题。
1. 什么是HashMap？
java.util.HashMap是Java语言标准库中的一个容器类，主要用来存储键值对。是数据结构中哈希表在Java语言的一个实现。
哈希表是数据结构中的一个概念，可以存储n个元素，取元素的时间复杂度为O(1).
一般情况下，从n个元素中查找一个元素，时间复杂度为O(n). 为何哈希表能有O(1)的时间复杂度？
因为元素在存储时已经大致确定了位置，查找的时候可以定位到对应的位置，因此时间复杂度为O(1).
2. HashMap中的数据结构
HashMap使用数组+链表的方式实现。
数组的作用主要是定位元素位置。
链表的作用是解决哈希冲突问题。遇到hash值相等的key，就把相应键值使用链表的方式全部保存下来。
3. put操作
put方法定义
public V put(K key, V value)
put操作执行过程：
a. 计算key的hashcode
b. 根据hashcode计算出需要将该键值对存储的位置-即桶的位置
c. 找到桶的位置后，如果桶未被占用，则存入该键值对；若桶中已有数据，则需要遍历桶中数据，并且比较key的equals方法。遇到key相同的，则用新的value，把旧值替换掉（put操作会将旧值覆盖掉）。若没找到，则将该键值对存储在链表的末尾。
4. get操作
get方法定义
public V get(Object key)
get操作执行过程：
a. 计算key的hashcode
b. 根据hashcode，定位该元素所在桶的位置
c. 若桶为空，则返回null；若桶不空，则遍历桶中数据，比较key的equals方法，若遇到相同的元素，则返回对于的value中；没遇到，则返回null
5. 什么样的类型可以作为HashMap的key？
a. 重写hashCode() 和 equals() 方法
HashMap在get/put数据时，需要调用hashCode() 和 equals() 方法，因此只有重写了hashCode() 和 equals() 方法的类，才可以作为HashMap的key。
（hashCode相同，对象不一定相等；对象相等，则hashCode必然相同）
b. 不可变性
不可变性也是必要的，若元素可变，则相应hashCode也会发生变化，调用get()方法时，可能找不到相应的value，甚至可能找到错误的value。
6. 如何计算数组下标
在JDK1.8之前的版本中，是通过key的hashCode()进行hashing，然后将( n-1 & hash)来确定数组下标，即桶的位置。
在JDK1.8版本，将hash值的高16位与低16位进行异或
JDK 1.8：
(h = key.hashCode()) ^ (h >>>16)
这样做的目的主要是为了减少哈希冲突的可能性。特别是数据量较小时，旧的计算方式哈希冲突的可能比较大。
7. HashMap的两个重要概念
容量(Capacity)，即HashMap中数组的大小，也是桶的个数
负载因子(load factor)，也成装载因子 = hashmap中实际保存键值对个数 / hashmap中数组的大小
随着HashMap中元素个数的增多，负载因子增大。如果不做额外的处理，则桶中的链表会越来越长，因此HashMap就无法保证取元素时O(1)的时间复杂度。因此，必须要调整HashMap中数组的大小
HashMap中定义的默认负载因子大小为0.75，当负载因子大于该值时，将对数组进行扩容
8. HashMap其他面试题
HashMap与HashTable区别：Hashtable中加入了锁，线程安全；HashMap线程不安全。也正因为Hashtable中加入了锁，导致性能上要差于HashMap。
ConcurrentHashMap：HashMap、Hashtable在性能和安全性上的一个折中方案。实现原理是ConcurrentHashMap中将Map划分为多个子Map，子Map分别加锁。对一个子Map加锁以后，不影响对其他子Map的访问。
9. 为什么要面试这道题目
a. 考察求职者技术水平.
我一把把这道题目作为第一道面试题来考察求职者。根据回答情况，能大致推测到求职者的水平，方便后续的面试。
零级水平：完全不知道。（当然，这种可能性很少。毕竟HashMap是非常常用的一个工具类）
一级水平：可以回答HashMap的时间复杂度，容量，装载因子等概念
二级水平：回答出get/put操作的完整过程。（多数求职者都没能完整的回答这个问题。能完全回答出这个问题，说明求职者对哈希的思想有完整的理解，而且很可能阅读过HashMap的源码 - 要想写好代码，首先要阅读优秀源代码的习惯）
三级水平：回答出hashCode，equals作用，不可变性，线程安全的Map（基本上满足公司实习生的要求，可以发offer了）
b. 考察求职者表达能力
能够把一件复杂的事情讲的清晰易懂，是件了不起的能力。（笔者在这方面能力有所欠佳）
注：
HashMap中其实允许null作为key，因为在get/put操作时都会对null值做特殊的处理。
本文主要是从哈希表的角度来讲述HashMap，因此这些细节问题并未涉及。