Java学习|HashMap浅析 hashmap|数据结构|java

文章目录

前言
一.HashMap构造函数
二.Node数据
三.put方法

第一部分

resize

第二部分

(n - 1) & hash

第三部分

(1)新旧值一致
(2)节点是TreeNode
(3)hash碰撞
第四部分

四.get方法
总结

前言 HashMap在开发中非常常用，刚好最近有时间分析HashMap，本质上HashMap是数组加上单向链表组合的。下面就简单的分析下HashMap。本文基于JDK1.8
一.HashMap构造函数

// 1.构造一个初始容量为initialCapacity，负载因子为0.75的空的HashMap public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 2.构造一个空的初始容量为initialCapacity，负载因子为loadFactor的HashMap public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }// 3.无参构造函数，默认负载因子为0.75 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }// 4.其实就是把传入的HashMap的数据传入到新的HashMap public HashMap(Map m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

这么多的构造函数主要关注下这个构造函数

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }

前面的各种判断是避免一些瞎操作，传入一些不合规的参数，主要看tableSizeFor函数。

static final int tableSizeFor(int cap) { int n = cap - 1; // 防止cap已经是2的幂时，操作 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; }

这个函数的作用是返回一个比给定整数大且最接近的2的幂次方整数，这里也说明HashMap的容量必须是2的幂次方。关于n的>>>操作可以参考这篇文章一文读懂HashMap总之是为了进行扩容，同时扩容的大小必须是2的幂次方。那么为啥是2的幂次方后面会给出解释。
二.Node数据在研究put之前看下Node，Node做为HashMap中重要的数据。我们来看下它的结构。

static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = https://www.it610.com/article/value; this.next = next; }public final K getKey(){ return key; } public final V getValue(){ return value; } public final String toString() { return key +"=" + value; }public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }public final V setValue(V newValue) { V oldValue = https://www.it610.com/article/value; value = newValue; return oldValue; }public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

可以看到，Node是实现自Map.Entry。其中，key和value就是你通过put传入的key和value。hash是通过key值计算出来的哈希值。next则是指向下一个节点Node的指针，既然已经知道了Node，那么接下来看下put。
三.put方法

transient Node[] table; public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 第一部分 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 第二部分 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; // 第三部分 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 第四部分 if (e != null) { // existing mapping for key V oldValue = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size> threshold) resize(); afterNodeInsertion(evict); return null; }

put方法调用了putVal，putVal有五个值其中比较重要的是key，value，hash三个值。首先看下hash函数。

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

从代码上可以看出，hash值是根据key的hashCode通过位移和异或计算出来的。首先看下异或，异或计算原则是"同(相同)为0(假)，异(不同)为1(真)"。hash值到底是怎么计算？
1.取出key的hashCode
2.hashCode右移16位
3.再和之前的hashCode异或操作。
PS:在Java中如果想表示二进制可以在数字前面加0b。
通过上面的操作，最终计算出相对随机性的hash值。
第一部分这一部分是如果tab为null，或者tab的长度为0就创建一个Node数组，如何创建Node数组主要是看resize方法。
resize

final Node[] resize() {// 保存当前table Node[] oldTab = table; // 保存当前table的容量 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 保存当前阈值 int oldThr = threshold; // 初始化新的table容量和阈值 int newCap, newThr = 0; if (oldCap > 0) { // 如果当前table大于MAXIMUM_CAPACITY，更新阀值是Integer.MAX_VALUE if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 如果当前容量两倍小于MAXIMUM_CAPACITY且大于等于默认值 // 则扩容新阀值为当前阀值的两倍。 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 当前阀值大于0，则当前阀值赋给新的table容量，否则计算一个新阀值 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else {// zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 新阀值等于0就生成一个新阀值 if (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[] newTab = (Node[])new Node[newCap]; table = newTab; if (oldTab != null) { // 把oldTab的值放到newTab中 for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 若该节点没有链表，则通过hash & (newCap - 1)定位赋值 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 若该节点是TreeNode，则做红黑树操作 else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); // 若该节点有链表则把旧节点的链表移到新节点的链表中 else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.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; }

通过上面的代码分析可以知道，首先创建一个通过判断得到Node数组。同时，把旧Node数组的数据放到新Node数组中。分析到这里也知道了，在HashMap执行一次put的时候HashMap就经历一次扩容。
第二部分这一部分通过(n - 1) & hash定位table数组的位置，如果为null，就在该位置上赋值Node。这一部分着重讲一下 (n - 1) & hash。
(n - 1) & hash
1.为什么一定是2的幂次方？
因为扩容的时候是通过左移<<来计算的，就相当于乘以 2 n 2^n 2n，所以其长度总是2的幂次方。而之所以用左移是因为计算更加有效率。
2.为什么(n - 1) & hash
如果长度是2的幂次方，那么这个数肯定是一个偶数，而偶数的二进制数的最后一位是0。如果与hash值相与，那么最后一位总是0，那么数组里面只有偶数位置有值，所以决定了HashMap的数组长度不能是奇数。长度如果是偶数，减1之后变成奇数，奇数的二进制数的最后一位是1，与hash值相与，最终结果是看hash值，可能是一个偶数，也可能是一个奇数。这样可以保证Node数组每个节点都能被赋值。
下面我们看下代码来加深下理解：

int a = 6; // 结果110 System.out.println(Integer.toBinaryString(a)); int b = 5; // 结果101 System.out.println(Integer.toBinaryString(b));

从代码可以看出偶数的二进制最后一位是0，奇数的最后一位是1。从代码可以看出HashMap就是通过自身长度与key的hash值做逻辑与，而得到数组中的地址。这样做的话，如果有两个一样的hash值该怎么处理呢？接下来我们来看第三部分代码。
第三部分紧接上面的分析，如果通过(n - 1) & hash得到的数组值不为null，那么就有三种可能：

可能新值和旧值是同一值
可能put的值是TreeNode，那么需要做红黑树处理
新值的位置和旧值位置一致，或者说发生了hash碰撞

(1)新旧值一致

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;

直接赋值覆盖旧值，注意这里需要判断key是否一致
(2)节点是TreeNode

else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

如果节点是TreeNode，就调用TreeNode的putTreeVal方法。
(3)hash碰撞

else { for (int binCount = 0; ; ++binCount) { ///链表的尾端也没有找到key值相同的节点，则生成一个新的Node, //并且判断链表的节点个数是否大于8，若是，则转换成红黑树。 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //链表长度超过了8就转换成红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } }

如果发生hash碰撞，首先判断当前数组节点的next是否为null，如果为null就在该数组节点下面挂一个。同时，链表的长度大于8就转成红黑树。
第四部分

// 如果e不为空就替换旧的oldValue值 if (e != null) { // existing mapping for key V oldValue = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } // 重要代码 ++modCount; if (++size> threshold) resize(); afterNodeInsertion(evict); return null;

注意到modCount这个变量，这个变量主要是用到Iterator迭代器中，它的作用就是判断集合在迭代的时候是否对数据做增删操作
四.get方法实际上知道了如何put数据，也基本知道该如何get数据了。

public V get(Object key) { Node e; // 通过hash函数计算key的哈希值，再调用getNode方法 return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; // 判断table不为null，table的长度不为0。 // 通过(n - 1) & hash取出数组对于的数据，同时判断是否为null if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 如果hash和key的值都相等，那就取该value值 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，那么通过红黑树算法查找 if (first instanceof TreeNode) return ((TreeNode)first).getTreeNode(hash, key); // 查找链表中的数据，hash和key相等代表查找到该数据 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } // 没有查到就返回null return null; }

总结到目前为止，完成了HashMap代码的分析，从代码分析可以看出来，实际上HashMap是通过数组加单向链表来做数据存储的，HashMap每次put的时候都会扩容一次，并且保证容量是2的幂次方。
【Java学习|HashMap浅析】参考文章：
一文读懂HashMap
图解HashMap原理