【Java学习笔记】集合

很多方法你都能在jdk api中找到，为了方便，建议下载一个jdk api方便查询
下载地址:http://blog.fondme.cn/posts/21004/

1. 集合的概述

1. 为什么要引入集合

学习集合之前，我们都知道，在Java中想要存储一组数据，可以使用数组，但是，数组的长度是固定的，很多时候，我们写的项目具体数目是不定的。比方说你写了个学生管理系统，你要对每个班级的学生的数据进行管理，一般学校每个班的人数是差不多了，这个时候按照班级的平均人数定义一个统一长度数组就行了，但是万一突然有一天，一个人数刚好是定义的数组长度的班级，转来了一个学生，你现在得把他的信息录入系统，这个时候，数组肯定就不能使用了，Java早就考虑到了这一点，所以就引入了一个新概念——集合。

2. 集合与数组的区别

1. 长度区别
   数组长度固定
   集合长度不定
2. 内容区别
   数组存储的是同一类型的数据
   集合可以存储不同类型的数据
3. 数据类型
   数组可以存储基本类型也可以存储应用类型
   集合只能存储引用类型

3. Java集合框架

Java集合主要分两大类Collection和Map

• Collection
  存储一群单个对象的集合。其下面还有List、Set、Queue三个子接口。
• Map
  用于存放键值对，每一组数据需要提供一个键和与之对应的值。

2. Collection接口

1. Interface Collection < E >

Collection是集合的顶层，由他引申出去的有三个接口List、Set、Queue。
由于下面三个接口是由Collection引申出来的，所以Collection的方法，下面三个都会继承，所以就先介绍下Collection的基本方法

• 添加元素

boolean add(E e): 把单个元素添加进集合中
boolean addAll(Collection<?extends E> c):将指定集合中的所有元素添加到此集合

• 删除元素

void clear():清空这个集合
boolean remove(Object o):删除这个元素
removeAll(Collection<?> c):删除集合中指定集合包含的元素

• 判断

boolean isEmpty():判断这个集合是否为空
boolean contains(Object o):判断集合中是否包含此元素
boolean containsAll(Collection c):判断集合中是否包含指定的集合元素(要全部包含)

• 长度

int size():获取元素个数

• 交集

boolean retainAll(Collection c):判断集合是否包含指定集合所有元素

• 转数组

Object[] toArray():把集合转为数组

• 迭代器(后面会单独讲)

2. List集合

List是有序集合，也成为序列。他能让存入的数据属于一种有序的存在，用户可以精确控制插入位置，也可以通过整数索引访问元素，而且允许元素重复

基本方法

他基本方法和Collection中的方法基本相同，下面说说他有而Collection没有的

• 比较

boolean equals(Object o):验证一个序列和另一个序列时候相等

• 返回元素

E get(int index)：返回引索对应的元素

• 返回哈希码

int hashCode()：返回该集合的哈希码值

• 返回索引

int indexOf(Object o)：返回元素对应的引索

• 替换

E set(int index,E element)：在给定的引索处将原元素替换为指定元素

• 排序

default void sort(Comparator<? super E> c)：对集合按照比较器的方法排序

具体类

ArrayList

// 构造器 List<数据引用类型> 对象名 = new ArrayList<>();
List<s> al = new ArrayList<>();

1. 实现原理，采用动态对象数组实现，默认构造方法创造了一个空数组
2. 第一次添加元素，扩充容量为10，之后的扩充算法：老容量+老容量的一半
3. 不适合进行删除或者插入操作
4. 为了防止数组动态的扩充次数过多，建议创建ArrayList时，给定初始容量
5. 线程不安全，适合在单线程访问时使用

Vector

// 构造器 List<数据引用类型> 对象名 = new Vector<>();
List<s> al = new Vector<>();

1. 实现原理，采用动态对象数组实现，默认构造方法创建了一个大小为10的对象数组
2. 扩充算法：当增量为0时，扩充为原来大小的0倍，当增量大于0时，扩充为原来大小+增量
3. 不适合删除或者插入
4. 为了防止数组动态扩充次数太多，建议创建Vector时，给定初始容量
5. 线程安全，适合在多线程访问时使用，但是在单线程效率太低

LinkedList

// 构造器 List<数据引用类型> 对象名 = new LinkedList<>();
List<s> al = new LinkedList<>();

1. 实现原理，采用双向链表结构实现
2. 适合插入、删除操作，性能高

选择

1. 安全性问题 Vector
2. 是否频繁插入和删除操作 LinkedList
3. 是否只是存储后遍历 ArrayList

3. Set

Set这种集合与List最大的区别在于，他不能包含重复的元素。他会通过equals方法检测两个元素时候相同，如果相同就不让其添加进去。

基本方法

Set的基本方法与List类似，并没有特殊的，可以参考jdk api

具体类

HashSet

// 构造器 Set<数据引用类型> 对象名 = new HashSet<>();
Set<s> al = new HashSet<>();

1. 实现原理，基于哈希表(HashMap)实现
2. 不允许重复，可以有一个null元素
3. 不保证顺序恒久不变
4. 添加元素时把元素作为HashMap的key存储，HashMap的value使用一个固定的Object对象
5. 排除重复元素是通过equals来检查对象时候相同
6. 判断两个对象时候相同，先判断两个对象的hashCode是否相同（如果两个对象的hashCode相同，未必是同一的对象；如果不同，那就一定不是同一个对象），如果不同，则两个对象不是同一对象，如果相同，还要进行判断equals判断，equals相同则是同一个对象，不同则不是。
7. 自定义对象要认为属性值都相同时，为同一个对象，有这种需求时，那么我们要重写对象所在类的hashCode和equals方法
8. 小结
   
   1. 哈希表的存储结构：数组+链表，数组里的每个元素以链表的形式存储
   2. 如何把对象存储到哈希表中，先计算对象的hashCode值，在对数组长度求余数，来决定对象要存储在数组中的那个位置
   3. 解决hashSet中的重复值使用的方式是，参考第6点

注意:得重写对象的hashCode以及equals方法！！！

TreeSet

1. 有序的，基于TreeMap（二叉树数据结构），对象需要比较大小通过对象比价器来实现。
2. 对象比较器还可以用来去除重复元素，如果自定义的数据类，没有实现比较器接口，将无法添加到TreeSet集合中

LinkedHashSet

1. 哈希表和链接列表实现
2. 维护着一个运行所有条目的双重链接列表。此链接列表定义了迭代顺序，即按照将元素插入到set中的顺序（插入顺序）进行迭代

选择

如果要排序，选择TreeSet
如果不要排序，也不用保证顺序 选择HashSet
如果不要排序，要保证顺序 选择LinkedHashSet

4. Queue

此处内容没学太懂，大家随便看下就行了，以后我再补充

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为 “先进先出”（FIFO—first in first out）的线性表。

基本方法

此接口的方法和Set及List都存在区别，我将重新介绍他的方法

• 构造器

Queue<String> queue = new LinkedList<>();
Deque<String> deque = new LinkedList<>();
Stack s = new Stack();

• 添加

boolean add(E e):增加一个元素，如果队列已满，则抛出一个IIIegaISlabEepeplian异常
boolean offer(E e): 添加一个元素并返回true，如果队列已满，则返回false

• 移除

E remove():检索并删除此队列的头。此方法与poll不同之处在于，如果此队列为空，它将抛出异常。 
E poll():检索并删除此队列的头，如果此队列为空，则返回null 。 

• 检索

E element():检索，但不删除，这个队列的头。此方法与peek的不同之处在于，如果此队列为空，它将抛出异常。 
E peek():检索但不删除此队列的头部，如果此队列为空，则返回null 。 

3. Map接口

Map是Collection另一个子接口，他采用的是键值对的存储方式，将键映射到值的对象，但是不能包含重复的键， 每个键只能映射一个值。
其方法和List方法基本相似，此处不再赘述，需要的可以查看jdk api。

HashMap的实现原理

1. 基于哈希表（数组+链表+二叉树（红黑树））JDK1.8
2. 默认加载因子为0.75，默认数组大小是16
3. 把对象存储到哈希表中，是怎么存储的
   把key对象通过hash()方法计算hash值，然后用这个hash值对数组长度取余（默认16），来决定该KEY对象在数组中存储的位置，当这个位置有多个对象时，以链表结构存储，JDK1.8以后，当链表长度大于8时，链表将转换为红黑树结构存储这样的目的，是为了取值更快，存储的数据量更大，性能表现越明显
4. 扩充原理：当数组的容量超过了75%，那么表示该数组需要扩充，
   扩充的算法是：当前数组容量<<1（相当于是乘2），扩大一倍，扩充次数过多，会影响性能，每次扩充表示哈希表重新散列（重新计算每个对象的存储位置），我们在开发中要尽量减少扩充次数带来的性能问题
5. 线程不安全，适合在单线程中使用，

Hashtable

1. 基于哈希表实现（数组+链表）
2. 默认数组大小为11，加载因子为0.75
3. 扩充方式：原数组大小<<1（*2）+1
4. 线程安全的，用在多线程访问时

LinkedHashMap

LinkedHashMap是HashMap的子类，由于HashMap不能保证顺序永久不变，此类使用一个双重链表来维护

4. Iterator迭代器

迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。

方法

• boolean hasNext()
  如果迭代器中还有元素，返回true
• E next()
  返回迭代器中的下一个元素
• default void remove()
  从底层集合中删除此迭代器返回的最后一个元素（可选操作）。 此方法只能调用一次next() 。 如果底层集合在迭代过程中以任何方式进行修改而不是通过调用此方法，则迭代器的行为是未指定的。
• default void forEachRemaining(Consumer<? super E> action)
  对每个剩余元素执行给定的操作，直到所有元素都被处理或动作引发异常。 如果指定了该顺序，则按迭代的顺序执行操作。 动作抛出的异常被转发给呼叫者。

示例

• 使用hasNext和next方法迭代

Iterator<Cat> iter = c.iterator();
        while (iter.hasNext()){
            System.out.println(iter.next());
        }

5. Collections

Collections是集合的一个工具类，类似于String等工具类，其也提供了各种各样的静态方法，来对集合中的元素进行各种各样的操作。

方法

• 反转
  反转指定列表中元素的顺序

Collections.reverse(list);

• 随机排序
  对集合中的元素进行随机排序

Collections.shuffle(list);

• 按自然升序
  根据其元素的natural ordering ，按照升序排列指定的列表。 列表中的所有元素必须实现Comparable接口。 此外，列表中的所有元素都必须相互可比较 （即e1.compareTo(e2)不能为ClassCastException中的任何元素e1和e2 )

Collections.sort(list);

• 自定义顺序排序
  根据指定的比较器引起的顺序对指定的列表进行排序。 列表中的所有元素必须使用指定的比较器相互比较 （即， c.compare(e1, e2)不能为ClassCastException中的任何元素e1和e2 )

Collections.sort(list,c);

• 交换元素位置
  交换指定列表中指定位置的元素（如果指定的位置相等，调用此方法将保持不变）

Collections.swap(list, 0, 2);

• 将所有元素向右移动指定长度
  将指定列表中的元素旋转指定的距离

Collections.rotate(list, 1);

• 找到指定元素的位置

System.out.println(Collections.binarySearch(list, "tom"));

• 返回最大元素

System.out.println(Collections.max(list));
System.out.println(Collections.max(list,s));

• 返回最小元素

System.out.println(Collections.min(list));

• 填充(全部元素都被替换为obj)
  用指定的元素代替指定列表的所有元素

Collections.fill(list, "bin");

• 返回指定对象出现次数

System.out.println(Collections.frequency(list,"bin"));

• 替换
  将列表中一个指定值的所有出现替换为另一个

Collections.replaceAll(list,"lily","littlecorgi");

• 同步控制(返回指定集合对象对应的同步对象)

List<String> syncList = Collections.synchronizedList(new ArrayList<String>());
Map<Key, Value> syncMap = Collections.synchronizedMap(new HashMap<Key, Value>());
Set<String> syncSet = Collections.synchronizedSet(new Set<String>());

• 返回空集合

List<String> sList = Collections.emptyList();
Map<K, V> sMap = Collections.emptyMap();
Set<T> sSet = Collections.emptySet();

示例

package com.unit09.collectionsdemo;

import java.util.*;

public class CollectionsDemo {
    public static void main(String[] args){
        List<String> list = new ArrayList<>();
        list.add("jack");
        list.add("tom");
        list.add("lily");
        // 反转
        Collections.reverse(list);
        // 随机排序
        Collections.shuffle(list);
        // 按自然升序
        Collections.sort(list);
        // 自定义顺序排序
        Collections.sort(list,c);
        // 交换元素位置
        Collections.swap(list, 0, 2);
        // 将所有元素向右移动指定长度
        Collections.rotate(list, 1);
        // 找到指定元素的位置
        System.out.println(Collections.binarySearch(list, "tom"));
        // 返回最大元素
        System.out.println(Collections.max(list));
        System.out.println(Collections.max(list,s));
        // 返回最小元素
        System.out.println(Collections.min(list));
        // 填充(全部元素都被替换为obj)
        Collections.fill(list, "bin");
        // 返回指定对象出现次数
        System.out.println(Collections.frequency(list,"bin"));
        // 替换
        Collections.replaceAll(list,"lily","littlecorgi");
        // 同步控制(返回指定集合对象对应的同步对象)
        List<String> syncList = Collections.synchronizedList(new ArrayList<String>());
        // 设置不可变集合
        List<String> sList = Collections.emptyList();
        System.out.println(list);
    }
}