第14章集合(P499 - P553)¶

1、集合框架体系¶

单列集合

双列集合

2、单列集合¶

1、Collection接口和常用方法¶

collection接口实现特点

public interface Collection<E\> extend Iterable<E\>

collection 实现子类可以存放多个元素，每个元素可以是Object
有些Collection的实现类，可以存放重复元素，有些不可
有些Collection的实现类，有些是有序的（List），有些不是（Set）
Collection 接口没有直接的实现子类，是通过它的子接口Set和List来实现的
常用方法
add(); 添加单个元素
remove(); 删除指定元素
contains(); 查找元素是否存在
size(); 获取元素个数
isEmpty(); 判断是否为空
clear(); 清空
addAll(); 添加多个元素
containsAll(); 查找多个元素是否都存在
removeAll(); 删除多个元素

2、Collection 接口便利元素方式¶

使用 Iterator （迭代器）
Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素
所有实现了Collection 接口的集合类都有一个 iterator（）方法，用以返回一个实现了Iterator 接口的对象，即可以返回一个迭代器
Iterator 的结构图

注意：在调用iterator.next() 方法之前必须要调用iterator.hasNext() 进行检测，若不调用，并且下一条记录无效，直接调用iterator.next() 会抛出NoSuchElementException 异常。
Iterator 仅用于遍历集合，Iterator 本省并不存放对象
当再次使用迭代器时，需要重置迭代器

iteraator = col.ietrator();

快捷键：itit

显示所有快捷键的快捷键：Ctrl + j

增强 for 循环

增强for循环，可以代替iterator迭代器，特点：增强 for 就是简化版的iterator，本质一样。只能用于遍历集合数组

基本语法

for (元素类型元素名: 集合名或数组名) {

访问元素

}
快捷键：I

3、List接口¶

基本介绍

List 接口时 Collection 接口的子接口

List 集合类中所有元素有序（即添加顺序和取出顺序一致）、且可重复
List 集合中的每个元素都有相应的顺序索引，即支持索引
List 容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素

list.get(3)
JDK API 中 List 接口的实现类有

常用的有：ArrayList、LinkedList、Vector
常用方法
void add(int index,Object ele)：在index位置插入ele元素
boolean addAll(int index,Collection eles)：从index位置开始将eles中所有元素添加进来
Object get(int index)：获取指定index位置的元素
int indexOf(Object obj)：返回obj在当前集合中首次出现的位置
int lastIndexOf(Object obj)：返回obj在当前集合中最后一次出现的位置
Object remove(int index)：移除指定index位置的元素，并返回此元素
Object set(int index,Object ele)：设置指定index位置的元素为ele，相当于是替换
List subList(int fromIndex,int toIndex)：返回从fromIndex到toIndex位置的子集合 [fromIndex,toIndex)

1、ArrayList¶

ArrayList 的底层操作机制源码分析
ArrayList中维护了一个Object类型的数组elementData

transient Object[] elementData;//transient 表示瞬间，短暂的，表示该属性不会被序列化
当创建ArrayList对象时，如果使用的时无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如果需要再次扩容，则扩容elementData为1.5倍
如果使用的是直接指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍

2、Vector底层结构和源码刨析¶

基本介绍
Vector 类定义说明
Vector 底层也是一个对象数组，protected Object[] elementData;
Vector 是线程同步的，即线程安全，Vector类的操作方法带有 synchronied
在开发中，需要线程同步安全时，考虑使用Vector
扩容机制

如果是无参，默认10，满后，就按2倍扩容

如果指定大小，则每次直接按2倍扩容

3、LinkedList底层结构¶

说明
LinkedList 底层实现了双向链表和双端队列的特点
可以添加任意元素
线程不安全，没有实现同步
LinkedList 的底层操作机制
LinkedList 底层维护了一个双向链表
LinkedList 中维护了两个属性first和last分别指向首节点和尾节点
每个节点（Node对象），里面有维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表
所以LinkedList 的元素的添加删除，不是通过数组完成的，相对来说效率较高

4、ArrayList和LinkedList的比较¶

	底层结构	增删效率	改查效率
ArrayList	可变数组	较低数组扩容	较高
LinkedList	双向链表	较高通过链表追加	较低

如何选择
改查操作多，选择ArrayList
增删比较多，选择LinkedList
一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList
在一个项目中，根据业务灵活选择，也可能是这样，一个模块使用的是ArrayList，另一个模块是LinkedList

4、Set接口¶

Set接口基本介绍
无序（添加和取出顺序不一致），没有索引
不允许重复元素，所以最多包含一个null
JDK API 中Set接口的实现类有：
Set接口的常用方法

和List接口一样，Set接口也是Collection子接口，因此常用方法和Collection接口一样

Set接口的遍历方式

同Collection的遍历方式一样

不能用索引的方式来获取

1、HashSet¶

HashSet实现了Set接口
HashSet实际上是HashMap
可以存放null值，但是只能有一个null
HashSet不保证元素是有序的，取决于hash后，在确定索引的结果
不能有重复的元素/对象
HashSet 底层机制

HashSet 底层是（数组 + 链表 + 红黑树）

HashSet 底层是 HashMap
添加存储数据表table，看这个索引位置是否已经存放元素
如果没有，则直接加入
如果有，调用equals 比较，如果相同，就放弃添加，如果不同，则添加到最后
在Java8 中，如果一条链表的元素个数到达TREEIFYTHRESHOLD(默认是8)，并且table的大小 >= MINTREEIFY_CAPACITY(默认64)就会进行树化（红黑树）
扩容机制
HashSet底层是HashMap，第一次添加时，table 数组扩容到16，临界值（threshold）是16*加载因子（loadFactor）是0.75 = 12

依照的是size（每加入一个元素，size 就会加 1）
如table 数组使用到了临界值 12，就会扩容到16*2=32，新的临界值就是32*0.75=24，以此类推
在Java8 中，如果一条链表的元素个数到达TREEIFYTHRESHOLD(默认是8)，并且table的大小 >= MINTREEIFY_CAPACITY(默认64)就会进行树化（红黑树）

2、LinkedHashSet¶

LinkedHashSet说明
LinkedHashSet是HashSet的子类
LinkedHashSet 底层是一个LinkedHashMap，底层维护了一个数组 + 双向链表（LinkedHashSet 有 head 和 tail）
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的
LinkedHashSet 不允许添加重复元素
每个结点有 befor 和 after 属性，这样可以形成双向链表
在添加一个元素使，先求hash值，在求索引，确定该元素在hashtable的位置，然后添加的元素加入到双向链表（如果已经存在，不添加【原则和hashset一样】）
确保遍历LinkedHashSet 插入顺序和遍历顺序一致

5、Map接口¶

Map接口实现类特点
Map与Collection并列存在。用于保存具有映射关系的数据：Key - Value（双列元素）
Map 中的 Key 和 value 可以是任何引用类型的数据，会封装到 HashMap$Node 对象中
Map 中的 key 不允许重复（当有相同的 key ，就会替换），原因和 HashSet 一样
Map 中的 value 可以重复
Map 的 key 可以为 null ，value 也可以为 null，注意 key 为 null，只能有一个，value 为 null ，可以多个
常用 String 类作为 Map 的 key
key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value
Map存放数据的 key-value示意图，一对 k-v 是放在一个Node中的，因为 Node 实现了 Entry 接口
解读
k-v 最后是HashMap$Node node = newNode（hash，key，value，null）
k-v 为了方便遍历，还创建 EntrySet 集合，该集合存放的元素的类型 Entry ，而一个 Entry 对象就有 k，v EntrySet> 即： transient Set> entrySet;
entrySet 中，定义的类型是 Map.Entry，但实际上存放的还是 HashMap$Node ，因为 static class Node implements Map.Entry
当把 HashMap$Node 对象，存放到 entrySet 就方便我们遍历，因为 Map.Entry 提供了方法 K getKey(); V getValue();
Map接口常用方法
put：添加
remove：根据键（key）删除映射关系
get：根据键获取值
size：获取元素个数
isEmpty：判断个数是否为0
clear：清除
containsKey：查找键是否存在
Map接口遍历方法
containsKey：查找键是否存在
keySet：获取所有的键
entrySet：获取所有关系
vlaues：获取所有的值
HaspMap小结
HashMap 使Map 接口使用频率最高的实现类
HaspMap没有实现同步，因此线程是不安全的，方法没有做同步互斥的操作
HashMap底层机制及源码
扩容机制
1. HashMap 底层维护了Node 类型的数组table ，默认为null
2. 当创建对象时将加载因子（loadfactor)初始化为0.75
3. 当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key是否和准备加入的key相等，如果相等，则直接替换val；如果不相等需要判断是树结构还是链表结构，做出相应的处理。如果添加时发现容量不够，则需扩容
4. 第一次添加，则需要扩容table容量为16，临界值（threshold）为12
5. 以后再扩容，则需要扩容table容量为原来的2倍，临界值为原来的2倍，及24，以此类推
6. 再java8 中，如果一条链表的元素个数超过 TREEIFYTHRESHOLD(默认是 8)，并且 table 的大小 >= MINTREEIFY_CAPACITY(默认64)，就会进行树化（红黑树）

1、HashTable¶

HashTable 基本介绍
存放的元素是键值对：即 K - V
hashTable的键和值都不能为null
hashTable 使用的方法基本上和HashMap一样
hashTable 是线程安全的，hashMap 是线程不安全的
HashTable的底层
底层有数组 HashTable$Entry[] 初始化大小为 11
临界值 threshold 8 = 11 * 0.75
按照 int newCapacity = (oldCapacity << 1) + 1; 的大小扩容

2、Properties¶

基本介绍
Properties类继承自HashTable类并实现了Map接口，也是使用一种键值对的形式来保存数据
使用特点和HashTable类似
Properties 还可以用于从 xxx.properties 问文件中，加载数据到Properties 类对象，并进行读取和修改，（xxx.properties 文件通常作为配置文件）

3、总结——开发中如何选择集合实现类¶

先判断存储的类型（一组对象【单列】或一组键值对【双列】
一组对象【单列】：Collection接口
- 允许重复：List
- 增删改查多：LinkedList【底层维护了一个双向链表】
- 改查多：ArrayList【底层维护了 Object类型的可变数组】
- 不允许重复：Set
- 无序：HashSet【底层是HashMap，维护了一个哈希表，即（数组 + 链表红黑树）】
- 排序：TreeSet
- 插入和取出顺序一致：LinkedHashSet，维护了数组 + 双向链表
- 一组键值对【双列】：Map
- 键无序：HashMap【底层是：哈希表 jdk7：数组 + 链表，jdk8：数组 + 链表 + 红黑树】
- 键排序：TreeMap
- 键插入和取出顺序一致：LingkedHashMap
- 读取文件：Proerties

4、Collection工具类

collection 工具类介绍
Collection 是一个操作 Set、List 和 Map 等集合的工具类
Collection 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作
排序操作：（均为static方法）
reverse（List）：反转List中元素顺序
shuffle（Lise）：对List 集合元素进行随机排序
sort（List）：根据元素的自然顺序对指定 List 集合元素按升序排序
sort（List，Comparator）：根据指定的 Comparator 产生的顺序对List 集合元素进行排序
swap（List，int，int）：将指定List 集合中的 i 出元素和 j 处元素进行交换
查找、替换
Object max（Collection）：根据元素的自然顺序，返回给定集合中的最大元素
Object max（Collection，Comparator）：根据Comparator 指定的顺序，返回给定集合中的最大元素
Object min（Collection）
Object min(Collection,Comparator)
int frequency(Collection,Object)：返回指定集合中指定元素出现的次数
void copy(List dest,List src)：将src中的内容复制到dest中
boolean replaceAll（List list，Object oldVal，Object newVal）：使用新值替换List 对象的所有旧值

第14章 集合(P499 - P553)¶