关于存储数组有序无序

旧城等待， 2022-04-22 15:06 169阅读 0赞

# 底层实现  #

1:集合
        Collection(单列集合)
            List(有序,可重复)
                ArrayList
                    底层数据结构是数组,查询快,增删慢
                    线程不安全,效率高
                Vector
                    底层数据结构是数组,查询快,增删慢
                    线程安全,效率低
                LinkedList
                    底层数据结构是链表,查询慢,增删快
                    线程不安全,效率高
            Set(红黑树，无序,唯一)
                HashSet
                    底层数据结构是哈希表。
                    哈希表依赖两个方法：hashCode()和equals()
                    执行顺序：
                        首先判断hashCode()值是否相同
                            是：继续执行equals(),看其返回值
                                是true:说明元素重复，不添加
                                是false:就直接添加到集合
                            否：就直接添加到集合
                    最终：
                        自动生成hashCode()和equals()即可
                        
                    LinkedHashSet
                        底层数据结构由链表和哈希表组成。
                        由链表保证元素有序。
                        由哈希表保证元素唯一。
                TreeSet
                    底层数据结构是红黑树。(是一种自平衡的二叉树)
                    如何保证元素唯一性呢?
                        根据比较的返回值是否是0来决定
                    如何保证元素的排序呢?
                        两种方式
                            自然排序(元素具备比较性)
                                让元素所属的类实现Comparable接口
                            比较器排序(集合具备比较性)
                                让集合接收一个Comparator的实现类对象
        Map(双列集合)
            A:Map集合的数据结构仅仅针对键有效，与值无关。
            B:存储的是键值对形式的元素，键唯一，值可重复。
            
            HashMap
                底层数据结构是哈希表。线程不安全，效率高
                    哈希表依赖两个方法：hashCode()和equals()
                    执行顺序：
                        首先判断hashCode()值是否相同
                            是：继续执行equals(),看其返回值
                                是true:说明元素重复，不添加
                                是false:就直接添加到集合
                            否：就直接添加到集合
                    最终：
                        自动生成hashCode()和equals()即可
                LinkedHashMap
                    底层数据结构由链表和哈希表组成。
                        由链表保证元素有序。
                        由哈希表保证元素唯一。
            Hashtable
                底层数据结构是哈希表。线程安全，效率低
                    哈希表依赖两个方法：hashCode()和equals()
                    执行顺序：
                        首先判断hashCode()值是否相同
                            是：继续执行equals(),看其返回值
                                是true:说明元素重复，不添加
                                是false:就直接添加到集合
                            否：就直接添加到集合
                    最终：
                        自动生成hashCode()和equals()即可
            TreeMap
                底层数据结构是红黑树。(是一种自平衡的二叉树)
                    如何保证元素唯一性呢?
                        根据比较的返回值是否是0来决定
                    如何保证元素的排序呢?
                        两种方式
                            自然排序(元素具备比较性)
                                让元素所属的类实现Comparable接口
                            比较器排序(集合具备比较性)
                                让集合接收一个Comparator的实现类对象
        
    2.关于集合选取原则
        
        是否是键值对象形式:
            是：Map
                键是否需要排序:
                    是：TreeMap
                    否：HashMap
                不知道，就使用HashMap。
                
            否：Collection
                元素是否唯一:
                    是：Set
                        元素是否需要排序:
                            是：TreeSet
                            否：HashSet
                        不知道，就使用HashSet
                        
                    否：List
                        要安全吗:
                            是：Vector
                            否：ArrayList或者LinkedList
                                增删多：LinkedList
                                查询多：ArrayList
                            不知道，就使用ArrayList
                不知道，就使用ArrayList
                
    3:集合的常见方法及遍历方式
        Collection:
            add()
            remove()
            contains()
            iterator()
            size()
            
            遍历：
                增强for
                迭代器
                
            |--List
                get()
                
                遍历：
                    普通for
            |--Set
        
        Map:
            put()
            remove()
            containskey(),containsValue()
            keySet()
            get()
            value()
            entrySet()
            size()
            
            遍历：
                根据键找值
                根据键值对对象分别找键和值

# Collection \[I\] #

*Collection 层次结构* 中的根接口。Collection 表示一组对象，这些对象也称为 collection 的*元素*。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何*直接* 实现：它提供更具体的子接口（如 Set 和 List）实现。此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。

*包 (bag)* 或*多集合 (multiset)*（可能包含重复元素的无序 collection）应该直接实现此接口。

所有通用的 Collection 实现类（通常通过它的一个子接口间接实现 Collection）应该提供两个“标准”构造方法：一个是 void（无参数）构造方法，用于创建空 collection；另一个是带有 Collection 类型单参数的构造方法，用于创建一个具有与其参数相同元素新的 collection。实际上，后者允许用户复制任何 collection，以生成所需实现类型的一个等效 collection。尽管无法强制执行此约定（因为接口不能包含构造方法），但是 Java 平台库中所有通用的 Collection 实现都遵从它。

![932056-20171222023523037-1079865226.png][]

# \+--List \[I\] #

public class Listextends Componentimplements ItemSelectable, Accessible

`List` 组件为用户提供了一个可滚动的文本项列表。可设置此 list，使其允许用户进行单项或多项选择。

### ![932056-20171222015622850-1045072755.png][] ###

--------------------

![932056-20171222015654568-1762731202.png][]

--------------------

![932056-20171222015722537-1158896869.png][]

--------------------

![932056-20171222015744975-899131870.png][]

--------------------

# \+--ArrayList \[C\] #

List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以*分摊的固定时间* 运行，也就是说，添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行（大体上讲）。与用于 LinkedList 实现的常数因子相比，此实现的常数因子较低。

每个 ArrayList 实例都有一个*容量*。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。

在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

![932056-20171222015935615-419622935.png][]

--------------------

![932056-20171222020003178-917241078.png][]

--------------------

# \+--LinkedList \[C\] #

List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。

所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。

![932056-20171222020227178-1338233827.png][]

--------------------

![932056-20171222020316100-1083286992.png][]

--------------------

![932056-20171222020345350-941779344.png][]

--------------------

# \+--Vector \[C\] #

`Vector` 类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。但是，`Vector` 的大小可以根据需要增大或缩小，以适应创建 `Vector` 后进行添加或移除项的操作。

每个向量会试图通过维护 `capacity` 和 `capacityIncrement` 来优化存储管理。`capacity` 始终至少应与向量的大小相等；这个值通常比后者大些，因为随着将组件添加到向量中，其存储将按 `capacityIncrement` 的大小增加存储块。应用程序可以在插入大量组件前增加向量的容量；这样就减少了增加的重分配的量。

![932056-20171222020519990-787154377.png][]

--------------------

![932056-20171222020550943-830085427.png][]

--------------------

![932056-20171222020624412-339868430.png][]

--------------------

# \+--Stack \[C\] #

`Stack` 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。

![932056-20171222020736225-1781859277.png][]

--------------------

# \+--Set \[I\] #

一个不包含重复元素的 collection。更确切地讲，set 不包含满足 `e1.equals(e2)` 的元素对 `e1` 和 `e2`，并且最多包含一个 null 元素。正如其名称所暗示的，此接口模仿了数学上的 *set* 抽象。

在所有构造方法以及 add、equals 和 hashCode 方法的协定上，Set 接口还加入了其他规定，这些规定超出了从 Collection 接口所继承的内容。出于方便考虑，它还包括了其他继承方法的声明（这些声明的规范已经专门针对 Set 接口进行了修改，但是没有包含任何其他的规定）。

对这些构造方法的其他规定是（不要奇怪），所有构造方法必须创建一个不包含重复元素的 set（正如上面所定义的）。

注：如果将可变对象用作 set 元素，那么必须极其小心。如果对象是 set 中某个元素，以一种影响 equals 比较的方式改变对象的值，那么 set 的行为就是不确定的。此项禁止的一个特殊情况是不允许某个 set 包含其自身作为元素

![932056-20171222021030943-1811489239.png][]

--------------------

# \+--HashSet \[C\] #

此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

此类为基本操作提供了稳定性能，这些基本操作包括 add、remove、contains 和 size，假定哈希函数将这些元素正确地分布在桶中。对此 set 进行迭代所需的时间与 HashSet 实例的大小（元素的数量）和底层 HashMap 实例（桶的数量）的“容量”的和成比例。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

**注意，此实现不是同步的。**如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它*必须* 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 `Collections.synchronizedSet` 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：

![932056-20171222021221334-276669081.png][]

--------------------

# \+--LinkedHashSet \[C\] #

具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。此实现与 HashSet 的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，即按照将元素插入到 set 中的顺序（*插入顺序*）进行迭代。注意，插入顺序*不* 受在 set 中*重新插入的* 元素的影响。（如果在 s.contains(e) 返回 true 后立即调用 s.add(e)，则元素 e 会被重新插入到 set s 中。）

此实现可以让客户免遭未指定的、由 `HashSet` 提供的通常杂乱无章的排序工作，而又不致引起与 `TreeSet` 关联的成本增加。使用它可以生成一个与原来顺序相同的 set 副本，并且与原 set 的实现无关：

void foo(Set s) {
             Set copy = new LinkedHashSet(s);
             ...
         }

如果模块通过输入得到一个 set，复制这个 set，然后返回由此副本决定了顺序的结果，这种情况下这项技术特别有用。（客户通常期望内容返回的顺序与它们出现的顺序相同。）

此类提供所有可选的 Set 操作，并且允许 null 元素。与 HashSet 一样，它可以为基本操作（add、contains 和 remove）提供稳定的性能，假定哈希函数将元素正确地分布到存储段中。由于增加了维护链接列表的开支，其性能很可能会比 HashSet 稍逊一筹，不过，这一点例外：LinkedHashSet 迭代所需时间与 set 的*大小* 成正比，而与容量无关。HashSet 迭代很可能支出较大，因为它所需迭代时间与其*容量* 成正比。

链接的哈希 set 有两个影响其性能的参数：*初始容量* 和*加载因子*。它们与 HashSet 中的定义极其相同。注意，为初始容量选择非常高的值对此类的影响比对 HashSet 要小，因为此类的迭代时间不受容量的影响。

**注意，此实现不是同步的。**如果多个线程同时访问链接的哈希 set，而其中至少一个线程修改了该 set，则它*必须* 保持外部同步。这一般通过对自然封装该 set 的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 `Collections.synchronizedSet` 方法来“包装”该 set。最好在创建时完成这一操作，以防止意外的非同步访问：

![932056-20171222021424928-1496481131.png][]

--------------------

# \+--SortedSet \[I\] #

进一步提供关于元素的*总体排序* 的 `Set`。这些元素使用其自然顺序进行排序，或者根据通常在创建有序 set 时提供的 `Comparator` 进行排序。该 set 的迭代器将按元素升序遍历 set。提供了一些附加的操作来利用这种排序。（此接口是 `SortedMap` 的 set 对应接口）。

插入有序 set 的所有元素都必须实现 Comparable 接口（或者被指定的比较器所接受）。另外，所有这些元素都必须是*可互相比较的*：对于有序 set 中的任意两个元素 e1 和 e2，执行 e1.compareTo(e2)（或 comparator.compare(e1, e2)）都不得抛出 ClassCastException。试图违反此限制将导致违反规则的方法或者构造方法调用抛出 ClassCastException。

注意，如果有序 set 要正确实现 Set 接口，则有序 set 所维持的顺序（无论是否提供了明确的比较器）都必须*与 equals 一致*。（有关*与 equals 一致* 的精确定义，请参阅 Comparable 接口或 Comparator 接口。）这是因为 Set 接口是按照 equals 操作定义的，但有序 set 使用它的 compareTo（或 compare）方法对所有元素进行比较，因此从有序 set 的角度来看，此方法认为相等的两个元素就是相等的。即使顺序与 equals 不一致，有序 set 的行为仍然*是* 定义良好的，只不过没有遵守 Set 接口的常规协定。

所有通用有序 set 实现类都应该提供 4 个“标准”构造方法：1) void（无参数）构造方法，它创建一个空的有序 set，按照元素的自然顺序进行排序。2) 带有一个 Comparator 类型参数的构造方法，它创建一个空的有序 set，根据指定的比较器进行排序。3) 带有一个 Collection 类型参数的构造方法，它创建一个新的有序 set，其元素与参数相同，按照元素的自然顺序进行排序。4) 带有一个 SortedSet 类型参数的构造方法，它创建一个新的有序 set，其元素和排序方法与输入的有序 set 相同。无法保证强制实施此建议，因为接口不能包含构造方法。

注：一些方法返回具有受限范围的子集。这些范围区间是*半开的*，也就是说，它们包括低端点，但不包括高端点（如果适用）。如果需要一个*闭区间*（同时包含两个端点），且元素类型允许计算给定值的后继值，则只需要请求从 lowEndpoint 到 successor(highEndpoint) 的子区间。例如，假设 s 是一个字符串有序 set。下面的语句将得到一个包含 s 中从 low 到 high（包括）所有字符串的视图：

SortedSet<String> sub = s.subSet(low, high+"\0");

可使用类似的技术生成*开区间*（两个端点都不包括）。下面的语句得到包含 s 中从 low 到 high（不包括）所有字符串的视图：

SortedSet<String> sub = s.subSet(low+"\0", high);

![932056-20171222021541787-526977656.png][]

--------------------

# \+--TreeSet \[C\] #

基于 `TreeMap` 的 `NavigableSet` 实现。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 `Comparator` 进行排序，具体取决于使用的构造方法。

此实现为基本操作（`add`、`remove` 和 `contains`）提供受保证的 log(n) 时间开销。

注意，如果要正确实现 `Set` 接口，则 set 维护的顺序（无论是否提供了显式比较器）必须*与 equals 一致*。（关于*与 equals 一致* 的精确定义，请参阅 `Comparable` 或 `Comparator`。）这是因为 `Set` 接口是按照 `equals` 操作定义的，但 `TreeSet` 实例使用它的 `compareTo`（或 `compare`）方法对所有元素进行比较，因此从 set 的观点来看，此方法认为相等的两个元素就是相等的。即使 set 的顺序与 equals 不一致，其行为也*是* 定义良好的；它只是违背了 `Set` 接口的常规协定。

**注意，此实现不是同步的。**如果多个线程同时访问一个 TreeSet，而其中至少一个线程修改了该 set，那么它*必须* 外部同步。这一般是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 `Collections.synchronizedSortedSet` 方法来“包装”该 set。此操作最好在创建时进行，以防止对 set 的意外非同步访问：

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

此类的 `iterator` 方法返回的迭代器是*快速失败* 的：在创建迭代器之后，如果从结构上对 set 进行修改，除非通过迭代器自身的 `remove` 方法，否则在其他任何时间以任何方式进行修改都将导致迭代器抛出 `ConcurrentModificationException`。因此，对于并发的修改，迭代器很快就完全失败，而不会冒着在将来不确定的时间发生不确定行为的风险。

注意，迭代器的快速失败行为无法得到保证，一般来说，存在不同步的并发修改时，不可能作出任何肯定的保证。快速失败迭代器尽最大努力抛出 `ConcurrentModificationException`。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测 bug。

![932056-20171222021732350-1710329043.png][]

--------------------

![932056-20171222021806350-1683800382.png][]

--------------------

# Map \[I\] #

public interface Map<K,V>

将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。

此接口取代 Dictionary 类，后者完全是一个抽象类，而不是一个接口。

Map 接口提供三种*collection 视图*，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。映射*顺序* 定义为迭代器在映射的 collection 视图上返回其元素的顺序。某些映射实现可明确保证其顺序，如 TreeMap 类；另一些映射实现则不保证顺序，如 HashMap 类。

注：将可变对象用作映射键时必须格外小心。当对象是映射中某个键时，如果以影响 equals 比较的方式更改了对象的值，则映射的行为将是不确定的。此项禁止的一种特殊情况是不允许某个映射将自身作为一个键包含。虽然允许某个映射将自身作为值包含，但请格外小心：在这样的映射上 equals 和 hashCode 方法的定义将不再是明确的。

![932056-20171222022045475-230771329.png][]

--------------------

# \+--SortedMap \[I\] #

进一步提供关于键的*总体排序* 的 `Map`。该映射是根据其键的自然顺序进行排序的，或者根据通常在创建有序映射时提供的 `Comparator` 进行排序。对有序映射的 collection 视图（由 entrySet、keySet 和 values 方法返回）进行迭代时，此顺序就会反映出来。要采用此排序方式，还需要提供一些其他操作（此接口是 `SortedSet` 的对应映射）。

插入有序映射的所有键都必须实现 Comparable 接口（或者被指定的比较器接受）。另外，所有这些键都必须是*可互相比较的*：对有序映射中的任意两个键 k1 和 k2 执行 k1.compareTo(k2)（或 comparator.compare(k1, k2)）都不得抛出 ClassCastException。试图违反此限制将导致违反规则的方法或者构造方法调用抛出 ClassCastException。

注意，如果有序映射要正确实现 Map 接口，则有序映射所维持的顺序（无论是否提供了明确的比较器）都必须*与 equals 一致*。（有关*与 equals 一致* 的精确定义，请参阅 Comparable 接口或 Comparator 接口）。这是因为 Map 接口是按照 equals 操作定义的，但有序映射使用它的 compareTo（或 compare）方法对所有键进行比较，因此从有序映射的角度来看，此方法认为相等的两个键就是相等的。即使顺序与 equals 不一致，树映射的行为仍然*是* 定义良好的，只不过没有遵守 Map 接口的常规协定。

![932056-20171222022208193-1490765992.png][]

--------------------

# \+--TreeMap \[C\] #

public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, Serializable

基于红黑树（Red-Black tree）的 `NavigableMap` 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 `Comparator` 进行排序，具体取决于使用的构造方法。

此实现为 containsKey、get、put 和 remove 操作提供受保证的 log(n) 时间开销。这些算法是 Cormen、Leiserson 和 Rivest 的 *Introduction to Algorithms* 中的算法的改编。

注意，如果要正确实现 Map 接口，则有序映射所保持的顺序（无论是否明确提供了比较器）都必须*与 equals 一致*。（关于*与 equals 一致* 的精确定义，请参阅 Comparable 或 Comparator）。这是因为 Map 接口是按照 equals 操作定义的，但有序映射使用它的 compareTo（或 compare）方法对所有键进行比较，因此从有序映射的观点来看，此方法认为相等的两个键就是相等的。即使排序与 equals 不一致，有序映射的行为仍然*是* 定义良好的，只不过没有遵守 Map 接口的常规协定。

![932056-20171222022335678-771082246.png][]

--------------------

![932056-20171222022408943-778514742.png][]

--------------------

![932056-20171222022429006-834525830.png][]

--------------------

# \+--Hashtable \[C\] #

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, Serializable

此类实现一个哈希表，该哈希表将键映射到相应的值。任何非 `null` 对象都可以用作键或值。

为了成功地在哈希表中存储和获取对象，用作键的对象必须实现 `hashCode` 方法和 `equals` 方法。

`Hashtable` 的实例有两个参数影响其性能：*初始容量* 和*加载因子*。*容量* 是哈希表中*桶* 的数量，*初始容量* 就是哈希表创建时的容量。注意，哈希表的状态为 *open*：在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。*加载因子* 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。

通常，默认加载因子(.75)在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间（在大多数 Hashtable 操作中，包括 get 和 put 操作，都反映了这一点）。

初始容量主要控制空间消耗与执行 `rehash` 操作所需要的时间损耗之间的平衡。如果初始容量大于 Hashtable 所包含的最大条目数除以加载因子，则*永远* 不会发生 `rehash` 操作。但是，将初始容量设置太高可能会浪费空间。

如果很多条目要存储在一个 `Hashtable` 中，那么与根据需要执行自动 rehashing 操作来增大表的容量的做法相比，使用足够大的初始容量创建哈希表或许可以更有效地插入条目。

下面这个示例创建了一个数字的哈希表。它将数字的名称用作键：

Hashtable<String, Integer> numbers
         = new Hashtable<String, Integer>();
       numbers.put("one", 1);
       numbers.put("two", 2);
       numbers.put("three", 3);

要获取一个数字，可以使用以下代码：

Integer n = numbers.get("two");
         if (n != null) {
             System.out.println("two = " + n);
         }
       }

![932056-20171222022535990-1488179636.png][]

--------------------

![932056-20171222022554818-1719941676.png][]

--------------------

# \+--HashMap \[C\] #

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

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

HashMap 的实例有两个参数影响其性能：*初始容量* 和*加载因子*。*容量* 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。*加载因子* 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 *rehash* 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

![932056-20171222022659459-423489161.png][]

--------------------

# \+--LinkedHashMap \[C\] #

public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>

Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（*插入顺序*）。注意，如果在映射中*重新插入* 键，则插入顺序不受影响。（如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true，则调用时会将键 k 重新插入到映射 m 中。）

此实现可以让客户避免未指定的、由 `HashMap`（及 `Hashtable`）所提供的通常为杂乱无章的排序工作，同时无需增加与 `TreeMap` 相关的成本。使用它可以生成一个与原来顺序相同的映射副本，而与原映射的实现无关：

void foo(Map m) {
             Map copy = new LinkedHashMap(m);
             ...
         }

如果模块通过输入得到一个映射，复制这个映射，然后返回由此副本确定其顺序的结果，这种情况下这项技术特别有用。（客户通常期望返回的内容与其出现的顺序相同。）

提供特殊的`构造方法`来创建链接哈希映射，该哈希映射的迭代顺序就是最后访问其条目的顺序，从近期访问最少到近期访问最多的顺序（*访问顺序*）。这种映射很适合构建 LRU 缓存。调用 put 或 get 方法将会访问相应的条目（假定调用完成后它还存在）。putAll 方法以指定映射的条目集迭代器提供的键-值映射关系的顺序，为指定映射的每个映射关系生成一个条目访问。*任何其他方法均不生成条目访问。*特别是，collection 视图上的操作*不* 影响底层映射的迭代顺序。

![932056-20171222022759006-522929340.png][]

--------------------

# \+--WeakHashMap \[C\] #

public class WeakHashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>

以*弱键* 实现的基于哈希表的 Map。在 WeakHashMap 中，当某个键不再正常使用时，将自动移除其条目。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。丢弃某个键时，其条目从映射中有效地移除，因此，该类的行为与其他的 Map 实现有所不同。

null 值和 null 键都被支持。该类具有与 HashMap 类相似的性能特征,并具有相同的效能参数*初始容量* 和*加载因子*。

像大多数 collection 类一样，该类是不同步的。可以使用 `Collections.synchronizedMap` 方法来构造同步的 WeakHashMap。

该类主要与这样的键对象一起使用，其 equals 方法使用 == 运算符来测试对象标识。一旦这种键被丢弃，就永远无法再创建了，所以，过段时间后在 WeakHashMap 中查找此键是不可能的，不必对其项已移除而感到惊讶。该类十分适合与 equals 方法不是基于对象标识的键对象一起使用，比如，String 实例。然而，对于这种可重新创建的键对象，键若丢弃，就自动移除 WeakHashMap 条目，这种表现令人疑惑。

WeakHashMap 类的行为部分取决于垃圾回收器的动作，所以，几个常见的（虽然不是必需的）Map 常量不支持此类。因为垃圾回收器在任何时候都可能丢弃键，WeakHashMap 就像是一个被悄悄移除条目的未知线程。特别地，即使对 WeakHashMap 实例进行同步，并且没有调用任何赋值方法，在一段时间后 size 方法也可能返回较小的值，对于 isEmpty 方法，返回 false，然后返回 true，对于给定的键，containsKey 方法返回 true 然后返回 false，对于给定的键，get 方法返回一个值，但接着返回 null，对于以前出现在映射中的键，put 方法返回 null，而 remove 方法返回 false，对于键 set、值 collection 和条目 set 进行的检查，生成的元素数量越来越少。

WeakHashMap 中的每个键对象间接地存储为一个弱引用的指示对象。因此，不管是在映射内还是在映射之外，只有在垃圾回收器清除某个键的弱引用之后，该键才会自动移除。

[932056-20171222023523037-1079865226.png]: /images/20220327/9b59c59b5e9241a884a2e874b2f11dc2.png
[932056-20171222015622850-1045072755.png]: /images/20220327/5de75834703242b99021832da8dd14d2.png
[932056-20171222015654568-1762731202.png]: /images/20220327/d56493a13df24094917a18f0c58dbf93.png
[932056-20171222015722537-1158896869.png]: /images/20220327/9c6478fd41df4a0bbf17e6d0344576cf.png
[932056-20171222015744975-899131870.png]: /images/20220327/50008c8dcbca44b4accbcd26b4596b72.png
[932056-20171222015935615-419622935.png]: /images/20220327/d2c710e5598f4930abdc38213de5ee33.png
[932056-20171222020003178-917241078.png]: /images/20220327/bba3d99637bd470a8a51b817cff56385.png
[932056-20171222020227178-1338233827.png]: /images/20220327/401704b8812845f5bf96e595012acfd1.png
[932056-20171222020316100-1083286992.png]: /images/20220327/bcb80dc8f52f47248224eeff16b2ce92.png
[932056-20171222020345350-941779344.png]: /images/20220327/4993b152c21f4d028115c71e7d662c5b.png
[932056-20171222020519990-787154377.png]: /images/20220327/aff9cd1446c44014ae6290405fc5bf61.png
[932056-20171222020550943-830085427.png]: /images/20220327/229c3d1b37754cb8bade3e73287ff560.png
[932056-20171222020624412-339868430.png]: /images/20220327/5e95a4fb35834154bce25f831990ff64.png
[932056-20171222020736225-1781859277.png]: /images/20220327/92dcd7335d8545ad855eace1dfe8b6e2.png
[932056-20171222021030943-1811489239.png]: /images/20220327/95b36cbf9c614f2eba64ac874b88cb64.png
[932056-20171222021221334-276669081.png]: /images/20220327/a3195868985548f7a0c3f08a98113c9c.png
[932056-20171222021424928-1496481131.png]: /images/20220327/74f95ab236d748b0adc408b5f04c801e.png
[932056-20171222021541787-526977656.png]: /images/20220327/748207c7b87342d98ac2014dad2dae4f.png
[932056-20171222021732350-1710329043.png]: /images/20220327/5b35ca06fc3c4982acb5627f36010e7d.png
[932056-20171222021806350-1683800382.png]: /images/20220327/04a687bca0be48558c4e34def95958a5.png
[932056-20171222022045475-230771329.png]: /images/20220327/2277c1c3d57745afb413c979683f9f26.png
[932056-20171222022208193-1490765992.png]: /images/20220327/db14fb1f70d54b308216a1ec0429a19c.png
[932056-20171222022335678-771082246.png]: /images/20220327/ec1af34c196b437a96cc2aa401c0d260.png
[932056-20171222022408943-778514742.png]: /images/20220327/532048f4b0c24147adbf6357effd9121.png
[932056-20171222022429006-834525830.png]: /images/20220327/6b1b91d96ee4460e965f7e79a2122a54.png
[932056-20171222022535990-1488179636.png]: /images/20220327/c176a7cd0d414cdc9709a5365287fd3b.png
[932056-20171222022554818-1719941676.png]: /images/20220327/b6633f952e624d2a839f09faa6e3ef5f.png
[932056-20171222022659459-423489161.png]: /images/20220327/0262d48b9e4a44daa3e9bb4f5e7630c6.png
[932056-20171222022759006-522929340.png]: /images/20220327/64cc2d2f6ff94211a03207ee4c2314eb.png