最近参与公司的实习生招聘工作，面试了几位实习生，我有一道每次面试都必问的题目【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，因此这些细节问题并未涉及。