## 概述
### 集合与数组
1. 集合和数组都是对多个数据进行存储操作的结构,即 **Java 容器**,此时的存储是指内存层面的存储,不涉及持久化的存储
2. 数组一旦初始化,长度就确定了,而且存储的数据类型也确定了,数组提供的操作方法太少,增删插等操作不方便,效率不高,对于无序、不可重复的要求不能满足
### 集合的特点
1. 用于存储对象的容器,动态存储
2. 集合的长度是可变的
3. 集合中不可以存储基本数据类型值
集合定义在 java.util 包下,可以分为两个体系
* Collection:单列集合,用于存储对象
* List 接口:元素有序、可重复的合
* ArrayList
* LinkedList
* Vector
* Set 接口:元素无序、不可重复的集合
* HashSet
* LinkedHashSet
* TreeSet
* Map:双列集合,用于存储具有映射关系的 **key-value(键值对)** 的对象
* HashMap
* LinkedHashMap
* TreeMap
* Hashtable
* Properties
## Collection 接口
集合容器因为内部的数据结构不同,有多种具体容器,不断向上抽象,就形成了集合框架,框架的顶层是 Collection 接口
### 常见方法
1. 添加
```java
boolean add(Object obj);
// 添加元素
boolean addAll(Collection coll);
// 将coll中的元素添加至调用addAll()的集合中
```
2. 删除
```java
boolean remove(Object obj);
// 删除obj元素
boolean removeAll(Collection coll);
// 将两个集合中相同的元素从当前集合中删除
boolean retainAll(Collection coll);
// 取交集:将两个集合中相同的元素从当前集合中保留,删除不同元素
void clear();
// 清空集合
```
3. 判断
```java
boolean contains(Object obj);
// 判断集合中是否存在 obj 元素,注意,对于重写了 equals() 方法的类,比如String,底层是使用equals方法去比较 obj 对象的内容,如果没有写,则比较地址也就是 Object 类的对象,所以一般要求向集合中添加的类都要重写 equals() 方法
boolean containsAll(Collection coll);
// 判断集合中是否包含coll中的所有元素
boolean isEmpty();
// 判断集合是否为空
boolean equals(Collection coll);
// 判断集合元素是否全部相同(不同的Collection实现类可能考虑或不考虑有序)
```
4. 获取
```java
int size();
// 返回集合中元素的个数
Iterator iterator();
// 取出元素的方式:迭代器,返回迭代器对象,因为每个容器的数据结构不同,所以该迭代器对象是在具体容器内部实现的,具体实现方法对于使用容器者不重要
```
5. 其他
```java
int hashcode();
// 返回集合的哈希值
Object[] toArray();
// 将集合转成数组
```
注意:数组转换为集合需要 Arrays 类的静态方法 asList(T t)
```java
String str[] = new String[]{"hello","","world"}
List list = Arrays.asList(str);
System.out.println(list);
ArrayList list1 = Arrays.asList(new Integer[]{123,456});
System.out.println(list1);
LinkedList list2 = Arrays.asList(new int[]{123,456});
System.out.println(list2);
```
## 遍历集合
### Iterator 迭代器接口
Iterator 接口的对象即**迭代器**,用于遍历 Collection 容器(不用于 Map 遍历)中的元素,而不暴露容器的内部细节,注意集合对象每次调用 iterator() 都会得到一个**全新**的迭代器对象
**方法**
* hasNext()
* 判断当前指针位置的下一位置是否存在元素
* 如果不用此方法控制遍历,可能出现 NoSuchElementException
* next()
1. 指针下移
2. 返回指针下移之后所指位置上的元素
* remove()
在遍历的时候删除集合中的元素,此方法不同于集合直接调用remove(),如果还未调用 next()方法,或在上次调用 next()方法后已经调用了 remove()方法,再调用 remove() 方法的时候会出现 IllegalStateException
**遍历的正确方方式**
```java
Iterator it = coll.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
```
**错误1**
```java
Iterator it = coll.iterator();
// 调用 next() 就会让指针后移
while(it.next()!=null) {
System.out.println(it.next());
}
```
**错误2**
```java
Iterator it = coll.iterator();
// 调用集合的 iterator() 就会返回一个全新的迭代器
while(coll.iterator().hasNext()) {
System.out.println(coll.iterator().next());
}
```
**使用迭代器删除集合中的对象**
```java
Iterator iterator = coll.iterator;
while(iterator.hasNext()) {
Object obj = iterator.next();
if(targetObj.equals(obj)) {
iterator .remove();
}
}
```
### JDK5.0 新增 foreach 循环
```java
Collection coll = new ArrayList();
coll.add(123);
coll.add("hello world");
coll.add(false);
// 集合元素的类型 局部变量 : 集合对象
for(Object obj : coll) {
System.out.println(obj);
}
int[] arr = new int[]{1,2,3,4,5};
// 数组元素的类型 局部变量 : 数组对象
for(int i : arr) {
Syetem.out.println(i);
}
```
注:增强 for 循环在底层也是调用迭代器
## Collection 子接口:List
List 中的元素**有序**、**可重复**,每个元素都有其对应的顺序**索引**,可以根据索引存取,可以用来代替数组
List 接口的实现类主要是:ArrayList,LinkedList,Vector
* ArrayList 是 List 的主要实现类,线程不安全,效率高,底层使用数组存储数据
* LinkedList 底层使用双向链表,如果频繁插入和删除操作,效率高于 ArrayList
* Vector 作为 List 接口的古老实现类,线程安全,效率低,底层使用数组存储数据
### ArrayList
**jdk7**
* 使用数组存储数据
* 空参构造器 ArrayList()
初始化一个长度为 10 的 Object 数组
* 添加数据 add(E e)
如果此次添加数据导致底层的 elementData 数组容量不够,则扩容,默认情况下,扩容为 newCapacity = oldCapacity + (oldCapacity >> 1),即原来容量的 1.5 倍,然后将原数组中的数据复制到新的数组中
* 建议使用有参构造器,先指定一个容量,减少扩容次数
ArrayList list = new ArrayList(int initialCapacity)
**jdk8**
* 空参构造器
底层数组初始化为{},没有创建长度为 10 的数组,相当于懒汉式,延迟了对象创建,节省内存
* add()
第一次调用 add() 的时候,底层才创建了长度为10的数组,并将数据添加进数组,后续的添加和扩容与jdk7一样
### LinkedList
* LinkedList 内部将元素封装到 Node 对象中,且声明了 Node 类型的 first 和 last 属性,默认值为 null,分别指向链表头尾
* add() 创建 Node 对象
```java
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev,E element,Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
```
### Vector
Vector 扩容方式:默认扩容为之前的2倍
### List 接口中常用方法
相比 Collection 中的常用方法,多了关于索引的方法
```java
void add(int index,Object ele)
// 在 index 索引位置插入元素
boolean addAll(int index,Collection eles)
// 从index索引位置开始将eles中所有元素添加进来
Object get (int index)
// 获取指定 index 索引位置的元素
Object set(int index,Object ele)
// 修改指定index位置的元素为ele
int indexOf(Object obj)
// 返回 obj 在集合中首次出现的索引,若不存在,返回 -1
int lastIndexOf(Object obj)
// 返回 obj 在集合中末次出现的索引,若不存在,返回 -1
Object remove(int Index)
// 移除指定 index 位置的元素,并返回该元素,注意 Collection 中的remove(Object obj)是按照对象删除
List subList(int fromIndex,int toIndex)
// 返回从 fromIndex 到 toIndex 位置的子集,左闭右开
```
### 对比 ArrayList 和 LinkedList
||ArrayList|LinkedList|
|---|---|---|
|底层实现|数组|链表|
|获取指定元素|速度很快|需要从头开始查找元素|
|添加元素到末尾|速度很快|速度很快|
|在指定位置添加/删除|需要移动元素|不需要移动元素|
|内存占用|小|较大|
## Collection 子接口:Set
1. 无序性
以 HashSet 为例,底层使用数组加链表实现,但是存储的数据在底层数组中并非按照数组的索引的顺序添加,而是根据**哈希值**确定,遍历的顺序不同于添加元素的顺序,但是每次的遍历顺序是相同的,**不等于随机性**
2. 不可重复性
向 Set 中添加的对象不可以重复,即保证添加的元素按照 equals() 判断时,不可返回true
3. Set 没有提供额外的方法
### HashSet
* 作为 Set 接口的主要实现类,线程不安全,可以存储 null 值
* 底层实现是数组加链表
* **添加元素的过程**
向 HashSet 中添加元素 A,首先调用元素 **A 所在类**的 hashCode() 方法,计算元素 A 的 hash 值,然后此 hash 值通过某种算法计算出元素在 HashSet 底层数组中的存放位置(索引),判断数组如果此位置上没有其他元素,则添加成功,如果有其他元素 B(或以链表形式存在多个元素),则比较元素 A、B 的 hash 值,若不同,则添加成功,若哈希值相同,再调用 A 所在类的 equals() 方法,equals() 返回 true 则添加失败,若返回false,则添加成功,并以链表形式进行存储
* 对于自定义类,如果没有重写 hashcode() 方法,则调用 Object 的 hashcode(),类似于随机数,就算两个对象的内容一样,哈希值也不同,那么放入底层数组的时候位置就大概率不同,所以也不会去调用 equals() 方法比较内容,调用 equals() 只会出现在:重写了 hashcode() 方法且哈希值相同且数组索引相同的情况下。如果 equals() 也返回 true,再使用链表追加
* 要求:向set中添加的数据,其所在的类一定要重写 equals() 方法和 hashCode() 方法,且相同的对象一定要具有相等的哈希值,也就是说对象中用于 equals() 比较的 Field 也一定要用于计算哈希值
* 注意,如果指定索引位置上已经以链表形式储存元素
* jdk7 中,元素 A 放入数组中,指向原来的元素
* jdk8 中,原来的元素放入数组中,指向 A
### LinkedHashSet
* 作为 HashSet 的子类,遍历其内部数据时,可以按照添加的顺序遍历
* 其底层也是使用数组加链表存储数据,但同时也维护了**两个引用**,记录此数据的前后数据元素,对于频繁遍历,能提高效率
### TreeSet
* 底层使用红黑树,要求存入的数据必须是**同一个类的对象**,对象不可重复
* 可以按照添加对象的指定属性进行排序:自然排序(实现 Comparable 接口)或定制排序(实现 Comparator 接口)
* TreeSet 存储的元素必须实现了 Comparable 接口,或者创建 TreeSet 对象时传入一个 Comparator 接口的实现类对象
## Map 接口
* Map 接口存储双列数据,即 key-value(键值对)的数据
* Map 中的 key 是**无序不可重复**的,使用 Set 存储 key,key 所在的类必须重写 equals() 和 hashCode()
* Map 中的 value **无序可重复**,使用 Collection 存储,value 所在的类要重写 equals()方法
* 一个 key-value(键值对)构成一个 Entry 对象,Entry 对象是**无序不可重复**的,使用 Set 存储
### HashMap
* HashMap 是 Map 的主要实现类,线程不安全,效率高,可以存储值为 null 的 key 和 value
* 底层实现:jdk7及之前使用**数组 + 链表**,jdk8 使用**数组 + 链表 + 红黑树**
**jdk7**
* HashMap map = new HashMap();
实例化一个 HashMap,底层创建了一个长度为 16 的数组 Entry[] table
* map.put(k,v);
首先调用 k 所在类的 hashCode() 方法计算 k 的哈希值,此哈希值再通过某种算法计算得到在 Entry[] 数组中的存放位置(索引)
* 如果此位置上的数据为空,则 k-v 添加成功
* 如果此位置上的数据不为空,也就是说此位置上存在一个或多个(链表形式)数据,则比较 k 和已存在的数据(一个或多个)的哈希值
* 如果 k 的哈希值与已存在的数据的哈希值都不同,则 k-v 添加成功(以链表形式)
* 如果 k 的哈希值和已经存在的某个数据的哈希值相同,继续比较
* 调用 k 所在类的 equals()方法,如果 equals()返回 false,k-v添加成功
* 如果 equals()返回 true:使用 v 替换之前的键值对中的 value(即修改已有的数据)
* 在不断地添加过程中,涉及到扩容问题,当超出临界值且要存放的位置非空时,进行扩容,默认扩容方式:扩容位原来的2倍,并将元素复制到新的 Map
**jdk8**
* new HashMap() 没有创建一个长度为 16 的数组
* 底层为 Node[] 数组而不是 Entry[]
* 首次调用 put() 方法时才创建长度为 16 的数组
* 当数组某个索引位置的元素以链表形式存在的数据个数 >8,且数组长度 >64 时,该索引位置上所有数据改为使用红黑树存储
```java
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
}
```
**底层典型属性**
* DEFAULT_INITIAL_CAPACITY:HashMap的默认容量,16
* DEFAULT_LOAD_FACTOR:HashMap的默认加载因子,0.75
* threshold:扩容的临界值,= 容量*加载因子:16 * 0.75 => 12
* TREEIFY_THRESHOLD:Bucket 中链表长度大于该默认值 8,转化为红黑树
* MIN_TREEIFY_CAPACITY:Bucket 中的 Node 被树化时最小的数组容量,64
### LinkedHashMap
* LinkedHashMap 继承于HashMap,其底层使用的结构与 HashMap 相同,
* LinkedHashMap 内部提供了 Entry,替换 HashMap 中的 Node
* 底层的 Entry 类加了一对指针指向前后元素,可以按照添加元素的顺序实现遍历,对于频繁的遍历操作,效率高于HashMap
```java
static class Entry extends HashMap.Node {
Entry before,after;
Entry(int hash,K key,V value,Node next) {
super(hash,key,value,next)
}
}
```
### TreeMap
TreeMap 底层使用**红黑树**,向 TreeMap 中添加 key-value,要求 key 必须是用同一个类创建的对象,因为要按照 key 进行排序,实现自然排序(Comparable)或定制排序(Comparator)
### Hashtable
Hashtable 是 Map 的古老实现类,线程安全,效率低,不能存储值为 null 的 key 和 value
### Properties
* 作为 Hashtable 的子类,常用于处理配置文件
* 配置文件中的 key 和 value 都是 字符串,所以 Properties 中的 key 和 value 都是 String
* 存取数据时,建议使用 setProperty(String key,String value) 方法和 getProperty(String key)
```java
Properties pros = new Properties();
// 加载对应的文件流,这里简写,实际应用时,需要捕捉异常和关闭资源
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);
```
### 常用方法
```java
Object put(Object key,Object value)
// 将指定 key-value 添加到(或修改)当前 Map 对象中
void putAll(Map m)
// 将 m 中的所有 key-value 存储到当前 Map 对象中
Object remove(Object key)
// 移除指定 key 的key-value 对,并返回 value,如果当前 Map 中没有指定的 key,返回null
void clear()
// 清空当前 Map 对象中的数据,注意不是 map=null 操作,当前 Map 对象依然存在
Object get(Object key)
// 获取指定 key 对应的 value
boolean containsKey(Object key)
// 是否包含指定的key
boolean containsValue(Object value)
// 是否包含指定的value
int size()
// 返回当前 Map 对象的 key-value 对的个数
boolean isEmpty()
// 判断当前 Map 对象是否为空
boolean equals(Object obj)
// 判断当前 Map 对象和参数对象 obj 是否相同
/* 遍历Map ,先获取 key-value 对应的集合,之后可以用迭代器去遍历*/
Set keySet()
// 返回所有key构成的Set集合
Collection values()
// 返回所有 value 构成的 Collection 集合
Set entrySet()
// 返回所有 key-value 对构成的 Set 集合
```
## Collections 工具类
Collections 是操作 Collection、Map 的工具类
**常用方法**
```java
void reverse(List> list)
// 反转 List 中的元素的顺序
void shuffle(List> list)
// 对List中的元素进行随机排序
void sort(List)
// 根据自然顺序升序排序,List 中的元素必须实现了 Comparable 接口
void sort(List list, Comparator super T> c)
// 根据指定 Comparator 产生的顺序对 List 集合元素进行排序
void swap(List> list,int i,int j)
// 将指定索引位置的两个元素交换
void copy(List dest,List src)
// 将 src 中的内容复制到 dest 中
boolean replaceAll(List list,Object oldVal,Object newVal)
// 使用新值替换 List 对象的所有旧值
Object max(Collection coll)
// 根据自然顺序,返回最大元素,元素必须实现了 Comparable 接口
Object max(Collection coll ,Comparator comp)
// 根据指定的比较器引发的顺序,返回给定集合的最大元素
Object min(Collection Coll)
// 根据自然顺序,返回最小元素,元素必须实现了 Comparable 接口
Object min(Collection Coll,Comparator comp)
// 根据指定的比较器引发的顺序,返回给定集合的最小元素
int frequency(Collection> c,Object o)
// 返回集合中元素 o 出现的次数
```
**不可变集合**
Collections 还提供了一组方法把可变集合封装成不可变集合
```java
List unmodifiableList(List extends T> list)
Set unmodifiableSet(Set extends T> set)
Map unmodifiableMap(Map extends K, ? extends V> map)
```
**注意**:继续对原始的可变集合进行增删是可以的,并且,会直接影响到封装后的不可变集合。因此,如果希望把一个可变集合封装成不可变不可变,那么,返回不可变集合后,最好立刻置空可变集合的引用
**线程安全集合**
ArrayList 和 HashMap 都是线程不安全的,Collections还提供了一组方法,可以把线程不安全的集合变为线程安全的集合
```java
List synchronizedList(List list)
Set synchronizedSet(Set set)
Map synchronizedMap(Map map)
```
**注意**:Java 5 引入了更高效的并发集合类,所以上述这几个同步方法已经没有什么用了

Java基础 | 集合框架