java基础—集合类

java集合框架包含两种类型的容器，一种是集合collection，另一种是图map。集合collection有三种子类型set，list，Queue。

set

set是一种无序且不包含重复元素的collection，set最多只有一个null

HashSet

HashSet是由哈希表实现，数据是无序的，只能放入一个null，其底层是hashMap，只使用了HashMap的key来存放数据。HashSet要求放入的对象必须实现hashcode方法，放入的对象是以hashcode码作为标识的，相同内容的String对象，hashcode相同，所以放入的内容不能相同，但同一个类的对象可以放入不同的实例。
HashSet中保证元素唯一的hashcode和equals方法进行判断。如果hashcode不同，则不用判断equals直接存在hashset中，如果hashcode相同，则需要用equals判断，相同则不存，不相同则存储。

TreeSet

TreeSet底层是自平衡的排序二叉树，可以保证快速检索指定节点。保证数据唯一性的方法是根据比较方法返回的结果是否为0，为0则相同，不加入TreeSet，不为0则为不同元素，进行存储，所以要求加入TreeSet的对象类要实现Comparable接口，否则会抛出异常。
TreeSet对元素的排序方式：
1）自然排序：元素本身具有排序功能，实现Comparable接口，重写compareTo方法
2）比较器排序：元素不具备排序功能，实现Comparator接口，覆盖compare方法
compareTo和compare方法
compareTo是java.lang.Comparable< T >接口中的方法，当需要对某个类的对象进行排序时，该类需要实现Comparable< T >接口，重写compareTo方法。
它强行将实现它的每一个接口进行整体排序------称为自然排序，实现此接口的对象列表和数组可以用Collections.sort和Arrays.sort进行自动排序。
只要实现了这个接口，其对象就拥有了排序能力，是一种内部排序方式，通过实现它唯一的方法compareTo。
compare是java.util.Comparator< T > 接口中的方法，实际上用的是待比较对象的compareTo方法，主要是针对一些没有比较能力的对象，为他们实现比较的功能，所以叫做比较器，是一种外部的东西，通过它定义比较的方式，再传到Collections.sort()和Arrays.sort()中对目标排序，而且通过自身的compare方法定义比较的内容和结果的升降序

      List<String> list = Arrays.asList("hello", "world", "welcome", "nihao");//按照字母排序Collections.sort(list);System.out.println(list);//按照字符串的长度.Collections.sort(list, (item1, item2) -> item1.length() - item2.length());System.out.println(list);//按照字符串的长度降序排序.Collections.sort(list, (item1, item2) -> item2.length() - item1.length());

list

list是有序的collection，能够精确控制每个元素插入的位置，用户能够使用索引（元素在list中的位置，类似数组中的下标）来访问list中的元素，类似于java的数组。
list允许有相同的元素，常用的实现类：Arraylist，linkedlist，Stack和vector

list的3种遍历方式

for(int i=0;i<list.size();i++){list.get(i);
}

for(String s:list){System.out.print(s);
}

Iterator<String> iter=list.iterator();
while(iter.hasNext()) String s=iter.next();

Iterator和ListIterator
Iterator是所有集合Collection类都可以使用的迭代器，ListIterator是专门为list设计的迭代器接口。ListIterator继承了Iterator接口。Iterator接口只支持hasNext(),next(),remove()3种操作，ListIterator支持更多操作。

ublic interface ListIterator<E> extends Iterator<E> {//继承自Iterator的接口boolean hasNext();         //后面是否有元素E next();                  //游标向后移动，取得后面的元素void remove();             //删除最后一个返回的元素//ListIterator新增的接口boolean hasPrevious();     //前面是否有元素E previous();              //游标往前移动，取得前面的元素int previousIndex();       //取得游标前的indexint nextIndex();           //取得游标后的indexvoid set(E e);             //将当前元素改设成evoid add(E e);             //增加一个元素
}

注意，一边遍历一边用Iterator和ListIterator做删除或增加的工作，不会影响list的结果。但如果不使用迭代器，而直接在遍历中对list进行增删会报错。Java容器有一种保护机制，能防止多个进程同时修改同一个容器的内容。遍历过程中，另一个进程对其容器对象进行修改操作会抛出ConcurrentModificationException。在遍历过程中都调用了checkForConmodification来判断当前arraylist是否同步。每次对容器对象修改时会执行一次modCount加一操作，遍历时把modCount传入，arraylist在checkForConmodification中验证modcount和expectedModCount是否一致。而是用迭代器进行remove等操作是允许的，因为其操作的不是list对象，而是Iterator对象。
Linkedlist查找元素较慢，一般使用ListIterator来进行查找。

ArrayList

ArrayList实现了可变大小的数组，允许所有元素包括null，底层采用动态数组的存储模式，遍历效率高，但arraylist是线程不安全的。
size,isEmpty,get,set方法运行时间为常数，add方法的开销为分摊的常数，添加n个元素需要O(n)时间，其他方法运行时间运行为线性。
每个arraylist实例都有一个容量capacity，用于存储元素的数组大小，这个容量可随着不断添加元素而自动增加。当插入大量元素时，可通过ensureCapacity方法来增加arraylist的容量，以提高插入效率。
arrayList的初始容量系统默认为10，每次按照1.5倍通过copyOf方式扩容。

ArrayList的浅拷贝和深拷贝

浅拷贝
ArrayList<Integer> list2=new ArrayList<>(l1);
list2.addAll();
ArrayList<Integer> list2=(ArrayList<Integer>)l1.clone()
Collections.copyOf(list2,list1);
深拷贝
1.需要对泛型类实现序列化

public static <T>List<T> depCopy(List<T> srcList){ByteArrayOutputStream byteOut=new ByteArrayOutputStream();try{ObjectOutputStream out=new ObjectOutputStream(byteOut);out.writeObject(srcList);ByteArrayInputStream byteIn=new ByteArrayInputStream(byteOut.toByteArray());ObjectInputStream in=new ObjectInputStream(byteIn);List<T> destList=(List<T>)in.readObject();return destList;}catch(IOException e){e.printStackTrace();}catch(ClassNotFoundException e){e.printStackTrace();}return null;
}

2.泛型类实现cloneable接口，重写clone方法,有限制，要先声明list保存的对象，对象中有list集合不行

public static List<Address> depCopy(List<Address> addresses){List<Address> destAddress=new ArrayList<>();for(Address ad:addresses){destAddress.add((Address)ad.clone());}
}

LinkedList

LinkedList底层是基于双向循环链表，且头节点不存放数据。
LinkedList是继承AbstractSequentialList的双向链表，可以被当做堆栈，队列或双端队列进行操作。
LinkedList实现了list接口，能进行队列操作。
LinkedList实现Deque接口，能将其当做双端队列使用。
LinkedList实现了Cloneable接口，覆盖了函数clone(),能克隆。
LinkedList实现了java.io.Serializable接口，所以linkedList支持序列化，能通过序列化去传输。
LinkedList是非同步的。

LinkedList和ArrayList的区别

ArrayList实现了基于动态数组的数据结构，LinkedList实现了基于链表的数据结构。
对于随机访问，ArrayList优于LinkedList，LinkedList要移动指针
对于新增和删除操作，LinkedList优于ArrayList，因为ArrayList要移动数据。

Vector

vector是通过Sychronized实现线程安全的动态数组。

Stack

Stack继承Vector。实现后进先出的堆栈，Stack提供额外5个方法，使得vector可以当做堆栈使用。基本的push和pop方法，peek(),empty(),search()检测一个元素在堆栈中的位置。

栈和队列

栈与队列的相同点：
1.都是线性结构。
2.插入操作都是限定在表尾进行。
3.都可以通过顺序结构和链式结构实现。、
4.插入与删除的时间复杂度都是O（1），在空间复杂度上两者也一样。
5.多链栈和多链队列的管理模式可以相同。
栈与队列的不同点：
1.删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。
2.应用场景不同；常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。
3.顺序栈能够实现多栈空间共享，而顺序队列不能。
栈共享空间的思想是：让一个栈的栈底为数组的开始端，即下标为0处，另一个栈的栈底为数组的末端，即下标为数组长度的n-1出，这样，两个栈如果增加元素，就是两端点向中间延伸。当两个栈见面之时，也就是两个指针相差1时，即top1 + 1 == top2时为栈满。

Queue

Queue模拟队列这种数据结构，遵循先进先出原则
（1）添加元素
boolean add(E e); boolean offer(E e);
//这两个方法都在尾部添加一个值为e的元素。如果队列没有满，将给定的元素添加到这个队列的尾部并返回true。不同的是如果队列满了，add方法会抛出一个IllegalStateException异常，而offer方法返回false。
（2）删除并返回元素
E remove(); E poll();
这两个方法删除队列头部的元素。如果队列非空，这两个方法删除头部元素后并返回这个元素。不同的是如果队列是空的，remove方法抛出一个NoSuchElementException异常，而poll方法返回false。
（3） 获得头部元素
E element(); E peek();
这两个方法都会返回头部的元素，而都不删除头部元素。不同的是如果队列是空的，element方法抛出一个NoSuchElementException异常，而peek方法返回null。

Deque双端列表

(1）添加元素
void addFirst(E e); void addLast(E e); boolean offerFirst(E e); boolean offerLast(E e);
这四个方法在头部或尾部添加给定的元素。如果队列满了，前两个方法将抛出一个IllegalStateException异常，后两个方法返回false。
（2）删除并返回元素
E removeFirst(); E removeLast(); E pollFirst(); E pollLast();
这四个方法删除头部或尾部的元素并返回。如果队列为空，前两个方法将抛出一个NoSuchElementException异常，后两个方法返回null。
（3）返回但不删除元素
E getFirst(); E getLast(); E peekFirst(); E peekLast();
这四个方法返回头部或尾部的元素，但不删除。如果队列为空，前两个方法将抛出一个NoSuchElementException异常，后两个方法返回null。

PriorityQueue

PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示（任意一个非叶子节点的权值，都不大于其左右子节点的权值）
大顶堆

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(DEFAULT_INITIAL_CAPACITY ,new Comparator<Integer>(){@Overridepublic int compare(Integer i1 , Integer i2){return i2 - i1;
}
});

LinkedList

LinkedList同时实现了Deque, Queue, List三个接口

map

Map没有继承Collection接口，Map提供key到value的映射，一个map不能含有相同的key，每个key只能映射一个value。

HashMap

JDK1.7：数组+链表
JDK1.8：数组+链表+红黑树：链表长度>=8，链表转为红黑树。

HashTable

HashTable继承Dictionary，实现了Map，Cloneable，Serializable接口，实现了key-value映射表，任何非空对象都可作为key和value。
HashTable采用"拉链法"实现哈希表，它定义了几个重要的参数：table、count、threshold、loadFactor、modCount。
table：为一个Entry[]数组类型，Entry代表了“拉链”的节点，每一个Entry代表了一个键值对，哈希表的"key-value键值对"都是存储在Entry数组中的。

count：HashTable的大小，注意这个大小并不是HashTable的容器大小，而是他所包含Entry键值对的数量。

threshold：Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值=“容量*加载因子”。

loadFactor：加载因子。

modCount：用来实现“fail-fast”机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常。
默认构造函数，容量为11，加载因子为0.75。.用指定初始容量和指定加载因子构造一个新的空哈希表。其中initHashSeedAsNeeded方法用于初始化hashSeed参数，其中hashSeed用于计算key的hash值，它与key的hashCode进行按位异或运算。这个hashSeed是一个与实例相关的随机值，主要用于解决hash冲突。
HashTable是同步的，所有的读写等操作都进行了锁（synchronized）保护。
1. put方法
先获取synchronized锁。
put方法不允许null值，如果发现是null，则直接抛出异常。
计算key的哈希值和index
遍历对应位置的链表，如果发现已经存在相同的hash和key，则更新value，并返回旧值。
如果不存在相同的key的Entry节点，则调用addEntry方法增加节点。
addEntry方法中，如果需要则进行扩容，之后添加新节点到链表头部。
2. get方法
先获取synchronized锁。
计算key的哈希值和index。
在对应位置的链表中寻找具有相同hash和key的节点，返回节点的value。
如果遍历结束都没有找到节点，则返回null。
3.rehash扩容方法
数组长度增加一倍（如果超过上限，则设置成上限值）。
更新哈希表的扩容门限值。
遍历旧表中的节点，计算在新表中的index，插入到对应位置链表的头部。
4.remove方法
先获取synchronized锁。
计算key的哈希值和index。
遍历对应位置的链表，寻找待删除节点，如果存在，用e表示待删除节点，pre表示前驱节点。如果不存在，返回null。
更新前驱节点的next，指向e的next。返回待删除节点的value值。

TreeMap

TreeMap继承AbstractMap，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制。

ConcurrentHashMap

1.7ConcurrentHashMap
底层是一个segment数组。segment类，其属性有一个hashEntry数组。
并发级别默认16指segment的大小
Capacity默认16用于计算hashEntry的大小
每个segment里hashEntry数组的大小最小是2，也是2的整数幂
底层是UNSAFE直接操作
先计算key的hash值得到segment下标，访问该位置，从UNSAFE类中获取该位置的segment对象，如果不存在就用UNSAFE的CAS新建一个，保证线程安全

其实就是将HashMap分为多个小HashMap,每个Segment元素维护一个小HashMap,目的是锁分离，本来实现同步，直接可以是对整个HashMap加锁，但是加锁粒度太大，影响并发性能，所以变换成此结构，仅仅对Segment元素加锁，降低锁粒度，提高并发性能。
扩容：只针对segment内部，segment之间不相关
put操作
对于插入操作，需要两次Hash映射去定位数据存储位置
首先通过第一次hash过程，定位Segment位置，然后通过第二次hash过程定位HashEntry位置
Segment继承ReentrantLock,在数据插入指定HashEntry过程的时候会尝试调用ReentrantLock的tryLock方法获取锁，如果获取成功就直接插入相应位置，如果有线程获取该Segment的锁，当前线程就会以自旋方式去继续调用tryLock方法去获取锁，超过指定次数就挂起，等待唤醒。
Trylock：true，false，不会阻塞
Lock：false 阻塞

get操作
也是两次Hash映射，相对于put操作，少了加锁过程
ConcurrentHashMap为什么读的时候不加锁？
ConcurrentHashMap是分段并发分段进行读取数据的。
Segment 里面有一个Count 字段，用来表示当前Segment中元素的个数 它的类型是volatile变量。所有的操作到最后都会在最后一部更新count 这个变量，由于volatile变量 happer-before的特性。导致get 方法能够几乎准确的获取最新的结构更新。

size操作
size操作就是计算ConcurrentHashMap的大小，有两种方案
给每个Segment都加上锁(相当于给整个Map加上锁)，然后计算size返回
不加锁的模式，尝试多次计算ConcurrentHashMap的size,最多三次，比较前后计算的结果，结果一致就认为当前没有元素加入，计算结果是准确的。(查看计算出size的前后modCount的数值有没有发生变化，modCount的值用于记录元素变化的操作。如put，remove，clear)
1.8 ConcurrentHashMap
jdk1.8ConcurrentHashMap是数组+链表，或者数组+红黑树结构,并发控制使用，只有一个Node数组通过Synchronized关键字和CAS操作完成并发控制。扩容时，synchronized对头结点加锁，加完锁判断是否是之前的那个节点
binCount：链表的节点数
树化：TreeBin对象，里面有个红黑树
为什么要生成treeBin?如果依然是TreeNode对象，有可能红黑树的根节点会发生变化，但线程的锁锁住的是根节点，所以用TreeBin对象封装一颗红黑树，这样里面怎么变
putValue函数，首先调用spread函数，计算hash值，之后进入一个自旋循环过程，直到插入或替换成功，才会返回。如果table未被初始化，则调用initTable进行初始化。之后判断hash映射的位置是否为null,如果为null,直接通过CAS自旋操作，插入元素成功，则直接返回，如果映射的位置值为MOVED(-1),则直接去协助扩容，排除以上条件后，尝试对链头Node节点f加锁，加锁成功后，链表通过尾插遍历，进行插入或替换。红黑树通过查询遍历，进行插入或替换。之后如果当前链表节点数量大于阈值，则调用treeifyBin函数，转换为红黑树最后通过调用addCount,执行CAS操作，更新数组大小，并且判断是否需要进行扩容

HashMap，HashTable和concurrentHashMap区别

1.继承不同，HashMap继承AbstractMap，Hashtable继承Dictionary，ConcurrentHashMap继承AbstractMap，也实现了concurrentMap接口。
2.HashMap非安全，HashTable和concurrentHashMap实现同步方法，concurrentHashMap降低锁粒度。
3.key-value：concurrentHashMap和hashtable不允许value，key为null，HashMap允许唯一key为null，多个value为null
4.哈希算法：HashMap和1.8的concurrentHashMap的算法一致是使用key的hashcode进行高16位和低16位异或，再取模长度，hashtable直接对key的hashcode值取模。
5.扩容，concurrentHashMap和hashmap的扩容和初始容量一致，扩两倍，初始为16，hashtable初始为11，扩容2倍+1
6.失败机制，concurrentHashMap支持安全失败，hashtable和hashmap支持快速失败
7.concurrentHashMap和hashtable支持contains，hashmap不支持。
8.concurrentHashMap支持Enumeration迭代。