昨天面试时又问到了关于HashMap相关的问题，而我虽然大致回答上来了，但是回答的并不是很好。所以借此机会，把关于HashMap的知识点再重新梳理下，增进理解，加深记忆。
在讲何为HashMap之前，我们必须得先搞定另一个概念：Map。
从宏观意义上来讲，Map代表的是一种映射关系。比如有两个集合，集合A和集合B，A集合当中的每一个元素都能在B集合中找到唯一的一个值与之对应，我们就把A集合和B集合共同组成的这种映射关系称之为Map。而A集合中的元素，我们称之为Key，即键；B集合中的元素，我们称之为值，即Value。所以，Map又被称之为双列集合。其实，Map集合在我们生活中的应用无处不在，比如身份证和姓名，IP地址和MAC地址等等。同时，我们也可以感觉到，Key-Value这种数据结构很符合人类的存储习惯。
而HashMap相比于Map而言，前面多加了个名字叫做Hash的前缀。我们来看一下什么是Hash。
先看一下Hash算法的定义：将任意长度的数据映射到有限长度的域上面。翻译成人话，意思就是对一串数据m进行杂糅，输出为另一段固定长度的数据h，作为这段数据的特征（数据指纹）。也就是说，无论输入的数据m有多大，长度或短或长，经过Hash算法的运算过后，其输出值h的长度永远都是固定的。至于Hash算法的具体实现细节，我们暂且不讲。
所以综上所述，HashMap就是一个基于Hash算法的Map实现。
搞清楚什么是HashMap之后，我们接下来要思考另一个问题：为什么需要HashMap呢？
我们都知道，集合框架是用来存储数据的。而对于数据的存储而言，插入、删除和遍历的速度变得至关重要。对于其他的Java集合类，比如ArrayList、LinkedList和Vector，它们统统都是在某一方面存在着缺陷，要么插入删除慢，要么遍历速度慢。而为了实现快速查找，HashMap底层使用了数组，从而达到了时间复杂度为O(1)的查找效率；同时有了Hash算法的加入，解决Hash冲突所采用的链地址法和后期红黑树的加入，HashMap的插入和删除性能也变得十分优异。
首先，我们来看一下HashMap定义部分的源码
1 public class HashMap<K,V> extends AbstractMap<K,V> 2 implements Map<K,V>, Cloneable, Serializable { 3 private static final long serialVersionUID = 362498820763181265L; 4 //默认初识化大小。此处1<<4表示将1向左移动四位 5 //0000 0001 ----> 0001 0000 6 //默认会创建16个结点。节点的个数要适当，如果太多遍历哈希表会比较慢，太少的话则会触发扩容 7 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 8 //最大容量 9 static final int MAXIMUM_CAPACITY = 1 << 30; 10 //默认加载因子.初始情况下，当键值对的数量>16*0.75=12时，就会触发扩容 11 static final float DEFAULT_LOAD_FACTOR = 0.75f; 12 //默认转为红黑树的阈值。即当某个结点下面挂载的链表长度大于8时，链表将转为红黑树 13 static final int TREEIFY_THRESHOLD = 8; 14 //在哈希表扩容时，如果发现链表的长度小于6，则会由树退化成链表 15 static final int UNTREEIFY_THRESHOLD = 6; 16 //在由链表转换为红黑树之前，还需再进行一次判断，只有当整个哈希表的键值对总数量大于64时才会发生转换 17 //这是为了避免哈希表在建立初期，多个键值对恰巧都被放入了同一个链表中而导致不必要的转换 18 static final int MIN_TREEIFY_CAPACITY = 64; 19 //HashMap主体的每个结点定义，即数组的结点定义 20 static class Node<K,V> implements Map.Entry<K,V> { 21 final int hash;//哈希值，用来定位数组的索引位置 22 final K key; 23 V value; 24 Node<K,V> next;//链表的下一个Node 25 ? 26 Node(int hash, K key, V value, Node<K,V> next) { 27 this.hash = hash; 28 this.key = key; 29 this.value = value; 30 this.next = next; 31 } 32 ? 33 public final K getKey() { return key; } 34 public final V getValue() { return value; } 35 public final String toString() { return key + "=" + value; } 36 //自定义的hashCode()方法 37 public final int hashCode() { 38 //此处的^为异或运算。相同二进制位进行^运算，结果为0；不同，结果为1 39 //1001^1100=0101 40 return Objects.hashCode(key) ^ Objects.hashCode(value); 41 } 42 ? 43 public final V setValue(V newValue) { 44 V oldValue = value; 45 value = newValue; 46 return oldValue; 47 } 48 49 public final boolean equals(Object o) { 50 if (o == this) 51 return true; 52 if (o instanceof Map.Entry) { 53 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 54 if (Objects.equals(key, e.getKey()) && 55 Objects.equals(value, e.getValue())) 56 return true; 57 } 58 return false; 59 } 60 } 61 //计算哈希值 62 static final int hash(Object key) { 63 int h; 64 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 65 } 66 //用transient修饰符修饰的变量不参与序列化过程 67 transient Node<K,V>[] table;//哈希表的主干数组 68 transient Set<Map.Entry<K,V>> entrySet;//遍历用 69 transient int size;//哈希表中元素的数量 70 transient int modCount;//标记字段，记录对该哈希表进行结构修改的次数，主要用于迭代器访问时检测哈希表 71 //是否因为删除等其他操作引起内部机构发生变化 72 int threshold;//扩容阈值 73 final float loadFactor;//加载因子
看一下它的构造方法
1 //构造方法1，指定初始容量和负载因子 2 public HashMap(int initialCapacity, float loadFactor) { 3 if (initialCapacity < 0) 4 throw new IllegalArgumentException("Illegal initial capacity: " + 5 initialCapacity); 6 if (initialCapacity > MAXIMUM_CAPACITY) 7 initialCapacity = MAXIMUM_CAPACITY; 8 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 9 throw new IllegalArgumentException("Illegal load factor: " + 10 loadFactor); 11 this.loadFactor = loadFactor; 12 this.threshold = tableSizeFor(initialCapacity); 13 } 14 //构造方法2，指定初始容量 15 public HashMap(int initialCapacity) { 16 this(initialCapacity, DEFAULT_LOAD_FACTOR); 17 } 18 //无参构造方法 19 public HashMap() { 20 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 21 } 22 //指定集合，转换为哈希表 23 public HashMap(Map<? extends K, ? extends V> m) { 24 this.loadFactor = DEFAULT_LOAD_FACTOR; 25 putMapEntries(m, false); 26 }
再看一下最关键的put和get操作
1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 2 boolean evict) { 3 Node<K,V>[] tab; 4 Node<K,V> p; 5 int n, i; 6 //判断table是否初始化，否则对其进行初始化 7 if ((tab = table) == null || (n = tab.length) == 0) 8 n = (tab = resize()).length; 9 //计算存储的索引位置，如果该位置上没有元素，即不发生哈希碰撞，就直接赋值，存储 10 if ((p = tab[i = (n - 1) & hash]) == null) 11 tab[i] = newNode(hash, key, value, null); 12 else { 13 //如果发生哈希碰撞，做以下处理 14 Node<K,V> e; 15 K k; 16 //节点已存在，执行赋值操作 17 if (p.hash == hash && 18 ((k = p.key) == key || (key != null && key.equals(k)))) 19 e = p; 20 //判断链表是否为红黑树 21 else if (p instanceof TreeNode) 22 //为红黑树，对红黑树操作 23 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 24 else { 25 //为链表，对链表操作 26 for (int binCount = 0; ; ++binCount) { 27 if ((e = p.next) == null) { 28 p.next = newNode(hash, key, value, null); 29 //链表长度为8，将链表转化为红黑树进行操作 30 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 31 treeifyBin(tab, hash); 32 break; 33 } 34 //key存在，直接覆盖 35 if (e.hash == hash && 36 ((k = e.key) == key || (key != null && key.equals(k)))) 37 break; 38 p = e; 39 } 40 } 41 if (e != null) { // existing mapping for key 42 V oldValue = e.value; 43 if (!onlyIfAbsent || oldValue == null) 44 e.value = value; 45 afterNodeAccess(e); 46 return oldValue; 47 } 48 } 49 ++modCount;//记录修改的次数 50 //判断是否需要扩容 51 if (++size > threshold) 52 resize(); 53 //空操作 54 afterNodeInsertion(evict); 55 return null; 56 }
简单来讲，哈希表的存放过程分为以下六步：
1.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
2.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3；
3.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；
4.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；
5.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
6.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
原文：https://www.cnblogs.com/majortom/p/13132690.html