目录

本文一是总结前面两种集合，补充一些遗漏，再者对HashMap进行简单介绍。

因为前两篇ArrayList和LinkedList都是针对单独的集合类分析的，只见树木未见森林，今天分析HashMap，可以结合起来看一下java中的集合框架。下图只是一小部分，而且为了方便理解去除了抽象类。

集合体系

Java中的集合（有时也称为容器）是为了存储对象，而且多数时候存储的不止一个对象。

可以简单的将Java集合分为两类：

  • 一类是Collection，存储的是独立的元素，也就是单个对象。细分之下，常见的有List，Set，Queue。其中List保证按照插入的顺序存储元素。Set不能有重复元素。Queue按照队列的规则来存取元素，一般情况下是“先进先出”。

  • 一类是Map，存储的是“键值对”，通过键来查找值。比如现实中通过姓名查找电话号码，通过身份证号查找个人详细信息等。

    理论上说我们完全可以只用Collection体系，比如将键值对封装成对象存入Collection的实现类，之所以提出Map，最主要的原因是效率。

HashMap用来存储键值对，也就是一次存储两个元素。在jdk1.8中，其实现是基于数组+链表+红黑树，简单说就是普通情况直接用数组，发生哈希冲突时在冲突位置改为链表，当链表超过一定长度时，改为红黑树。

可以简单理解为：在数组中存放链表或者红黑树。

  1. 完全没有哈希冲突时，数组每个元素是一个容量为1的链表。如索引0和1上的元素。
  2. 发生较小哈希冲突时，数组每个元素是一个包含多个元素的链表。如索引2上的元素。
  3. 当冲突数量超过8时，数组每个元素是一棵红黑树。如索引6上的元素。

下图为示意图，相关结构没有严格遵循规范。

HashMap的存储结构

  1. public class HashMap<K,V> extends AbstractMap<K,V>
  2.     implements Map<K,V>, Cloneable, Serializable

如下图

HashMap继承体系

实现Cloneable和Serializable接口，拥有克隆和序列化的能力。

HashMap继承抽象类AbstractMap的同时又实现Map接口的原因同样见上一篇LinkedList。

  1. //序列化版本号
  2. private static final long serialVersionUID = 362498820763181265L;
  4. //默认初始化容量为16
  5. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
  7. //最大容量，2的30次方
  8. static final int MAXIMUM_CAPACITY = 1 << 30;
  10. //默认负载因子，值为0.75
  11. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  14. //以下三个常量应结合看
  15. //链表转为树的阈值
  16. static final int TREEIFY_THRESHOLD = 8;
  18. //树转为链表的阈值，小于6时树转链表
  19. static final int UNTREEIFY_THRESHOLD = 6;
  21. //链表转树时的集合最小容量。只有总容量大于64，且发生冲突的链表大于8才转换为树。
  22. static final int MIN_TREEIFY_CAPACITY = 64;

上述变量的关键在于链表转树和树转链表的时机，综合看：

  • 当数组的容量小于64是，此时不管冲突数量多少，都不树化，而是选择扩容。
  • 当数组的容量大于等于64时，
    • 冲突数量大于8，则进行树化。
    • 当红黑树中元素数量小于6时，将树转为链表。
  1. //存储节点的数组，始终为2的幂
  2. transient Node<K,V>[] table;
  4. //批量存入时使用，详见对应构造函数
  5. transient Set<Map.Entry<K,V>> entrySet;
  7. //实际存放键值对的个数
  8. transient int size;
  10. //修改map的次数，便于快速失败
  11. transient int modCount;
  13. //扩容时的临界值，本质是capacity * load factor
  14. int threshold;
  16. //负载因子
  17. final float loadFactor;

数组中存储的节点类型，可以看出，除了K和Value外，还包含了指向下一个节点的引用，正如一开始说的，节点实际是一个单向链表。

  1. static class Node<K,V> implements Map.Entry<K,V> {
  2.     
  3.     final int hash;
  4.     final K key;
  5.     V value;
  6.     Node<K,V> next;
  7.     
  8.    //...省略常见方法
  9. }

常见的无参构造和一个参数的构造很简单，直接传值，此处省略。看一下两个参数的构造方法。

  1. public HashMap(int initialCapacity, float loadFactor) {
  2.     if (initialCapacity < 0)
  3.         throw new IllegalArgumentException("Illegal initial capacity: "+initialCapacity);
  4.     
  5.     //指定容量不能超过最大值
  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.     
  12.     this.loadFactor = loadFactor;
  13.     //将给定容量转换为不小于其自身的2的幂
  14.     this.threshold = tableSizeFor(initialCapacity);
  15. }

上述方法中有一个非常巧妙的方法tableSizeFor，它将给定的数值转换为不小于自身的最小的2的整数幂。

  1. static final int tableSizeFor(int cap) {
  2.     int n = cap - 1;
  3.     n |= n >>> 1;
  4.     n |= n >>> 2;
  5.     n |= n >>> 4;
  6.     n |= n >>> 8;
  7.     n |= n >>> 16;
  8.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  9. }

比如cap=10，转换为16；cap=32，则结果还是32。用了位运算，保证效率。

有一个问题，为啥非要把容量转换为2的幂？之前讲到的ArrayList为啥就不需要呢？其实关键在于hash，更准确的说是转换为2的幂，一定程度上减小了哈希冲突。

关于这些运算，画个草图很好理解，关键在于能够想到这个方法很牛啊。解释的话配图太多，这里篇幅限制，将内容放在另一篇文章。

在上面构造方法中，我们没有看到初始化数组也就是Node<K,V>[] table的情况，这一步骤放在了添加元素put时进行。

  1. public V put(K key, V value) {
  2.     return putVal(hash(key), key, value, false, true);
  3. }

可以看出put调用的是putVal方法。

在此之前回顾一下HashMap的构成，数组+链表+红黑树。数组对应位置为空，存入数组，不为空，存入链表，链表超载，转换为红黑树。

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
  2.     
  3.     Node<K,V>[] tab; 
  4.     Node<K,V> p; 
  5.     int n, i;
  6.     //数组为空，则扩容
  7.     if ((tab = table) == null || (n = tab.length) == 0)
  8.         n = (tab = resize()).length;
  9.     //根据key计算hash值得出数组中的位置i，位置i上为空，直接添加。
  10.     if ((p = tab[i = (n - 1) & hash]) == null)
  11.         tab[i] = newNode(hash, key, value, null);
  12.     //数组对应位置不为空
  13.     else {
  14.         Node<K,V> e; 
  15.         K k;
  16.         //对应节点key上的key存在，直接覆盖value
  17.         if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
  18.             e = p;
  19.         //为红黑树时
  20.         else if (p instanceof TreeNode)
  21.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  22.         //为链表时
  23.         else {
  24.             for (int binCount = 0; ; ++binCount) {
  25.                 if ((e = p.next) == null) {
  26.                     p.next = newNode(hash, key, value, null);
  27.                     //链表转换为红黑树
  28.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  29.                         treeifyBin(tab, hash);
  30.                     break;
  31.                 }
  32.                 if (e.hash == hash &&
  33.                     ((k = e.key) == key || (key != null && key.equals(k))))
  34.                     break;
  35.                 p = e;
  36.             }
  37.         }
  38.         if (e != null) { 
  39.             V oldValue = e.value;
  40.             if (!onlyIfAbsent || oldValue == null)
  41.                 e.value = value;
  42.             afterNodeAccess(e);
  43.             return oldValue;
  44.         }
  45.     }
  46.     
  47.     ++modCount;
  48.     //下次添加前需不需要扩容，若容量已满则提前扩容
  49.     if (++size > threshold)
  50.         resize();
  51.     afterNodeInsertion(evict);
  52.     return null;
  53. }

resize()方法比较复杂，最好是配合IDE工具，debug一下，比较容易弄清楚扩容的方式和时机，如果干讲的话反而容易混淆。

根据键获取对应的值，内部调用getNode方法

  1. public V get(Object key) {
  2.     Node<K,V> e;
  3.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  4. }
  1. final Node<K,V> getNode(int hash, Object key) {
  2.     
  3.     Node<K,V>[] tab; 
  4.     Node<K,V> first, 
  5.     e; int n; 
  6.     K k;
  7.     
  8.     //数组不为空
  9.     if ((tab = table) != null && (n = tab.length) > 0 &&
  10.         (first = tab[(n - 1) & hash]) != null) {
  11.         //第一个节点满足则直接返回对应值
  12.         if (first.hash == hash && 
  13.             ((k = first.key) == key || (key != null && key.equals(k))))
  14.             return first;
  15.         if ((e = first.next) != null) {
  16.             //红黑树中查找
  17.             if (first instanceof TreeNode)
  18.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  19.             do {
  20.                 //链表中查找
  21.                 if (e.hash == hash &&
  22.                     ((k = e.key) == key || (key != null && key.equals(k))))
  23.                     return e;
  24.             } while ((e = e.next) != null);
  25.         }
  26.     }
  27.     return null;
  28. }

HashMap的内容太多，每个内容相关的知识点也很多，篇幅和个人能力限制，很难讲清所有内容，比如最基础的获取hash值的方法，其实也很讲究的。有机会再针对具体的细节慢慢详细写吧。

版权声明：本文为xiyixiaodao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/xiyixiaodao/p/14483586.html