基础 - Java中的集合 - 《Java 技术文档》

List与Set的区别
ArrayList与LinkList的区别
双端队列Deque的使用
Map之间的区别
Set中最常用的集合
- HashSet
线程安全与不安全的集合
集合的遍历
- List 的遍历
针对ArrayList的操作
参考资料

集合分为：List，Set，Map三种，其中List与Set是继承自Collection，而Map不是。
集合可以存储任何类型的值。
```
List<List<Integer>> list;
List<String> list; 
Map<ListNode,ListNode> map;
```
List与Set的区别
List中的元素有存放顺序，并且可以存放重复元素，检索效率高，插入删除效率低；
Set没有存放顺序，而且不可以存放重复元素，后来的元素会把前面重复的元素替换掉，检索效率低，插入删除效率高。（Set存储位置是由它的HashCode码决定的，所以它存储的对象必须有equals()方法，而且Set遍历只能用迭代，因为它没有下标。）Set不是键值对的形式。
Set集合会让两个对象，先调用自己的 hashCode() 方法得到彼此的哈希值(所谓的内存地址)然后比较两个对象的哈希值是否相同，如果不相同则直接认为两个对象不重复。如果哈希值相同，会继续让两个对象进行 equals 比较内容是否相同，如果相同认为真的重复了，如果不相同认为不重复。
ArrayList与LinkList的区别
ArrayList 基于数组实现的，可以存储任何类型的数据，但数据容量有限制，超出限制时会 扩增50%容量，把原来的数组复制到另一个内存空间更大的数组中，查找元素效率高。ArrayList是一个简单的数据结构，因超出容量会自动扩容，可认为它是常说的动态数组。线程是非安全的。
LinkedList 以双向链表实现，链表无容量限制，但双向链表本身使用了更多空间，每插入一个元素都要构造一个额外的Node对象，也需要额外的链表指针操作。允许元素为null，线程不安全。
ArrayList 和 LinkedList 都实现了List接口，LinkedList还额外实现了Deque接口。

综合比较结论：
LinkList在增、删数据效率方面要优于ArrayList，而ArrayList在改和查方面效率要远超LinkList。
ArrayList查询直接根据下标查询，而LinkedList需要遍历才能查到元素。增加时直接增加放在队尾，指定位置增加时，数组的元素会往后移动，而链表则需要进行先遍历到指定的位置。
但是，虽然综合比较之下LinkedList的优势要比ArrayList要好，但是在java中，我们用的比较多的确实ArrayList，因为我们的业务通常是对数据的改和查用的比较多。
一般情况下，存储相同多的数据，数组占用的内存较少，而链表还需要存储前驱和后继，需要更多的内存。

双端队列Deque的使用

在有需要用到栈功能的时候，都是通过使用Stack接口完成的，Java Doc里建议用Deque替代Stack接口完成栈的功能

Stack<T> stack = new Stack<>()

Deque是继承自Queue，而Stack是继承自Vector。
Java中的Deuqe，即“double ended queue”的缩写，是Java中的双端队列集合类型，它集成自Deque，完全具备普通队列FIFO的功能，同时它也具备了Stack的LIFO功能，并且保留了push和pop函数，所以使用起来应该是一点障碍都没有。
Deque可以由ArrayDeuqe或者LinkedList实现，它们两者使用的区别以及优劣也就是数组和链表的区别。

ArrayDeque

ArrayDeque是Deque接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque可以作为栈来使用，效率要高于 Stack。ArrayDeque也可以作为队列来使用，效率相较于基于双向链表的LinkedList也要更好一些。注意，ArrayDeque不支持为null的元素。

LinkedList

LinkedList与ArrayList一样实现List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List 接口链表的实现。基于链表实现的方式使得 LinkedList 在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。LinkedList实现所有可选的列表操作，并允许所有的元素包括null。除了实现List接口外，LinkedList类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。同时，与 ArrayList 一样此实现不是同步的。

Deque 方法总结

push()                              等价于addFirst()
pop()                               等价于removeFirst()
add()                               等价于addLast()
contains(Object o)                  是否包含某一个元素
element()                           检索首元素,不删除
getFirst()                          检索，但不删除，这个deque的第一个元素。
getLast()                           检索，但不删除，这个deque的最后一个元素。
offer(E e)                          在队列尾添加元素
offerFirst(E e)                     在队列前添加元素
offerLast(E e)                      在队列尾添加元素
peek()                              检索首元素,不删除
peekFirst()                         检索首元素,不删除
peekLast()                          检索，但不删除，这个deque的最后一个元素。
poll()                              检索并删除首元素
pollFirst()                         检索并删除首元素
pollLast()                          检索并删除尾元素
remove()                            删除首元素
remove(Object o)                    从此deque中删除指定元素的第一个出现。
removeFirst()                       检索并删除此deque的第一个元素。
removeFirstOccurrence(Object o)     从此deque中删除指定元素的第一个出现。
removeLast()                        检索并删除此deque的最后一个元素。
removeLastOccurrence(Object o)      从此deque中删除指定元素的最后一次出现。
size()                              返回此deque中的元素数。

注意：
poll()是队列数据结构实现类的方法，从队首获取元素，同时获取的这个元素将从原队列删除；
pop() 是栈结构的实现类的方法，表示返回栈顶的元素，同时该元素从栈中删除，当栈中没有元素时，调用该方法会发生异常
两个函数的代码实现是基本一致的，如果一定要说区别那么就是当头结点为空的时候，两个函数的处理方式不同：poll()选择返回null，pop()选择抛出异常。

Map之间的区别

equals 方法

JAVA当中所有的类都是继承于Object这个超类的，在Object类中定义了一个equals的方法，equals的源码是这样写的：

public boolean equals(Object obj) {
    //this - s1
    //obj - s2
    return (this == obj);   //引用数据类型：当他们用（==）进行比较的时候，比较的是他们在内存中的存放地址（确切的说，是堆内存地址）。
}

可以看到，这个方法的初始默认行为是比较对象的内存地址值，一般来说，意义不大。所以，在一些类库当中这个方法被重写了，如String、Integer、Date。在这些类当中equals有其自身的实现（一般都是用来比较对象的成员变量值是否相同），而不再是比较类在堆内存中的存放地址了。
所以说，对于复合数据类型之间进行equals比较，在没有覆写equals方法的情况下，他们之间的比较还是内存中的存放位置的地址值，跟双等号（==）的结果相同；如果被复写，按照复写的要求来。

Hashcode 的作用

HashMap 的添加、获取时需要通过 key 进行 hash()得到 hashCode ，然后计算下标 ( n-1 & hash)，从而获得要找的同的位置。当发生冲突（碰撞）时，利用 key.equals() 方法去链表或树中去查找对应的节点。

Hash

Hash是散列的意思，就是把任意长度的输入，通过散列算法变换成固定长度的输出，该输出就是散列值。关于散列值，有以下几个关键结论：

如果散列表中存在和散列原始输入K相等的记录，那么K必定在f(K)的存储位置上
不同关键字经过散列算法变换后可能得到同一个散列地址，这种现象称为碰撞
如果两个Hash值不同（前提是同一Hash算法），那么这两个Hash值对应的原始输入必定不同

HashCode
HashCode的存在主要是为了查找的快捷性，HashCode是用来在散列存储结构中确定对象的存储地址的
如果两个对象equals相等，那么这两个对象的HashCode一定也相同
如果对象的equals方法被重写，那么对象的HashCode方法也尽量重写
如果两个对象的HashCode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置
总结

hashCode() 在散列表中才有用，在其它情况下没用
哈希值冲突了场景，hashCode相等，但equals不等 (equals就是内存地址，hashcode只不过是内存地址的表示)
hashcode：计算键的hashcode作为存储键信息的数组下标用于查找键对象的存储位置
equals：HashMap使用equals()判断当前的键是否与表中存在的键相同。
- 如果两对象equals()是true,那么它们的hashCode()值一定相等，
- 如果两对象的hashCode()值相等，它们的equals不一定相等（hash冲突啦）
- 注：Hash冲突的四种解决办法
  HashMap
  
  数组
  数组存储区间连续，占用内存比较严重，空间复杂度很大。但数组的二分查找时间复杂度小，为O(1)；
  数组的特点是：寻址容易，插入和删除困难；
  链表
  链表存储区间离散，占用内存比较宽松，空间复杂度很小，但时间复杂度很大，达O（N）。
  链表的特点是：寻址困难，插入和删除容易。
  Set中最常用的集合
  HashSet
  HashSet是使用Hash表实现的，集合里面的元素是无序得，可以有null值，但是不能有重复元素。
  HashSet不是key value结构，仅仅是存储不重复的元素，相当于简化版的HashMap，只是包含HashMap中的key而已
  HashSet内部就是使用HashMap实现，只不过HashSet里面的HashMap所有的value都是同一个Object而已，因此HashSet也是非线程安全的
  特点：因为相同的元素具有相同的hashCode，所以不能有重复元素
  线程安全与不安全的集合
  线程安全就是多线程访问时，采用了加锁机制，当一个线程访问该类的某个数据时，进行保护，其他线程不能进行访问直到该线程读取完，其他线程才可使用。不会出现数据不一致或者数据污染。
  线程不安全就是不提供数据访问保护，有可能出现多个线程先后更改数据造成所得到的数据是脏数据。
  比如 List 接口下面有两个实现，一个是ArrayList，另外一个是vector。从源码的角度来看，因为Vector的方法前加了synchronized 关键字，也就是同步的意思，sun公司希望Vector是线程安全的，而希望arraylist是高效的，缺点就是另外的优点。
  ArrayList为什么线程不安全
  一个 ArrayList ，在添加一个元素的时候，它可能会有两步来完成：1. 在 Items[Size] 的位置存放此元素； 2. 增大 Size 的值。
  在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1；
  而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 （注意哦，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。那好，现在我们来看看 ArrayList 的情况，元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这就是“线程不安全”了。
  线程安全的工作原理
  主要依据为JMM原理，jvm中有一个 main memory 对象，每一个线程也有自己的 working memory，一个线程对于一个变量variable进行操作的时候，都需要在自己的 working memory 里创建一个copy,操作完之后再写入main memory。当多个线程操作同一个变量 variable，就可能出现不可预知的结果。
  而用 synchronized 的关键是建立一个监控monitor（synchronized加锁原理），这个monitor可以是要修改的变量，也可以是其他自己认为合适的对象(方法)，然后通过给这个monitor加锁来实现线程安全，每个线程在获得这个锁之后，要执行完加载load到working memory 到 use && 指派assign 到存储store 再到 main memory的过程。才会释放它得到的锁。这样就实现了所谓的线程安全。
  安全与不安全的类
  Java中提供了很多的集合类，比如ArrayList、LinkedList、HashMap…等，集合类内部采用了诸多的方式进行存储这些数据，目的是能够让增删改查某些操作更快一些，不同的存储方式被称作数据结构。因为这些不同的存储方式，导致了增删改查效率的不同。
  数据结构：容器存储数据，管理数据的一种方式，数据结构常用的包括数组、链表、哈希表、树。

ArrayList主要是用数组来存储元素，LinkedList主要是用链表来存储元素，HashMap的底层实现主要是借助数组+链表+红黑树来实现。
Vector、HashTable、Properties 等集合类效率比较低但都是线程安全的。包java.util.concurrent下包含了大量线程安全的集合类，效率上有较大提升。
- CopyOnWriteArrayList 线程安全，适用于读转写操作，每次操作时会复制一个新的List，在新的List上进行写操作，操作完成之后，再将原来的List指向新的List。线程安全地遍历，因为如果另外一个线程在遍历的时候修改List的话，实际上会拷贝出一个新的List上修改，而不影响当前正在被遍历的List。
- ConcurrentLinkedQueue 线程安全，是一个基于链接节点的、无界的、线程安全的队列。此队列按照 FIFO（先进先出）原则对元素进行排序，队列的头部是队列中时间最长的元素。队列的尾部是队列中时间最短的元素。新的元素插入到队列的尾部，队列检索操作从队列头部获得元素。当许多线程共享访问一个公共 collection 时，ConcurrentLinkedQueue 是一个恰当的选择，此队列不允许 null 元素。
- ConcurrentHashMap 线程安全。 jdk1.7采用分段锁机制对整个桶数组进行了分割分段（Segment），segment继承自ReetrantLock，每一把锁只锁容器中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提供了并发访问率；jdk1.8 采用CAS + synchronized，是对hashtable进行优化，将锁细粒化到每个table的每个元素，来提升并发性能。jdk1.8 彻底放弃segment 而采用node，不再使用分段锁。 利用 CAS 尝试写入，失败则自旋保证成功,利用 synchronized 锁写入数据。
ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等都是线程不安全的。（线程不安全是指：当多个线程访问同一个集合或Map时，如果有超过一个线程修改了ArrayList集合，则程序必须手动保证该集合的同步性。）
集合的遍历
List 的遍历

for循环遍历，基于计数器
遍历者自己在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后，停止。主要就是需要按元素的位置来读取元素。
因为是基于元素的位置，按位置读取。所以我们可以知道，对于顺序存储，因为读取特定位置元素的平均时间复杂度是O(1)，所以遍历整个集合的平均时间复杂度为O(n)。而对于链式存储，因为读取特定位置元素的平均时间复杂度是O(n)，所以遍历整个集合的平均时间复杂度为O(n2)（n的平方）（先知道位置，再循环到相同位置）。
```
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
```
迭代器遍历
Iterator本来是OO的一个设计模式，主要目的就是屏蔽不同数据集合的特点，统一遍历集合的接口。Java作为一个OO语言，自然也在Collections中支持了Iterator模式。
那么对于RandomAccess类型的集合来讲，没有太多意义，反而由于一些额外的操做，还会增长额外的运行时间。可是对于Sequential Access的集合来讲，就有很重大的意义了，由于Iterator内部维护了当前遍历的位置，因此每次遍历，读取下一个位置并不须要从集合的第一个元素开始查找，只要把指针向后移一位就好了，这样一来，遍历整个集合的时间复杂度就下降为O(n)；
```
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
iterator.next();
}
```
foreach循环遍历
屏蔽了显式声明的Iterator和计数器。分析Java字节码可知，foreach内部实现原理，也是经过Iterator实现的，只不过这个Iterator是Java编译器帮咱们生成的，因此咱们不须要再手动去编写。可是由于每次都要作类型转换检查，因此花费的时间比Iterator略长。时间复杂度和Iterator同样。
优点：代码简洁，不易出错。
缺点：只能做简单的遍历，不能在遍历过程中操作（删除、替换）数据集合。 ```java for (ElementType element : list) {

}

<a name="d6BWe"></a>
### Map 的遍历
```java
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// keySet() 遍历
//遍历map中的键
for (Integer key : map.keySet()) {
    System.out.println("Key = " + key);
}
//遍历map中的值
for (Integer value : map.values()) {
    System.out.println("Value = " + value);
}
 // hashmap 迭代器 遍历
  Iterator it = map.entrySet().iterator();
  while (it.hasNext()) {
       Map.Entry entry = (Map.Entry) it.next();
       Object key = entry.getKey();
       Object value = entry.getValue();
       System.out.println("key=" + key + " value=" + value);
  }

针对ArrayList的操作

List 包含的方法

add(Object element)：向列表的尾部添加指定的元素。
size()：返回列表中的元素个数。
get(int index)：返回列表中指定位置的元素，index从0开始。
add(int index, Object element)：在列表的指定位置插入指定元素。
set(int i, Object element)：将索引i位置元素替换为元素element并返回被替换的元素。
clear()：从列表中移除所有元素。
isEmpty()：判断列表是否包含元素，不包含元素则返回 true，否则返回false。
contains(Object o)：如果列表包含指定的元素，则返回 true。
remove(int index)：移除列表中指定位置的元素，并返回被删元素。
remove(Object o)：移除集合中第一次出现的指定元素，移除成功返回true，否则返回false。
iterator()：返回按适当顺序在列表的元素上进行迭代的迭代器。

排序 ```java Collections.sort(list); //针对一个ArrayList内部的数据排序

如果想自定义排序方式则需要有类来实现Comparator接口并重写compare方法调用sort方法时将ArrayList对象与实现Commparator接口的类的对象作为参数

— 调用 Collections.sort(list, new SortByAge());

— 实现接口

class SortByAge implements Comparator { public int compare(Object o1, Object o2) { Student s1 = (Student) o1; Student s2 = (Student) o2; return s1.getAge().compareTo(s2.getAge()); } }

注：compareTo方法比较字符串，但是也可以比较数字（数字为String类型）
原理：先比较字符串长度，再逐一转成char类型去比较字符串里的每一个字符。


-  **遍历**

— for循环的遍历方式 for (int i = 0; i < lists.size(); i++) { System.out.print(lists.get(i)); }

— foreach的遍历方式 for (Integer list : lists) { System.out.print(list); }

— Iterator的遍历方式 for (Iterator list = lists.iterator(); list.hasNext();) { System.out.print(list.next()); }


-  **删除** 
```java
lists.remove(6);        //指定删除
/** List 删除元素的逻辑是将目标元素之后的元素往前移一个索引位置，
最后一个元素置为 null，同时 size - 1。
遍历删除时，操作不当会导致异常，
原因：ArrayList 中两个 remove() 方法都对 modCount 进行了自增，
那么我们在用迭代器迭代的时候，若是删除末尾 的元素，
则会造成 modCount 和 expectedModCount 的不一致导致异常抛出。
Iterator 迭代遍历删除是最安全的方法。**/
// 示例：
public static void remove(List list, String target){
      Iterator iter = list.iterator();
        while (iter.hasNext()) {
           String item = iter.next();
           if (item.equals(target)) {
            iter.remove();
        }
      }
      System.out.println(list);
}

去重（参考6）

利用HashSet（不保证元素顺序一致）
利用LinkedHashSet (去重后顺序一致)，继承的父类HashSet
参考资料

Java中的集合

List与Set的区别

ArrayList与LinkList的区别

双端队列Deque的使用

ArrayDeque

LinkedList

Deque 方法总结

Map之间的区别

equals 方法

Hashcode 的作用

Hash

HashCode

总结

HashMap

Set中最常用的集合

HashSet

线程安全与不安全的集合

ArrayList为什么线程不安全

线程安全的工作原理

安全与不安全的类

集合的遍历

List 的遍历

针对ArrayList的操作

参考资料