Java学习笔记——集合

集合的概念 概念

在java.util包中，可以存放对象的容器

集合中只能存放对象集合中存放的是多个对象的引用，对象本身还是存放在堆内存中集合中可以存放不同类型、不限数量【size():int】的数据类型的数据，如果不使用泛型约束存储数据的类型，则默认Object 数组和集合的比较

数组	集合
定长	变长存储数据的容器，容量可以动态改变
不是面向对象的	弥补了数组的缺陷，比数组更灵活
存放简单类型和引用类型的数据	存放的都是对象的引用
无法判断存储的元素个数，length：容器的大小	size：元素的个数
仅采用顺序表的方式	有多种不同的实现方式和不同的适用场景
	以类的形式存在，具有三大特征

Collction体系集合 Collection父接口 方法

boolean add(Object obj)//添加一个对象

boolean addAll(Collection c)//将一个集合中的所有对象添加到此集合

void clear()//清空此集合中的所有对象

boolean contains(Object o)//检查此集合中是否包含o对象

boolean equals(Object o)//比较此集合是否与指定对象相等

boolean isEmpty()//判断此集合是否为空

boolean remove(Object o)//在此集合中移除o对象

int size()//返回此集合中的元素个数

Object[] toArray()//将此集合转换成数组

Iterator iterate()//迭代集合中的所有元素

//遍历集合中的所有元素
for(Object tmp:collection){}

//使用迭代器
Iterator it = collection.iterator();
while(it.hasNext()){
    Object tmp = it.next();
}

List接口与实现类 List子接口 方法

void add(int index, Object o)//在index位置上插入对象o

boolean addAll(int index, Collection c)//将一个集合中的元素添加到集合中的index位置

Object get(int index)//返回集合中指定位置的元素

List subList(int fromIndex, int toIndex)//返回fromIndex和toIndex之间的集合元素

Object remove(int index)//删除指定位置上的元素，并返回删除的数据

Object set(int index, Object obj)//修改指定位置上的元素，并返回原始数据

boolean addAll(Collection c)//将一个集合中的所有对象添加到此集合

int indexOf(Object obj)//查找元素的下标位置

List实现类 ArrayList

内部采用数组实现

实现了RandomAccess接口，支持随机访问功能不是一个线程安全的容器具体存储数据使用的是transient Object[] elementData具体元素的移动和拷贝都是通过System.arrayCopy实现的 构造器

ArrayList()内部存储数据的数组为空数组

elementData保存数据capacity容器 ArrayList(int) 默认容积10当容器容积不足时，会自动进行扩容处理，容积增大50%modcout快速失败

无参构造器

new ArrayList()，JDK1.8采用的是延迟数组初始化操作elementData={}，这是一种针对内存消耗的优化处理

带参构造器

new ArrayList(18) 初始化容积 capacity和size

add方法

添加元素时首先仅从范围检查，然后和建议分配的大小值进行比较，如果大于默认大小则进行扩容。扩容时首先将原始数组的大小提升到1.5倍，称为新数组大小，然后进行元素的拷贝

remove方法

删除元素，但是没有变小容积的处理

线程安全的替代方案：Collections.sychronizedList CopyOnWriteArrayList

get方法

首先进行索引序号[0,size()-1]检查，然后判定是否有并发修改[快速失败处理modcount]，最后按照下标从数组中获取元素

Vector

内部采用数组实现，同时线程安全

在构造器中直接初始化数组

linkedList

内部采用双向链表，没有长度限制

实现了Deque接口，双向队列没有容积的限制，所以无限制追加元素[size():int]

transient int size = 0;
transient Node first;
transient Node last;

删除remove(Object)虽然删除操作时间复杂度O(1)，但是定位元素的时间复杂度为O(n)

	ArrayList	linkedList	Vector
实现方式	底层实现是数组	底层实现是双向链表	底层实现是数组
查询增删	查询快，增删慢	查询慢，增删快	查询快，增删慢
线程安全	线程不安全、没有同步处理，并发访问效率高	线程不安全、没有同步处理，并发访问效率高	线程安全、同步处理，并发访问效率较低

Set接口和实现类 Set子接口 方法

全部继承Collection中的方法，没有新方法，对add、equals和hashCode方法添加了限制

当添加的两个对象类型元素的hashCode值相等时，才会调用equals判定相等

如果hashCode值不相等，则不会调用equals方法

允许使用null元素

具体实现类有HashCode、linkedHashSet和TreeSet

Set–>HashSet–>linkedHashSetSortedSet–>TreeSet Set实现类 HashSet 概念

HashSet实现了Set接口，底层实际上是包装了一个HashMap实现的

private transient HashMap map;//具体存储数据的实现
private static final Object PRESENT == new Object();//向HashSet中存储数据实际上是利用HashMap存储Key-Value的方式进行存储，其中key是HashSet中存储的数据，value是一个常量对象PRESENT

HashSet采hash算法来存储集合中的元素，因此具有良好的读写性能

调用add方法向HashSet中添加元素时，首先针对对象的hashCode值进行比较。HashCode值相等——>继续调用equals方法。

定义类时，如果equals为true，则hashCode必须相等，反之不一定。

HashSet方法没有同步约束，所以线程不安全

HashSet允许添加null元素

HashSet常见方法方法

boolean contains(Object)Object[] toArray()：放回包含所有元素的数组；如果需要指定返回数组的类型，可以使用toArray(类型[])boolean add(Object)boolean remove(Object)

//典型错误
Set set = new HashSet<>();
for(int i =0; i< 10; i++){
    set.add("set-"+i);
}
Iterator it = set.iterator();
while(it.hasNext()){
    String tmp = it.next;
    sout(tmp);
//  set.remove(tmp);//ConcurrentModificationException--modCount
    it.remove();//删除刚访问过的元素
}

常见问题：hashset是如何保证数据不重复的

HashSet的底层实际上就是HashMap，只不过 HashSet是实现了Set接口，并且把数据作为key值，而具体的value值一直使用一个相同的虚值来实现的 private static final Object PRESENT = new Object();

public boolean add(E e){
    return map.put(e,PRESENT)==null;//调用hashmap中的put方法添加数据，其中添加的元素是key值，具体的value是hashset中定义一个常量
}

由于HashMap的key值不允许重复，并且在HashMap中如果出现key值相同时，会使用新的value覆盖旧有的value，然后返回就有的value值，那么在hashset中执行这句话就会返回一个false，表示插入失败，这样就能保证了数据的不可重复性

linkedHashSet

底层采用的是链表和哈希表的算法，使用链表记录元素的添加位置，使用哈希表保证元素的唯一性

链表实现的HashSet，按照链表进行存储，即可保留元素的插入顺序

linkedHashSet是HashSet的一个子类，linkedHashSet也是根据hashCode值来决定元素的具体存储位置，但是同时它引入了一个链表可以维护元素的插入顺序

使用HashSet存储数据，并遍历访问

使用linkedHashSet存储数据，并遍历访问

SortedSet接口 TreeSet

基于排列顺序实现元素不重复

实现了SortedSet接口，对集合元素自动排序

元素对象的类型必须实现Comparable接口，指定排序规则

通过CompareTo方法确定是否为重复元素

TreeSet是一种排序的Set集合

数据存储采用的是NaviatableMap，底层实际上就是TreeMap实现的，本质上是一个红黑树原理

	HashSet	linkedHashSet	TreeSet
	无序（不仅不能保证元素的插入顺序，而且元素以后的顺序也可能发生改变），底层采用的是哈希算法，查询效率高	linkedHashSet是HashSet的子类，底层采用的是哈希算法以及链表实现，既能保证元素的添加顺序，同时也保证了查询性能。但是由于需要额外维护链表结构，所以整体性能要略低于HashSet	TreeSet不保证元素的添加顺序，但是会对集合中的元素进行排序。底层采用的是红黑树的实现，但是由于需要定位存储位置，所以增删的效率较低。
	存储的元素不允许重复（equals和hashCode）	如果访问的顺序和插入的顺序一致，使用linkedHashSet	Comparable接口或者自定义Comparator
	要求存入HashSet中的元素必须覆盖定义equals()和hashCode()两个方法，判断元素相等需要依赖这两个方法	要求存入HashSet中的元素必须覆盖定义equals()和hashCode()两个方法
性能分析	HashSet和TreeSet是Set集合中使用最多的集合，HashSet的性能总是比TreeSet集合的性能好，因	linkedHashSet需要额外维护链表以实现记录元素的插入顺序，因此在插入时性能比HashSet低，

Set的典型问题

1.使用Set集合可以剔除集合中的重复元素

Random r = new Random();
List list = new ArrayList();
for (int i = 0; i < 10; i++) {
	list.add(r.nextInt(20));
}
System.out.println(list);
		
Set set = new linkedHashSet<>(list);
System.out.println(set);

2.读取一个英文文档，获取其中有哪些字符（去重复）

读取文本文件可以使用BIO中的字符文件流每次获取一个字符 String提供了方法charAt(int):char存储数据可以使用set，以达到去重复的目的

BufferedReader br = new BufferedReader(new FileReader("abc.txt"));
Set set = new HashSet();
String str = null;
while ((str=br.readLine())!=null) {
	for (int i = 0; i < str.length(); i++) {
		char cc = str.charAt(i);
		set.add(cc);
	}
}
System.out.println(set);

Map接口与实现类

Map接口与Collection接口没有任何关系，也是一个顶级接口

Map结构

数组＋链表＋红黑树

Map父接口

存储一对数据（Key+Value）

public interface Map{}

定义map对象时建议指定key和value对应的类型，key和value要求必须时复杂类型，不能采用int之类的简单类型

map接口中有一个内部接口Entry，每个Entry对象用于封装一对key/value，value允许修改，但是key不允许修改

map中所有存储的数据都将封装为Entry对象，一个key/value对对应一个Entry对象

方法

V put(K key,V value)//将对象存入到集合中，关联键值。key重复则覆盖原值

Object get(Object key)//根据键获取对应的值

int size()

Object get(Object key)//根据键获取对应的值

…

Map集合的实现类 HashMap

public class HashMap extends AbstractMap implements Map,Cloneable,Serializable

如果不指定泛型，则默认key-value的类型都是Obejct

具体的内部数据存储方式

transient Node[] table;//哈希表的本质就是一个数组，数组中的每一个元素称为一个桶，桶里存放的是一个key-value组成的链表或者红黑树

TreeMap Hashtable SortedMap接口 练习题×

输入一个链表，反转链表后，输出新链表的表头

public ListNode reverseList(ListNode head){
    if(head==null)
        return null;//判断链表是否为空，为空的直接返回null
    ListNode prev = null;//前一个结点
    ListNode next = null;//后一个结点
    while(head!=null){
        next = head.next;
        
    }
}

Tips

有关集合的学习：记接口 记接口中的方法 记实现类的区别

Collection接口	List接口	Set接口	Map接口
无序、无下标、元素可以重复	有序、有下标、元素可以重复	无序、无下标、元素不可重复	无序、无下标、键不可重复、值可重复