HashMap是一个比较常用的数据结构，它的底层原理涉及到很多的java基础知识，也是面试官比较喜欢考查的一个点。博主以前也看过很多关于HashMap相关的博客、推文，但一直眼高手低、走马观花看了就忘， 后来终于下定决心好好死嗑一下记下笔记，死嗑了一天后七七八八地整理出来以下笔记，笔记内容应该还不是那么完整，有很多的地方没有提到，在后续的学习中有新的发现也会进行补充。

HashMap简介

• HashMap是Map接口的实现，允许空的KV键值对，HashMap是一个非线程安全的容器，如果想构造线程安全的Map考虑使用CurrentHashMap，HashMap内部存储的键值对是乱序的
• HashMap底层数据结构是数组+链表，数组在HashMap中又称为桶，遍历HashMap老板娘的损耗为桶的数量+KV数量
• HashMap中两个重要的因素：初始容量、负载因子，初始容量指的是桶的数量，负载因子 一种衡量哈希表填充程度的标准，当哈希表中的entry超过了负载因子和当前容量，哈希表会进行rehash操作，内部数据重构rebuilt

HashMap底层结构

HashMap中的重要内部类和接口

1. Node内部类

Node节点是用来存储HashMap的一个个实例，实现了Map.Entry接口

• Map.Entry接口

// 一个map 的entry 链，这个Map.entrySet()方法返回一个集合的视图，包含类中的元素，
// 这个唯一的方式是从集合的视图进行迭代，获取一个map的entry链。这些Map.Entry链只在
// 迭代期间有效。
interface Entry<K,V> {K getKey();V getValue();V setValue(V value);boolean equals(Object o);int hashCode();
}

• Node内部类的变量

Node结点存储四个变量：key、value、hash、next

Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;
}

2. 内部类KeySet

keySet 类继承于 AbstractSet 抽象类，它是由 HashMap 中的 keyset() 方法来创建 KeySet 实例的，旨在对HashMap 中的key键进行操作

public Set<K> keySet() {Set<K> ks = keySet;if (ks == null) {ks = new KeySet();keySet = ks;}return ks;}final class KeySet extends AbstractSet<K> {...}

3. 内部类Values
   与KeySet类似，它是对KV键值对中的values进行操作，返回的是一个Collection

public Collection<V> values() {Collection<V> vs = values;if (vs == null) {vs = new Values();values = vs;}return vs;}final class Values extends AbstractCollection<V> {...}

HashMap 1.7 的底层结构

JKD1.7下，HashMap就是使用桶(数组)加链表的方式实现，用链表来处理哈希冲突，当桶中元素过多时，容易使得一些链表过长，导致查询效率降低

HashMap底层是一个数组

在1.7下Node类是叫Entry类，改个名而已

transient Entry<K,V>[] table;  //1.7
transient Node<K,V>[] table;   //1.8

HashMap 1.8 的底层结构

相比1.7做了一些改动，当一个桶里的元素大于8时，就会把链表转为红黑树，优化查询效率；还重写了 resize() 方法，结构如下

HashMap中的重要属性

1. 初始容量

HashMap的默认初始容量是由DEFAULT_INITIAL_CAPACITY管理的

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

2. 最大容量

左移30位后1是在二进制表示从左往右数的第二位，第一位是符号位，所以不能再左移

static final int MAXIMUM_CAPACITY = 1 << 30;

3. 默认负载因子

负载因子和扩容机制有关，当存储数量>容量 * 负载因子时，就会把HashMap容量扩大为原来的2倍

static final float DEFAULT_LOAD_FACTOR = 0.75f;

4. 树化阈值
   当桶中的元素数量大于阈值(8)，就会把它转为红黑树

static final int TREEIFY_THRESHOLD = 8;

5. 链表阈值

当桶中的元素数量小于阈值时(6)，就会把它转为链表

static final int UNTREEIFY_THRESHOLD = 6;

6. 扩容临界值

当桶的容量小于这个值的时候，先扩容，而后再考虑树化

static final int MIN_TREEIFY_CAPACITY = 64;

7. 节点数组

Node数组，HashMap中的数组+链表的数组，在第一次使用的时候进行初始化，后面需要扩容调用resize()方法把长度变为原来的2倍

transient Node<K,V>[] table;

8. 键值对数量

transient int size;

9. 修改次数

表示修改次数，用于并发修改HashMap时的快速失败机 制 fail-fast，这个还不太懂以后再学

transient int modCount;

10. 扩容阈值

扩容阈值就是容量*负载因子的值

int threshold;

//返回一个大于等于cap的最接近的2的幂次方的数
//cap=8  return 8
//cap=9  return 16
static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

11. 负载因子

数组中数据的密集程度

static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap构造函数

1. 带有初始容量和负载因子的构造函数

public HashMap(int initialCapacity, float loadFactor) {//初始容量小于0抛出异常if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//初始容量大于最大容量，让初始容量等于最大容量if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//负载因子小于等于0抛出异常if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);}

2. 只带有初始容量的构造函数

public HashMap(int initialCapacity) {//调用带初始容量和负载因子的构造函数，负载因子传入默认值this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

3. 无参构造函数

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;}

4. 传入一个map的构造函数

把外部元素批量放入HashMap中

public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}

putVal()方法

我们调用的put()方法，其实就是调用putVal()方法

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
//hash()方法
//返回hashcode和hashcode无符号右移16位进行异或操作后的结果
//无符号右移又称逻辑右移，就是左边补0
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

看完上面一小段接下来就真的是putVal()方法啦

//hash：put放在桶中的位置，会进行hash函数的计算
//key、value：传入的KV
//onlyIfAbsent：是否进行value值的替换
//evict：是否是刚创建HashMap的标志
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 如果table 为null 或者没有为 table 分配内存，就resize一次if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 指定hash值节点为空则直接插入，这个(n - 1) & hash才是表中真正的哈希if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 如果不为空else {Node<K,V> e; K k;// 计算表中的这个真正的哈希值与要插入的key.hash相比if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 若不同的话，并且当前节点已经在 TreeNode 上了else if (p instanceof TreeNode)// 采用红黑树存储方式e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// key.hash 不同并且也不再 TreeNode 上，在链表上找到 p.next==nullelse {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {// 在表尾插入p.next = newNode(hash, key, value, null);// 新增节点后如果节点个数到达阈值，则进入 treeifyBin() 进行再次判断if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 如果找到了同 hash、key 的节点，那么直接退出循环if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;// 更新 p 指向下一节点p = e;}}// map中含有旧值，返回旧值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// map调整次数 + 1++modCount;// 键值对的数量达到阈值，需要扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

putVal()方法解读

• 检查table是否为null，是就先执行**resize()**方法
• 计算传入的KV键值对对应在数组的哪个位置(计算下标)：i = (n-1) & hash
• 如果对应位置为null直接创建一个新的Node

tab[i] = newNode(hash, key, value, null);

• 如果不为空，取出这个Node(变量名：p)，比较传入的hash和p.hash是否相等并且p.key和k是否相等，满足条件则将结点插入树中

e = p;

• 如果不满足上述判断，说明结点已经在tab[i]的后面，如果是TreeNode即红黑树存储方式，则

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

• 如果是链表存储的，通过一个for循环遍历链表，如果找到相应的key则跳出循环后修改value，如果遍历到表尾则插入，如果新增结点大于阈值，进行树化

扩容机制resize()方法

照着注释看下来应该就能理解得差不多吧

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;// 存储old table 的大小int oldCap = (oldTab == null) ? 0 : oldTab.length;// 存储扩容阈值int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {// 如果old table数据已达最大，那么threshold也被设置成最大if (oldCap >= MAXIMUM_CAPACITY) {//2^31-1,因为最高位为符号位必须是0，所以最大值是除最高位后所有位都为1threshold = Integer.MAX_VALUE;return oldTab;}//其他情况正常左移1位，把长度直接扩大为原来的两倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 扩容成原来二倍newThr = oldThr << 1; // double threshold}// 如果oldThr                                                                                                                                               !> 0else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 如果old table <= 0 并且 存储的阈值 <= 0else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 如果扩充阈值为0if (newThr == 0) {// 扩容阈值为 初始容量*负载因子float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 重新给负载因子赋值threshold = newThr;// 获取扩容后的数组@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// 如果第一次进行table 初始化不会走下面的代码// 扩容之后需要重新把节点放在新扩容的数组中if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// 重新映射时，需要对红黑树进行拆分((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;// 遍历链表，并将链表节点按原顺序进行分组do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 将分组后的链表映射到新桶中//扩容后还在数组前半段位置的结点if (loTail != null) {loTail.next = null;newTab[j] = loHead;}//放在扩容后半段数组位置的结点if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

get()方法

• 如果table为null或者length==0或者数组对应下标位置的值为null，直接返回null
• 否则找到tab[i]的元素first，判断first结点的hash和key是否与传入的hash和key相等，如果相等直接返回结点
• 如果不相等，并且first的next为null，直接返回null
• 如果有next判断first是否为TreeNode，是则调用getTreeNode()方法查找并返回结点
• 如果不是TreeNode则是链表，遍历链表进行查找，找到就返回结点，找不到返回null

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 找到真实的元素位置if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 总是会check 一下第一个元素if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 如果不是第一个元素，并且下一个元素不是空的if ((e = first.next) != null) {// 判断是否属于 TreeNode，如果是 TreeNode 实例，直接从 TreeNode.getTreeNode 取if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 如果还不是 TreeNode 实例，就直接循环数组元素，直到找到指定元素位置do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

HashMap的遍历

HashMap遍历的基类 HashIterator，它是一个内部抽象类，它里面有三个方法：

hasNext()、remove()、nextNode()

abstract class HashIterator {Node<K,V> next;        // next entry to returnNode<K,V> current;     // current entryint expectedModCount;  // for fast-failint index;             // current slotHashIterator() {expectedModCount = modCount;Node<K,V>[] t = table;current = next = null;index = 0;if (t != null && size > 0) { // advance to first entry//这里的判断只要找到不为null的结点，在nextNode()方法中还要考虑结点后面是否还有元素do {} while (index < t.length && (next = t[index++]) == null);}}public final boolean hasNext() {return next != null;}final Node<K,V> nextNode() {Node<K,V>[] t;Node<K,V> e = next;if (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();//除了跟构造方法中的判断，还需要判断结点的末尾是否为空if ((next = (current = e).next) == null && (t = table) != null) {do {} while (index < t.length && (next = t[index++]) == null);}return e;}public final void remove() {Node<K,V> p = current;if (p == null)throw new IllegalStateException();if (modCount != expectedModCount)throw new ConcurrentModificationException();current = null;K key = p.key;removeNode(hash(key), key, null, false, false);expectedModCount = modCount;}}

其中的remove()方法，后面会去调用removeNode()方法，大概流程就是：根据hash找到对应桶的位置，遍历链表，删除对应结点

final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;
}

有三个实现这个抽象内部类的类，分别是

• KeyIterator 遍历key
• ValueIterator 遍历value
• EntryIterator 遍历Entry

final class KeyIterator extends HashIteratorimplements Iterator<K> {public final K next() { return nextNode().key; }}final class ValueIterator extends HashIteratorimplements Iterator<V> {public final V next() { return nextNode().value; }}final class EntryIterator extends HashIteratorimplements Iterator<Map.Entry<K,V>> {public final Map.Entry<K,V> next() { return nextNode(); }}