深入了解 Map Set

引言

近几天面试，期间面试官有多次提到源码层面的实现，故将自己以前看的东西拿出来加上自己现有的理解作以归类总结。
#Map
Map 提供了一个更通用的元素存储方法。Map 集合类用户存储元素对(称作"键"和"值")，其中每个键映射到一个值。从概念分析，感觉也可以将数组看作具有数值键的 Map。
Java 当中有很多定义的 Map 类，首先先分析下 Map 接口本身，即其所定义的四种类型的方法，每个 Map 接口的实现都包含这些方法。

覆盖的方法

方法名	含义
equals(Object o)	比较指定对象与此 Map 的等价性
hashCode()	返回此 Map 的哈希码
##Map 构建
Map 定义的几个用于插入和删除元素的变换方法
方法名	含义
:--:	:--:
clear()	从 Map 中删除所有映射
remove(Object key)	从 Map 中删除键和关联的值
put(Object key,Object value)	将指定值与指定键相关联
claer()	从 Map 中删除所有映射
putAll(Map t)	将指定 Map 中的所有映射复制到此 Map
##内部哈希:哈希映射技术
几乎所有通用 Map 都使用哈希映射。这是一种将元素映射到数组的非常简单的机制。
哈希映射结构由一个存储元素的内部数组组成。由于内部采用数组存储，因此必然存在一个用于确定任意键访问数组的索引机制。实际上，该机制需要提供一个小于数组大小的整数索引值。该机制称为哈希函数。在 Java 基于哈希的 Map 中，哈希函数将对象转换为一个适合内部数组的整数。您不必为寻找一个易于使用的哈希函数而大伤脑筋： 每个对象都包含一个返回整数值的 hashCode() 方法。要将该值映射到数组，只需将其转换为一个正值，然后在将该值除以数组大小后取余数即可。
上图为哈希工作原理

HashMap

特点:非线程安全，并允许 null 值和 null 键。不保证映射顺序。
HashMap 实际上是一个"链表散列“的数据结构，即数组和链表的结合体。
其解决 hash 冲突也主要依靠链地址法。
现在来分析下 JDK 中 HashMap 源码

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)//Capacity的意思为容量，此处指初始数组长度的意思
            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);

        // 表明容量一定为2^n
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];//看到这里已经可以发现其创建了一个Entry数组，其大小为capacity entry为一个static class 其中包含了key和value,Entry 就是数组中的元素，每个 Entry 其实就是一个 key-value 对，它持有一个指向下一个元素的引用，这就构成了链表。
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
}

综上，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 hash 算法来决定其在数组中的存储位置，在根据 equals 方法决定其在该数组位置上的链表中的存储位置；当需要取出一个 Entry 时，也会根据 hash 算法找到其在数组中的存储位置，再根据 equals 方法从该位置上的链表中取出该 Entry。(这当中比较的都是 key)

TreeMap

与 SortedSet 接口类似，SortedMap 也是一个结构，待排序的 Map，其一个比较常用的实现类是 TreeMap。
reeMap 的 put(K key, V value)方法在每添加一个元素时，都会自动排序。
对于 TreeMap 而言，由于它底层采用一棵“红黑树”来保存集合中的 Entry，这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低：当 TreeMap 添加元素时，需要通过循环找到新增 Entry 的插入位置，因此比较耗性能；当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态。

排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表：所有节点只有左节点（如果插入节点集本身是大到小排列）；或所有节点只有右节点（如果插入节点集本身是小到大排列）。在这种情况下，排序二叉树就变成了普通链表，其检索效率就会很差。

为了改变排序二叉树存在的不足，Rudolf Bayer 与 1972 年发明了另一种改进后的排序二叉树：红黑树，他将这种排序二叉树称为“对称二叉 B 树”，而红黑树这个名字则由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。

红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组。典型地，JDK 提供的集合类 TreeMap 本身就是一个红黑树的实现。

红黑树在原有的排序二叉树增加了如下几个要求：

• 性质 1：每个节点要么是红色，要么是黑色。
• 性质 2：根节点永远是黑色的。
• 性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。
• 性质 4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
• 性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点

根据性质 5：红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度（black-height）”。

性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑色高度为 3 的红黑树：从根节点到叶节点的最短路径长度是 2，该路径上全是黑色节点（黑节点 - 黑节点 - 黑节点）。最长路径也只可能为 4，在每个黑色节点之间插入一个红色节点（黑节点 - 红节点 - 黑节点 - 红节点 - 黑节点），性质 4 保证绝不可能插入更多的红色节点。由此可见，红黑树中最长路径就是一条红黑交替的路径。

由此我们可以得出结论：对于给定的黑色高度为 N 的红黑树，从根到叶子节点的最短路径长度为 N-1，最长路径长度为 2 * (N-1)。
#Set
Set 集合不能包含重复的元素的集合。
Set 接口只包含继承自 Collection 的方法，并增加了重复的元素被禁止约束性

对于 HashSet 而言，它是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，我们应该为保存到 HashSet 中的对象覆盖 hashCode() 和 equals()。
HashSet 保证唯一性：
由于 HashMap 的 put() 方法添加 key-value 对时，当新放入 HashMap 的 Entry 中 key 与集合中原有 Entry 的 key 相同（hashCode()返回值相等，通过 equals 比较也返回 true），新添加的 Entry 的 value 会将覆盖原来 Entry 的 value（HashSet 中的 value 都是 PRESENT），但 key 不会有任何改变，因此如果向 HashSet 中添加一个已经存在的元素时，新添加的集合元素将不会被放入 HashMap 中，原来的元素也不会有任何改变，这也就满足了 Set 中元素不重复的特性。

该方法如果添加的是在 HashSet 中不存在的，则返回 true；如果添加的元素已经存在，返回 false。其原因在于我们之前提到的关于 HashMap 的 put 方法。该方法在添加 key 不重复的键值对的时候，会返回 null。

LinkedHashSet

LinkedHashSet 跟 HashSet 类似，不过 LInkedHashSet 会维护一个链表来加入元素的次序，因为性能比 hashSet 略差，不过在遍历集合元素的时候具有较好的性能，根据加入集合的次序来遍历

TreeSet

TreeSet 是依靠 TreeMap 来实现的。
TreeSet 是一个有序集合，TreeSet 中的元素将按照升序排列，缺省是按照自然排序进行排列，意味着 TreeSet 中的元素要实现 Comparable 接口。或者有一个自定义的比较器。
我们可以在构造 TreeSet 对象时，传递实现 Comparator 接口的比较器对象。

EnumSet

EnumSet 是一个与枚举类型一起使用的专用 Set 实现。枚举 set 中所有元素都必须来自单个枚举类型（即必须是同类型，且该类型是 Enum 的子类）。
枚举类型在创建 set 时显式或隐式地指定。枚举 set 在内部表示为位向量。