HashMap的构造方法
/** *使用默认的容量及装载因子构造一个空的HashMap */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } /** * 根据给定的初始容量和装载因子创建一个空的HashMap * 初始容量小于0或装载因子小于等于0将报异常 */ 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; //这个方法就是把容量控制在2的倍数 this.threshold = tableSizeFor(initialCapacity); } /** *根据指定容量创建一个空的HashMap */ public HashMap(int initialCapacity) { //调用上面的构造方法，容量为指定的容量，装载因子是默认值 this(initialCapacity, DEFAULT_LOAD_FACTOR); } //通过传入的map创建一个HashMap，容量为默认容量（16）和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者，装载因子为默认值 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } 复制代码
HashMap提供了四种构造方法：
（1）使用默认的容量及装载因子构造一个空的HashMap；
（2）根据给定的初始容量和装载因子创建一个空的HashMap；
（3）根据指定容量创建一个空的HashMap；
（4）通过传入的map创建一个HashMap。
第三种构造方法会调用第二种构造方法，而第四种构造方法将会调用putMapEntries方法将元素添加到HashMap中去。
putMapEntries方法是一个final方法，不可以被修改，该方法实现了将另一个Map的所有元素加入表中，参数evict初始化时为false，其他情况为true，我们来看看这个方法吧
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { //根据m的元素数量和当前表的加载因子，计算出阈值 float ft = ((float)s / loadFactor) + 1.0F; //修正阈值的边界 不能超过MAXIMUM_CAPACITY int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY); //如果新的阈值大于当前阈值 if (t > threshold) //返回一个>=新的阈值的 满足2的n次方的阈值 threshold = tableSizeFor(t); } //如果当前元素表不是空的，但是 m的元素数量大于阈值，说明一定要扩容。 else if (s > threshold) resize(); //遍历 m 依次将元素加入当前表中。 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } 复制代码
从中可以看出，它这个涉及了2个操作，一个是计算新的阈值，另一个是扩容方法
如果新的阈值大于当前阈值，需要返回一个>=新的阈值的 满足2的n次方的阈值，这涉及到了tableSizeFor：
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; } 复制代码
如果当前元素表不是空的，但是 m的元素数量大于阈值，说明一定要扩容。这涉及到了扩容方法resize。最复杂的方法之一
final Node<K,V>[] resize() { //oldTab 为当前表的哈希桶 Node<K,V>[] oldTab = table; //当前哈希桶的容量 length int oldCap = (oldTab == null) ? 0 : oldTab.length; //当前的阈值 int oldThr = threshold; //初始化新的容量和阈值为0 int newCap, newThr = 0; //如果当前容量大于0 if (oldCap > 0) { //如果当前容量已经到达上限 if (oldCap >= MAXIMUM_CAPACITY) { //则设置阈值是2的31次方-1 threshold = Integer.MAX_VALUE; //同时返回当前的哈希桶，不再扩容 return oldTab; }//否则新的容量为旧的容量的两倍。 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //如果旧的容量大于等于默认初始容量16 //那么新的阈值也等于旧的阈值的两倍 newThr = oldThr << 1; // double threshold } //如果当前表是空的，但是有阈值。代表是初始化时指定了容量、阈值的情况 else if (oldThr > 0) newCap = oldThr;//那么新表的容量就等于旧的阈值 else { //如果当前表是空的，而且也没有阈值。代表是初始化时没有任何容量/阈值参数的情况 newCap = DEFAULT_INITIAL_CAPACITY;//此时新表的容量为默认的容量 16 //新的阈值为默认容量16 * 默认加载因子0.75f = 12 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { //如果新的阈值是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; //如果以前的哈希桶中有元素 //下面开始将当前哈希桶中的所有节点转移到新的哈希桶中 if (oldTab != null) { //遍历老的哈希桶 for (int j = 0; j < oldCap; ++j) { //取出当前的节点 e Node<K,V> e; //如果当前桶中有元素,则将链表赋值给e if ((e = oldTab[j]) != null) { //将原哈希桶置空以便GC oldTab[j] = null; //如果当前链表中就一个元素，（没有发生哈希碰撞） if (e.next == null) //直接将这个元素放置在新的哈希桶里。 //注意这里取下标 是用 哈希值 与 桶的长度-1 。 由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高 newTab[e.hash & (newCap - 1)] = e; //如果发生过哈希碰撞 ,而且是节点数超过8个，转化成了红黑树 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。 else { //因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位，或者扩容后的下标，即high位。high位=low位+原哈希桶容量 //低位链表的头结点、尾节点 Node<K,V> loHead = null, loTail = null; //高位链表的头节点、尾节点 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next;//临时节点 存放e的下一个节点 do { next = e.next; //利用位运算代替常规运算：利用哈希值与旧的容量，可以得到哈希值去模后，是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，否则存放在高位 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); //将低位链表存放在原index处 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //将高位链表存放在新index处 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } 复制代码
resize的操作主要涉及以下几步操作：
- 如果到达最大容量，那么返回当前的桶，并不再进行扩容操作，否则的话扩容为原来的两倍，返回扩容后的桶；
- 根据扩容后的桶，修改其他的成员变量的属性值；
- 根据新的容量创建新的扩建后的桶，并更新桶的引用；
- 如果原来的桶里面有元素就需要进行元素的转移；
- 在进行元素转移的时候需要考虑到元素碰撞和转红黑树操作；
- 在扩容的过程中，按次从原来的桶中取出链表头节点，并对该链表上的所有元素重新计算hash值进行分配；
- 在发生碰撞的时候，将新加入的元素添加到末尾；
- 在元素复制的时候需要同时对低位和高位进行操作。
这段是借鉴人家的，确实很复杂，各种if else ，一点点去跟，也很累，但是大家至少也要知道它是怎么扩容的，几个重要的步骤要能说出来，面试的时候会问。
HashMap的成员方法
put方法
//向哈希表中添加元素 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 复制代码
- 向用户开放的put方法调用的是putVal方法：
- putVal方法需要判断是否出现哈希冲突问题：
- 其中如果哈希值相等，key也相等，则是覆盖value操作；如果不是覆盖操作，则插入一个普通链表节点；
- 遍历到尾部，追加新节点到尾部；
- 在元素添加的过程中需要随时检查是否需要进行转换成红黑树的操作；
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab存放当前的哈希桶，p用作临时链表节点 Node<K,V>[] tab; Node<K,V> p; int n, i; //如果当前哈希表是空的，代表是初始化 if ((tab = table) == null || (n = tab.length) == 0) //那么直接去扩容哈希表，并且将扩容后的哈希桶长度赋值给n n = (tab = resize()).length; //如果当前index的节点是空的，表示没有发生哈希碰撞。直接构建一个新节点Node，挂载在index处即可。 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else {//否则 发生了哈希冲突。 Node<K,V> e; K k; //如果哈希值相等，key也相等，则是覆盖value操作 if (p.hash == hash &&((k = p.key) == key || (key != nul l && key.equals(k)))) e = p;//将当前节点引用赋值给e else if (p instance of TreeNode) e = ((TreeNode<K,V>)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); //如果追加节点后，链表数量>=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; } } //如果e不是null，说明有需要覆盖的节点， if (e != null) { // existing mapping for key //则覆盖节点值，并返回原oldValue V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //这是一个空实现的函数，用作LinkedHashMap重写使用。 afterNodeAccess(e); return oldValue; } } //如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null。 ++modCount; //更新size，并判断是否需要扩容。 if (++size > threshold) resize(); //这是一个空实现的函数，用作LinkedHashMap重写使用。 afterNodeInsertion(evict); return null; } 复制代码
总结一下put过程
- 第一步当然是先计算key的hash值(有过处理的 (h = key.hashCode()) ^ (h >>> 16))
- 第二步调用putval方法，然后判断是否容器中全部为空，如果是的话，就把容器的容量扩容。
- 第三步，把最大容量和hash值求&值（i = (n - 1) & hash），判断这个数组下标是否有数据，如果没有就把它放进去。还要判断key的equals方法，看是否需要覆盖。
- 第四步，如果有，说明发生了碰撞，那么继续遍历判断链表的长度是否大于8，如果大于8，就继续把当前链表变成红黑树结构。
- 第五步，如果没有到8，那么就直接把数据存在链表的尾部
- 第六步，最后将容器的容量+1。
key.hashCode（）是Key自带的hashCode()方法，返回一个int类型的散列值。我们大家知道，32位带符号的int表值范围从-2147483648到2147483648。这样只要hash函数松散的话，一般是很难发生碰撞的，因为HashMap的初始容量只有16。但是这样的散列值我们是不能直接拿来用的。用之前需要对数组的长度取模运算。得到余数才是索引值。
get方法
public V get(Object key) { Node<K,V> e; //传入扰动后的哈希值 和 key 找到目标节点Node return (e = getNode(hash(key), key)) == null ? null : e.value; } 复制代码
HashMap向用户分开放的get方法是调用的getNode方法来实现的
//传入扰动后的哈希值 和 key 找到目标节点Node final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //查找过程，找到返回节点，否则返回null if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } 复制代码
简单讲讲查询过程，还是比较简单的
- 第一步，看下整个容器是否为空。
- 第二步，如果不为空，再比较hash值的同时需要比较key的值是否相同e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))
- 然后返回
contains
HashMap没有提供判断元素是否存在的方法，只提供了判断Key是否存在及Value是否存在的方法，分别是containsKey(Object key)、containsValue(Object value)。 containsKey(Object key)方法很简单，只是判断getNode (key)的结果是否为null，是则返回false，否返回true。
public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } public boolean containsValue(Object value) { Node<K,V>[] tab; V v; //遍历哈希桶上的每一个链表 if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) { //如果找到value一致的返回true if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; } 复制代码
判断一个value是否存在比判断key是否存在还要简单，就是遍历所有元素判断是否有相等的值。这里分为两种情况处理，value为null何不为null的情况，但内容差不多，只是判断相等的方式不同。这个判断是否存在必须遍历所有元素，是一个双重循环的过程，因此是比较耗时的操作。
remove方法
HashMap中“删除”相关的操作，有remove(Object key)和clear()两个方法。 其中向用户开放的remove方法调用的是removeNode方法，，removeNode (key)的返回结果应该是被移除的元素，如果不存在这个元素则返回为null。remove方法根据removeEntryKey返回的结果e是否为null返回null或e.value。
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { // p 是待删除节点的前置节点 Node<K,V>[] tab; Node<K,V> p; int n, index; //如果哈希表不为空，则根据hash值算出的index下 有节点的话。 if ((tab = table) != null && (n = tab.length) > 0&&(p = tab[index = (n - 1) & hash]) != null) { //node是待删除节点 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;//将待删除节点引用赋给node else if ((e = p.next) != null) {//否则循环遍历 找到待删除节点，赋值给node 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); } } //如果有待删除节点node， 且 matchValue为false，或者值也相等 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)//如果node == p，说明是链表头是待删除节点 tab[index] = node.next; else//否则待删除节点在表中间 p.next = node.next; ++modCount;//修改modCount --size;//修改size afterNodeRemoval(node);//LinkedHashMap回调函数 return node; } } return null; } 复制代码
clear()方法删除HashMap中所有的元素，这里就不用一个个删除节点了，而是直接将table数组内容都置空，这样所有的链表都已经无法访问，Java的垃圾回收机制会去处理这些链表。table数组置空后修改size为0。
public void clear() { Node<K,V>[] tab; modCount++; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i) tab[i] = null; } } 复制代码
总结
HashMap是我写的最长的一篇文章，但是还有很多没有写完，比如它的迭代器（Map是否有序，这个下篇得讲），它的红黑树，实在写不动了，我太难了。也是我菜，红黑树，还没好好学一下，什么左旋，右旋头晕。哈哈 以后有机会会好好补这个坑的。
问大家几个问题
- HashMap 的容量为啥是2的幂次方
- HashMap 的扩容伐值为什么是0.75
- HashMap 它的链表的插入是头插入还是尾插
给大家讲个故事 再Jdk1.7的时候 tomcat 的url上的请求参数 是用HashMap存的 因为它的查询是n(o),但是黑客可以找一些url的参数HashCode相同，几十万个，这样就导致查询非常慢，搞几下就可以把一个网站搞死，后面tomcat 还去找了jdk的人，但是让人家说这不是bug,最后tomcat就自己做了限制 哈哈。
大家如果能对着源码跟着过一遍也好，至少看过源码不是，我们知道HashMap 是线程不安全的，那线程安全的Map是啥，我们知道HashMap是无序的，有序的Map又是啥。各位一起加油吧，路慢慢慢其修远。
版本说明
- 这里的源码是JDK8版本，不同版本可能会有所差异，但是基本原理都是一样的。
因为博主也是一个开发萌新 我也是一边学一边写 我有个目标就是一周 二到三篇 希望能坚持个一年吧 希望各位大佬多提意见，让我多学习，一起进步。
