Java 集合框架系列（四）：Map 接口及其实现类

Map

用于存储键值对，是一个接口，其常见的实现类有 HashMap、Hashtable、TreeMap 等。在该接口中定义的统一操作有：

添加元素：

 // 用于键值对的绑定，当键不存在是返回null，当键存在是返回旧值。
 V put(K key, V value);

判断

 // 是否包含键
 boolean containsKey(Object key);
 // 是否包含值
 boolean containsValue(Object value);
 // 是否为空
 boolean isEmpty();
 // 判断两个map是否相同
 boolean equals(Object o);

获取元素

 // 根据键获取value值，不存在则返回null
 V get(Object key);
 // 获取所有键
 Set<K> keySet();
 // 获取所有的值
 Collection<V> values();
 // 获取所有键值对
 Set<Map.Entry<K,V>> entrySet();
 // 大小
 int size();

移除元素

// 移除某个键
 V remove(object key);
 // 清空map的内容
 void clear();

Map 接口及其实现类

HashMap

HashMap 是 JDK1.2 版本之后开始增加的，在 1.8 版本之前其底层使用数组+链表的方式来作为哈希表的存储结构，在 1.8 版本及之后改成了数组+链表/红黑树的方式来作为哈希表的存储结构，当链表的长度大于8的时候会将链表转换成一颗红黑树。
在分析 HashMap 的源码之前，先来看看一个键值对放入一个 Map 中应该经过什么步骤：

重要成员属性

// 初始容量，必须为2的幂次方，默认为16
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
 
 // 最大的容量
 static final int MAXIMUM_CAPACITY = 1 << 30;
 
 // 默认的负载因子
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
 // 链表的长度的阈值，大于该长度会转化成红黑树
 static final int TREEIFY_THRESHOLD = 8;
 // 红黑树收缩成链表的阈值，即当树节点为6个时会将树转换成红黑树
 static final int UNTREEIFY_THRESHOLD = 6;
 // 哈希表的桶大于 64 时才会将链表转换成树结构
 static final int MIN_TREEIFY_CAPACITY = 64;
 
 // 用数组结构保存哈希表
 transient Node<K,V>[] table;
 // 键值对集合，可以用于键值对的遍历
 transient Set<Map.Entry<K,V>> entrySet;
 // 键值对的数量
 transient int size;
 // 修改容器的次数
 transient int modCount;
 // 容量阈值
 int threshold;
 // 负载因子
 final float loadFactor;

构造方法

public HashMap() {
     this.loadFactor = DEFAULT_LOAD_FACTOR; // 设置为默认的负载因子
 }
 
 // 设置初始化容量，在阿里的开发手册中要求在创建 HashMap 时要指定初始化容量的大小
 public HashMap(int initialCapacity) {
     this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }
 
 // 设置初始化容量，并指定负载因子
 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);
     // n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
     // numberOfLeadingZeros可以获取前导0的数量。
 }

关键操作

put 添加元素方法，put 方法只是一个入口，实际添加元素的方法为 putVal。

// 不存在映射则会关联值，存在则直接替换值
 public V put(K key, V value) {
     return putVal(hash(key), key, value, false, true);
 }
 // 计算hash值，从这里可以看出 HashMap 的 key 可以为null，其hash值为0 
 // 面试可能会问。
 // 计算方式为获取 hashCode 之后再进行一次散列，可以打乱进一步的打乱值。
 static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
 /** 
     hash – 密钥的散列
     key——钥匙
     value – 要放置的值
     onlyIfAbsent – 如果为真，则不更改现有值
     evict – 如果为 false，则表处于创建模式。
     返回：以前的值，如果没有，则为 null
 */
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
     Node<K,V>[] tab; 
     Node<K,V> p; 
     int n, i;
     if ((tab = table) == null || (n = tab.length) == 0)
         // 如果 table 为空，则进行第一次的 resize 操作，分配空间
         // 因此 HashMap 是延迟到添加元素的时候才分配空间的
         n = (tab = resize()).length;
     if ((p = tab[i = (n - 1) & hash]) == null)
         // 桶中还没有元素，直接创建节点放入
         tab[i] = newNode(hash, key, value, null);
     else {
         // 桶中已经有元素，此时有两种情况，一种是键相同，一种是发生哈希碰撞
         Node<K,V> e; K k;
         if (p.hash == hash &&
             ((k = p.key) == key || (key != null && key.equals(k))))
             // 进一步判断key是否相等，或者是key重写equals方法后相等
             e = p;
         else if (p instanceof 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);
                     if (binCount >= TREEIFY_THRESHOLD - 1) 
                         // 链表长度大于8的时候转化成树结构，但是在 treeifyBin 里面还会判断桶的数量是否大于64，如果没有的话则进行扩容操作
                         treeifyBin(tab, hash);
                     break;
                 }
                 if (e.hash == hash &&
                     ((k = e.key) == key || (key != null && key.equals(k))))
                     break;
                 p = e;
             }
         }
         if (e != null) { // key相等会直接替换值并返回旧值
             V oldValue = e.value;
             if (!onlyIfAbsent || oldValue == null)
                 e.value = value;
             // 给 LinkedHashMap 扩展用的，可以用于链表 LRU 的性质
             afterNodeAccess(e);
             return oldValue;
         }
     }
     ++modCount;
     if (++size > threshold)
         // 扩容操作
         resize();
     afterNodeInsertion(evict);
     return null;
 }
 
 // 初始化容量或加倍表的大小 HashMap的底层数组table并不会在构造方法中创建，而是延迟到添加元素时创建
 final Node<K,V>[] resize() {
     Node<K,V>[] oldTab = table;
     // 第一次添加元素进来 resize 时table为空
     int oldCap = (oldTab == null) ? 0 : oldTab.length;
     int oldThr = threshold;
     int newCap, newThr = 0;
     if (oldCap > 0) {
         if (oldCap >= MAXIMUM_CAPACITY) {
             threshold = Integer.MAX_VALUE;
             return oldTab;
         }
         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
             // 新的阈值×2
             newThr = oldThr << 1; // double threshold
     } else if (oldThr > 0) {
         newCap = oldThr;
     } else {
         // 第一次添加元素，且使用空构造方法没有指定阈值大小时进入这个分支
         newCap = DEFAULT_INITIAL_CAPACITY;  // 初始化容量为16
         // 设置阈值大小
         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
     }
     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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
     table = newTab;
     // 对老结构中所有的元素都进行重新hash
     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)
                     // 如果当前桶只有一个Node节点，则不用改变其在桶的位置
                     newTab[e.hash & (newCap - 1)] = e;
                 else if (e instanceof TreeNode)
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                 else { // e的后续仍有节点，且e不是树节点
                     Node<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) { // 索引为0的位置
                             if (loTail == null)
                                 loHead = e;
                             else
                                 loTail.next = e;
                             loTail = e;
                         } else { // 索引为非0的位置
                             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;
 }

总结put操作的过程：

第一次添加元素时会调用 resize 方法扩容。该方法对所有的元素进行 rehash，对于索引为0的桶的元素不改变其位置，对于其他元素则将整条链挂到当前索引+老容量的新索引（j + oldCap）位置上去。
如果桶中没有元素则直接放入。
如果桶中有元素了，有相同的键值替换值，没有相同的键则发生冲突，采用尾插法的方式进行插入。
在插入节点之后如果链表的长度大于8且桶的数量大于64则会转成一棵树结构。

TreeMap

底层是一个红黑树结构，能够保证数据根据key排序，注意 key 不能为空。
节点的结构如下：

Entry = (key、value、左子树地址、右子树地址、父节点地址、颜色) 
static final class Entry<K,V> implements Map.Entry<K,V> {
     K key;
     V value;
     Entry<K,V> left;
     Entry<K,V> right;
     Entry<K,V> parent;
     // 使用boolean类型来表示红黑，BLACK和RED是一个常量
     boolean color = BLACK;
 
     // 新增的节点默认为黑色
     Entry(K key, V value, Entry<K,V> parent) {
         this.key = key;
         this.value = value;
         this.parent = parent;
     }
 }

TreeMap 的定义及常用字段

public class TreeMap<K,V>
     extends AbstractMap<K,V>
     implements NavigableMap<K,V>, Cloneable, java.io.Serializable
 {
     // 比较器，TreeMap 需要内部比较器或者外部比较器
     private final Comparator<? super K> comparator;
     // 红黑树的树根
     private transient Entry<K,V> root;
     // 红黑树节点数量    
     private transient int size = 0;
     // 修改次数
     private transient int modCount = 0;
     
     // 构造方法，key 需要实现 Comparable 接口来实现内部的比较
     public TreeMap() {
         comparator = null;
     }
     // 传入自定义外部比较器
     public TreeMap(Comparator<? super K> comparator) {
         this.comparator = comparator;
     }
 }

常用操作

 // 添加元素
 public V put(K key, V value) {
     Entry<K,V> t = root;
     if (t == null) {
         // 比较两个元素，有外部比较器优先调用外部比较器，没有时调用内部比较器
         compare(key, key); 
         root = new Entry<>(key, value, null);
         size = 1;
         modCount++;
         return null;
     }
     int cmp;
     Entry<K,V> parent;
     // 将外部比较器赋值给cpr，看构造函数
     Comparator<? super K> cpr = comparator;
     // cpr不等于null，意味着创建对象时调用有参构造器
     if (cpr != null) {
         do {
             parent = t;
             cmp = cpr.compare(key, t.key);  // 比较元素的key值
             // cmp返回的就是int类型的数据
             if (cmp < 0)
                 t = t.left;
             else if (cmp > 0)
                 t = t.right;
             else// cmp=0,即键相等，直接替换value的值，但是key不变，唯一的
                 return t.setValue(value);
         } while (t != null);
     }
     // 创建对象的时候没有指定外部比较器，使用的是内部比较器
     else {
         if (key == null)
             throw new NullPointerException();
         @SuppressWarnings("unchecked")
         Comparable<? super K> k = (Comparable<? super K>) key;
         do {
             parent = t;
             cmp = k.compareTo(t.key);
             if (cmp < 0)
                 t = t.left;
             else if (cmp > 0)
                 t = t.right;
             else
                 return t.setValue(value);
         } while (t != null);
     }
     Entry<K,V> e = new Entry<>(key, value, parent);
     if (cmp < 0)
         parent.left = e;
     else
         parent.right = e; 
     // 维护红黑树的性质
     fixAfterInsertion(e);
     size++;
     modCount++;
     return null;
 }
 
 // 获取key对应的值
 public V get(Object key) {
     Entry<K,V> p = getEntry(key);
     return (p==null ? null : p.value);
 }
 
 final Entry<K,V> getEntry(Object key) {
     // 由外部比较器则使用外部比较器比较获取值
     if (comparator != null)
         return getEntryUsingComparator(key);
     if (key == null)
         throw new NullPointerException();
     @SuppressWarnings("unchecked")
         Comparable<? super K> k = (Comparable<? super K>) key;
     Entry<K,V> p = root;
     while (p != null) {
         int cmp = k.compareTo(p.key);
         if (cmp < 0)
             p = p.left;
         else if (cmp > 0)
             p = p.right;
         else
             return p;
     }
     return null;
 }

总结：

TreeMap 底层就是一颗红黑树结构。
节点的 key 需要实现内部比较器或者有自定义的外部比较器，有自定义的外部比较器的时候先使用外部比较器。
节点的 key 不管在 put 还是在 get 都不能为空。而 HashMap 是允许为空的，至于为什么会有这两个的区别，传闻说是 TreeMap 的作者不喜欢 null。

LinkedHashMap

LinkedHashMap 继承 HashMap，可以在 HashMap 的基础上实现顺序的访问，其底层使用了双向链表+HashMap 来实现。由于新版本的 HashMap 会将链表转化成树结构，因此这里称为“Linked”有点混淆，但是官方仍然采用了这个命名方式。
LinkedHashMap 使用头尾节点和回调函数来维护双向链表的结构。回调函数在操作：access、insertion、removal 后触发。
更有用的一点是 LinkedHashMap 底层使用了LRU算法来维护节点的顺序。

类的定义和常用字段

public class LinkedHashMap<K,V>
     extends HashMap<K,V>
     implements Map<K,V>
 {
     /**
      * 头节点、也是最久没有使用的节点
      */
     transient LinkedHashMap.Entry<K,V> head;
 
     /**
      * 尾结点、也是最近使用的节点
      */
     transient LinkedHashMap.Entry<K,V> tail;
     
     /**
      * true：按照访问顺序遍历、LRU算法
      * false：按照插入顺序遍历
      */
     final boolean accessOrder;
     
     // 默认的 LinedHashMap 是按照插入顺序遍历的
     public LinkedHashMap(int initialCapacity, float loadFactor) {
         super(initialCapacity, loadFactor);
         accessOrder = false;
     }
     public LinkedHashMap(int initialCapacity) {
         super(initialCapacity);
         accessOrder = false;
     }
     public LinkedHashMap() {
         super();
         accessOrder = false;
     }
     
     // 要使用 LRU 算法则需将 accessOrder 设置为 true
     public LinkedHashMap(int initialCapacity,
                          float loadFactor,
                          boolean accessOrder) {
         super(initialCapacity, loadFactor);
         this.accessOrder = accessOrder;
     }

常用操作

public V get(Object key) {
     Node<K,V> e;
     if ((e = getNode(hash(key), key)) == null)
         return null;
     if (accessOrder)
         // 如果是按照访问顺序要调用回调函数
         afterNodeAccess(e);
     return e.value;
 }
 // 将当前最近一次访问的节点移动到链表尾部
 void afterNodeAccess(Node<K,V> e) { // move node to last
     LinkedHashMap.Entry<K,V> last;
     if (accessOrder && (last = tail) != e) {
         // 当前访问的节点不再最后一个位置
         LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, 
         // b：当前访问节点的上一个节点，a：当前访问节点的下一个节点
                                 b = p.before, a = p.after;
         p.after = null;
         if (b == null)
             // p就是头结点
             head = a;
         else
             // p节点要移除到最后一个位置的
             b.after = a;
         
         if (a != null)
             // p不是最后一个元素
             a.before = b;
         else
             last = b;
         
         if (last == null)
             // 第一次访问，
             head = p;
         else {
             p.before = last;
             last.after = p;
         }
         tail = p;
         ++modCount;
     }
 }
}

使用 LinkedHashMap 实现 LRU 缓存

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    public LRUCache(int capacity) {
        // 传递true会使用LRU算法
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    // 重写这个方法，实现超过容量时移除
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // 节点数大于容量时需要移除
        return size() > capacity; 
    }
}

总结

HashMap、TreeMap、LinkedHashMap 底层都是有红黑树结构的存在。
TreeMap 可以实现 key 有序，LinkedHashMap 可以实现访问插入有序和 LRU 缓存。

原文链接：https://blog.csdn.net/weixin_44184990/article/details/125924808