HashMap类

Hash节点 - Node类

上面是HashMap的一个静态内部类，这个Node类是HashMap存储元素的一个基本单位。当调用HaspMap的put方法是，其实就是创建了一个Node对象。如下所示：

因此可以看到，这个内部类中字段的含义：

hash：表示key的哈希值
key：键值对中的key
value：键值对中的value
next：下一个Hash节点的指针

上图可以看到，链表或者红黑树的第一个 Hash 节点是存放在数组的某个索引对应的内存中的，而这个索引也被称为“桶”。至于这个索引怎么确定的，其实是通过这个公式：index=f(hash(key))，也就是用 key 的哈希值通过函数f()进行运算得到的，而这个函数f就被称为哈希函数。一个哈希函数的选择是否正确，对HashMap的存储效率其中决定性的作用，HashMap采用的哈希算法参考下面文章：https://www.jianshu.com/p/2fee1d246cad

Hash冲突

所谓hash冲突就是 key 的哈希值通过哈希函数的运算后，得到的数组的索引对应的内存中已经存在一个Node对象，并且新put进去的Node对象和已经存在的Node对象也不是同一个对象（即内存地址不相同），这时候就发生了哈希冲突。HaspMap在JDK1.8之前使用的是链表来解决哈希冲突，而JDK1.8及以后采用链表+红黑树来解决哈希冲突。

JDK1.8前

JDK1.8之前，就是采用的外部拉链法解决的hash冲突，如下图所示：

也就是说，当调用map.get(key)的时候，先经过哈希运算，找到对应数组的索引，然后遍历这个索引对应的链表，直到找到这个Node对象为止，时间复杂度为O(N)。当链表长度较小的时候，这种方法倒也没什么大问题；但是，如果这个链表长度很大的话，那么这个遍历链表的方式还是比较慢的，因此JDK1.8以后才采用黑红树来优化这个查询效率。

JDK1.8及以后

JDK1.8开始，当链表的长度大于 8 时，就会将链表转化为红黑树来优化查询效率，如图：

扩容机制

当new一个HashMap对象的时候，如果不知道初始容量，那其默认容量大小就是16。

但是如果当HashMap存储的元素快要超过初始容量时，就需要进行扩容了，而这个值就被称为临界值。对应字段“int threshold”。在HashMap中，还有一个装载因子的概念，对应字段“final float loadFactor”，填充因子和临界值满足如下关系：

装载因子表示 HashMap 满的程度，默认值为 0.75f，也就是说默认情况下，当 HashMap 中元素个数达到了容量的 3/4 的时候就会进行自动扩容。HashMap的扩容方法在resize方法中实现：

并且，HashMap的扩容机制是new一个新的大容量的HashMap对象，然后重新调用Hash算法。
那么为什么HashMap默认的负载因子是0.75，而不是其它值？其主要原因有以下几个：

如果负载因子的值太大了，那么就会有很高的哈希冲突的概率，会大大降低查询速度
如果负载因子的值太小了，那么扩容太频繁，就会导致原对象的空间大量浪费
为了提高扩容效率，HashMap的容量必须是2的n次幂，所以，如果 loadFactor 是 3/4 的话，那么和 capacity 的乘积结果（即临界值）就可以是一个整数

至于怎么提高扩容效率，参考文章：为什么JDK1.8 HashMap的容量一定要是2的n次幂？

扩容需要重新开辟内存空间，并且还需重新哈希，开销很大，HashMap的容量理论上可以达到无限大（外部拉链+红黑树），为什么要设置一个容量和扩容机制。这其实和哈希冲突有关，下面这两种情况会导致哈希冲突发生的概率很大：

数组的容量太小，容量小，碰撞的概率就高了，狼多肉少，就会发生争抢。
hash 算法不够好，算法不合理，就可能都分到同一个或几个桶中，分配不均，也会发生争抢。

因此，JDK开发团队为了减少哈希冲突发生的概率，一方面采用比较好的哈希算法，另一方面在键值对比较多的时候通过增大桶容量（即数组长度）。

TreeMap类

TreeMap底层不存在一个数组，TreeMap它就是一棵红黑树，由于红黑树也是一棵二叉搜索树，因此TreeMap的元素是排好序的，并且不能存放key为null的键值对。HashMap的底层是Array，所以HashMap在添加，查找，删除等方法上面速度会非常快。而TreeMap的底层是一个Tree结构，所以速度会比较慢。另外HashMap因为要保存一个Array，所以会造成空间的浪费，而TreeMap只保存要保持的节点，所以占用的空间比较小。HashMap如果出现hash冲突的话，效率会变差，不过在java 8进行TreeNode转换之后，效率有很大的提升。TreeMap在添加和删除节点的时候会进行重排序，会对性能有所影响。

注意：参考文章：https://www.cnblogs.com/flydean/p/hashmap-vs-treemap.html

红黑树

定义

对于二叉搜索树，容易退化成一条链表，这时，查找的时间复杂度从O(log2N)退化为O(N)。当然，为了防止算法的时间复杂度退化，于是就出现了平衡二叉树。但是平衡二叉树的左右子树高度差不能超过1，每次进行插入/删除操作时几乎都需要通过旋转操作保持平衡，在频繁进行插入/删除的场景中，频繁的旋转操作使得AVL树的性能大打折扣，因此才出现了黑红树。
Map接口 - 图9
红黑树通过牺牲严格的平衡度来减少插入/删除时的旋转次数，因此在整体性能上优于平衡二叉树。下面就是一棵红黑树：

下面是红黑树的红黑规则：

节点不是黑色，就是红色（非黑即红），用一个标志位标记是红还是黑即可
根节点是黑色
叶子节点是黑色，并且都是null
一个节点为红色，则其两个子节点必须是黑色的（根到叶子的所有路径，不可能存在两个连续的红色节点）
每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度，但是红色节点没有要求）

其中，第4、5个规则就是限制了红黑树的大致平衡。除了这些红黑规则，还需要满足二叉搜索树的规则，即右子节点必须大于父节点，左子节点必须小于父节点。

class RedBlackTreeNode {
    public int val;
    public RedBlackTreeNode left;
    public RedBlackTreeNode right;
    // 记录节点颜色的color属性，暂定true表示红色
    public boolean color;
    // 为了方便迭代插入，所需的parent属性
    public RedBlackTreeNode parent;
    // 一些构造函数，根据实际需求构建
    public RedBlackTreeNode() {
    }
}

插入和删除

参考文章：https://www.cnblogs.com/LiaHon/p/11203229.html

主要成员变量

/**
 * 我们前面提到TreeMap是可以自动排序的，默认情况下comparator为null，这个时候按照key的自然顺序进行排
 * 序，然而并不是所有情况下都可以直接使用key的自然顺序，有时候我们想让Map的自动排序按照我们自己的规则，
 * 这个时候你就需要传递Comparator的实现类
 */
private final Comparator<? super K> comparator;
/**
 * TreeMap的存储结构既然是红黑树，那么必然会有唯一的根节点。
 */
private transient Entry<K,V> root;
/**
 * Map中key-val对的数量，也即是红黑树中节点Entry的数量
 */
private transient int size = 0;
/**
 * 红黑树结构的调整次数
 */
private transient int modCount = 0;

其中，Entry是一个静态内部类，结构如下：

static final class Entry<K,V> implements Map.Entry<K,V> {
    //key,val是存储的原始数据
    K key;
    V value;
    //定义了节点的左孩子
    Entry<K,V> left;
    //定义了节点的右孩子
    Entry<K,V> right;
    //通过该节点可以反过来往上找到自己的父亲
    Entry<K,V> parent;
    //默认情况下为黑色节点，可调整（红黑标志）
    boolean color = BLACK;
    /**
     * 构造器
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    /**
     * 获取节点的key值
     */
    public K getKey() {return key;}
    /**
     * 获取节点的value值
     */
    public V getValue() {return value;}
    /**
     * 用新值替换当前值，并返回当前值
     */
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    }
    public int hashCode() {
        int keyHash = (key==null ? 0 : key.hashCode());
        int valueHash = (value==null ? 0 : value.hashCode());
        return keyHash ^ valueHash;
    }
    public String toString() {
        return key + "=" + value;
    }
}

通过Entry的结构，不难看出TreeMap的结构：
Map接口 - 图12
HashMap的增加、删除操作就是对应红黑树的各种操作了。

LinkedHashMap类

底层结构

LinkedHashMap的实现采用的是哈希表+双向链表的数据结构，如下图所示：

形象地，HashMap与LinkedHashMap的Entry结构示意图如下图所示：
Map接口 - 图17
因此，总的来看，就是在HashMap的基础上加多了before和after指针，如图所示：
Map接口 - 图18
其中属性head和tail分别是链表的尾指针和头指针。本质上，LinkedHashMap = HashMap + 双向链表，也就是说，HashMap和双向链表合二为一即是LinkedHashMap。LinkedHashMap 在不对HashMap做任何改变的基础上，给HashMap的任意两个节点间加了两条连线(before指针和after指针)，使这些节点形成一个双向链表。在LinkedHashMapMap中，所有put进来的Entry都保存在HashMap中，但由于它又额外定义了一个以head为头结点的空的双向链表，因此对于每次put进来Entry还会将其插入到双向链表的尾部。

LinkedHashMap与LRU算法

LRU算法就是一个著名的缓存更新策略，而这个算法就需要借助LinkedHashMap这个数据结构来实现，而JDK也实现了LRU算法。使用LinkedHashMap实现LRU的必要前提是将accessOrder标志位设为true以便开启按访问顺序排序的模式。参考文章：

算法题就像搭乐高：手把手带你拆解 LRU 算法
彻头彻尾理解 LinkedHashMap

HashTable类
HashTable底层的数据结构和HashMap是一样的，而二者的区别如下：
HashMap允许将 null 作为一个 entry 的 key 或者 value，而 Hashtable 不允许。
HashTable 的方法是 Synchronize 的，而 HashMap 不是，在多个线程访问 Hashtable 时，不需要自己为它的方法实现同步，而 HashMap 就必须为之提供外同步。

注意：虽然HashTable是线程安全的，但是它的方法都是直接用 Synchronize 锁住的，所以其实它的并发效率是很低下的，因此一般不会使用HashTable，一般使用并发工具类ConcurrentHashMap。

Map接口