一、List

1、ArrayList

ArrayList 底层就是⼀个 Object[] 数组

ArrayList 底层数组默认初始化容量为 10

1、jdk1.8 中 ArrayList 底层先创建⼀个⻓度为 0 的数组

2、当第⼀次添加元素（调⽤ add() ⽅法）时，会初始化为⼀个⻓度为 10 的数组

当 ArrayList 中的容量使⽤完之后，则需要对容量进⾏扩容：

1、ArrayList 容量使⽤完后，会“⾃动”创建容量更⼤的数组，并将原数组中所有元素拷⻉过去，这会导致效率降低

2、优化：可以使⽤构造⽅法 ArrayList (int capacity) 或 ensureCapacity(int capacity) 提供⼀个初始化容量，避免刚开始就⼀直扩容，造成效率较低

ArrayList 构造⽅法：

1. ArrayList()：创建⼀个初始化容量为 10 的空列表

2. ArrayList(int initialCapacity)：创建⼀个指定初始化容量为 initialCapacity 的空列表

3. ArrayList(Collection<? extends E> c)：创建⼀个包含指定集合中所有元素的列表

ArrayList 特点：

优点：

        1. 向 ArrayList 末尾添加元素（add() ⽅法）时，效率较⾼

        2. 查询效率⾼

缺点：

        1. 扩容会造成效率较低（可以通过指定初始化容ᰁ，在⼀定程度上对其进⾏改善）

        2. 另外数组⽆法存储⼤数据量（因为很难找到⼀块很⼤的连续的内存空间）

        3. 向 ArrayList 中间添加元素（add(int index)），需要移动元素，效率较低

                1. 但是，向 ArrayList 中国位置增/删元素的情况较少时不影响；

                2. 如果增/删操作较多，可考虑改⽤链表 

2、Linklist

LinkedList 特点

数据结构： LinkedList 底层是⼀个双向链表

优点： 增/删效率⾼

缺点： 查询效率较低

LinkedList 也有下标，但是内存不⼀定是连续的（类似C++᯿载[]符号，将循位置访问模拟为循秩访问）

LinkedList 可以调⽤ get(int index) ⽅法，返回链表中第 index 个元素

但是，每次查找都要从头结点开始遍历

LinkedList 部分源码解读

add()⽅法

 ListIterator 接⼝

1、LinkedList.add ⽅法只能将数据添加到链表的末尾

2、如果要将对象添加到链表的中间位置

则需要使⽤ ListIterator 接⼝的 add ⽅法

        1. ListIterator 是 Iterator 的⼀个⼦接⼝ 

3、Iterator 中 remove ⽅法

        1. 调⽤ next 之后，remove ⽅法删除的是迭代器左侧的元素（类似键盘的 backspace）

        2. 调⽤ previous 之后，remove 删除的是迭代器右侧的元素

4、ListIterator 中 add ⽅法

        1. 调⽤ next 之后，在迭代器左侧添加⼀个元素

        2. 调⽤ previous 之后，add 是在迭代器右侧添加元素 

3、Vector

Vector 底层是数组

初始化容量为 10

扩容： 原容量使⽤完后，会进⾏扩容。新容量扩⼤为原始容量的 2 倍

Vector 是线程安全的（⾥⾯⽅法都带有 synchronized 关键字），效率较低，现在使⽤较少

如何将 ArrayList 变成线程安全的？

调⽤ Collections ⼯具类中的 static List synchronizedList(List list) ⽅法 

二、Set

泛型：

1、jdk 1.5 引⼊，之前都是使⽤ Object[]

2、使⽤ Object[] 的缺点（2个）

        1. 获取⼀个值时必须进⾏强制类型转换

        2. 调⽤⼀个⽅法前必须使⽤ instanceof 判断对象类型

泛型的好处：

1、减少了强制类型转换的次数 获取数据值更⽅便

2、类型安全

调⽤⽅法时更安全

3、泛型只在编译时期起作⽤

运⾏阶段 JVM 看不⻅泛型类型（JVM 只能看⻅对应的原始类型，因为进⾏了类型擦除）

4、带泛型的类型

在使⽤时没有指定泛型类型时，默认使⽤ Object 类型 

5、lambda 表达式 

1、HashSet 

特点：HashSet ⽆序（没有下标），不可重复

2、TreeSet

TreeSet ⽆序（没下标），不可重复，但是可以排序

HashSet 为 HashMap 的 key 部分；TreeSet 为 TreeMap 的 key 部分。

所以，这⾥没有重点讲。重点掌握 HashMap 和 TreeMap。

三、Map

1. Map 和 Collection 没有继承关系

2. Map 以 (key ,value) 的形式存储数据：键值对

         key 和 value 存储的都是对象的内存地址（引⽤）

Map 接⼝常⻅⽅法： 

注意：

Map.Entry<K, V> 是 Map 的⼀个接⼝。接⼝中的内部接⼝默认是 public static 的。 

Map的遍历⽅式

第⼀类⽅法

先获取map 的 keySet，然后取出 key 对应的 value

特点：

效率相对较低。（因为还要根据 key 从哈希表中查找对应的 value）

⽅法1：通过 foreach 遍历 map.keySet()，取出对应的 value 

⽅法2：通过迭代器迭代 map.keySet()，来取出对应的 value 

第⼆类⽅法

调⽤ map.entrySet()⽅法，获取 entrySet，然后直接从 entrySet 中获取 key 和 value。

特点：

        1. 效率较⾼（直接从 node 中获取key，value）

        2. 适⽤于⼤数据量 map 遍历

⽅法3：调⽤ map.entrySet()，然后使⽤ foreach 遍历 entrySet 

⽅法4：调⽤ map.entrySet()，然后使⽤迭代器遍历 entrySet  

1、HashMap 

HashMap 底层是⼀个数组

数组中每个元素是⼀个单向链表（即，采⽤拉链法解决哈希冲突）

        单链表的节点每个节点是 Node<K, V> 类型（见下源码）

同⼀个单链表中所有 Node 的 hash值不⼀定⼀样，但是他们对应的数组下标⼀定⼀样

        数组下标利⽤哈希函数/哈希算法根据 hash值计算得到的

HashMap 是数组和单链表的结合体

        数组查询效率⾼，但是增删元素效率较低

        单链表在随机增删元素⽅⾯效率较⾼，但是查询效率较低

        HashMap 将⼆者结合起来，充分它们各⾃的优点

HashMap 特点

        1. 无序、不可重复

        2. ⽆序：因为不⼀定挂在那个单链表上了

为什么不可重复？

        通过重写 equals ⽅法保证的

HashMap 默认初始化容量： 16

        必须是 2 的次幂，这也是 jdk 官⽅推荐的

        这是因为达到散列均匀，为了提⾼ HashMap 集合的存取效率，所必须的

HashMap 默认加载因⼦：0.75

        数组容量达到 3/4 时，开始扩容

JDK 8 之后，对 HashMap 底层数据结构（单链表）进⾏了改进

        如果单链表元素超过8个，则将单链表转变为红⿊树；

        如果红⿊树节点数量小于6时，会将红⿊树重新变为单链表。

这种方式也是为了提高检索效率，二叉树的检索会再次缩小扫描范围。提高效率。

 

put() 方法原理

先将 key, value 封装到 Node 对象中

底层会调⽤ key 的 hashCode() ⽅法得出 hash 值

通过哈希函数/哈希算法，将 hash 值转换为数组的下标

        如果下标位置上没有任何元素，就把 Node 添加到这个位置上；

        如果下标位置上有但链表，此时会将当前 Node 中的 key 与链表上每⼀个节点中的 key 进行 equals 比较

                如果所有的 equals 方法返回都是 false，那么这个新节点 Node 将被添加到链表的末尾；

                如果其中有⼀个 equals 返回了 true，那么链表中对应的这个节点的 value 将会被新节点 Node 的 value 覆盖。（保证了不可重复）

注：

1. HashMap 中允许 key 和 value 为 null，但是只能有⼀个（不可重复）！

2. HashTable 中 key 和 value 都不允许为 null。

get() 方法原理

先调⽤ key 的 hashCode() 方法得出 hash 值

通过哈希函数/哈希算法，将 hash 值转换为数组的下标

通过数组下标快速定位到数组中的某个位置：

        如果这个位置上什么也没有（没有链表），则返回 null；

        如果这个位置上有单链表，此时会将当前 Node 中的 key 与链表上每⼀个节点中的 key 进⾏ equals 比较。

                如果所有的 equals 方法返回都是 false，那么 get 方法返回 null；

                如果其中有⼀个 equals 返回了 true，那么这个节点的 value 便是我们要找的 value，此时 get 方法最终返回这个要找的 value。

注：

1. 放在 HashMap 中 key 的元素（或者放在 HashSet 中的元素）需要同时重写hashCode() 和 equals() 方法！！！

同时重写 hashCode() 和 equals() ⽅法

重写 hashCode() 方法时要达到散列分布均匀！！！

        如果 hashCode() 方法返回⼀个固定的值，那么 HashMap 底层则变成了⼀个单链表；

        如果 hashCode() 方法所有返回的值都不同，此时 HashMap 底层则变成了⼀个数组。

这两种情况称之为，散列分布不均匀

equals 和 hashCode方法⼀定要同时重写（直接用 eclipse 生成就行）

 

2、HashTable & Properties

HashTable

Properties

Properties 的 key 和 values 都是 String

常⽤⽅法

String getProperty(String key)

Object setProperty(String key, String value)

3、TreeMap

TreeMap 概述

        TreeSet/TreeMap 是自平衡⼆叉树

        TreeSet/TreeMap 迭代器采用的是中序遍历方式

TreeMap 特点

⽆序，不可重复，但是可排序

排序规则

TreeSet/TreeMap中key 可以⾃动对 String 类型或8⼤基本类型的包装类型进行排序

TreeSet ⽆法直接对自定义类型进行排序

直接将⾃定义类型添加到 TreeSet/TreeMap中key 会报错 java.lang.ClassCastException

原因： 是因为⾃定义没有实现 java.lang.Comparable 接口（此时，使用的是 TreeSet 的⽆参构造器）

对 TreeSet/TreeMap 中 key部分元素，必须要指定排序规则。主要有两种解决⽅案：

方法⼀： 放在集合中的自定义类型实现 java.lang.Comparable 接口，并重写 compareTo ⽅法

方法⼆： 选择 TreeSet/TreeMap 带⽐较器参数的构造器 ，并从写⽐较器中的 compare ⽅法

此时，在传递比较器参数给 TreeSet/TreeMap 构造器时，有 3 种方法：

        定义⼀个 Comparator 接⼝的实现类

        使⽤匿名内部类

        lambda 表达式（Comparator 是函数式接口）

                利⽤ -> 的 lambda表达式 重写 compare 方法

                利⽤ Comparator.comparing ⽅法

两种解决方案如何选择呢？

        当比较规则不会发⽣改变的时候，或者说比较规则只有⼀个的时候，建议实现 Comparable 接口

        当比较规有多个，并且需要在多个比较规则之间频繁切换时，建议使用 Comparator 接口

方法⼀代码：

方法二代码：