集合

什么是集合

集合类存放于java.util包中。集合类型主要有3种: set(集) 、list(列表) 和map(映射)。集合存放的都是对象的引用，而非对象本身。所以我们称集合中的对象就是集合中对象的引用。 简单来讲:集合就是一个放数据的容器，准确的说是放数据对象弓|用的容器。

基本方法：

int size() 获取元素个数

boolean isEmpty0 是否个数为0

boolean contains(Object element) 是否包含指元索

boolean add(E element) 添加元素，成功时返回true

boolean remove(Object element) 删除元素，成功时返回true

Iterator iterator() 获取迭代器

boolean addAl(Collection< extends E> ) 添加集合c中所有的元素到本集合中，如果集合有改变就返回true

boolean removeAll(Collection<> ) 删除本集合中和c集合中一致的元素，如果集合有改变就返回true

boolean retainAll(Collection<> ) 保留本集合中C集合中两者共有的，如果集合有改变就返回true

void clear()删除所有元素

●Object[] toArray0 ●返回一个包含集合中所有元素的数组 ● T toArray(TI a) ●返回一个包含集合中所有元素的数组，运行时根据集合元愫的类型指定数组的类型

List:有可重复集合; Set:无不重复集合; Map:键值对存储，key必须唯一，只有一个key可以为null,value可以有多 个null,使用key来搜索value;

1.LinkedList

LinkedList也是List接口的实现类,和ArrayList功能类似，但LinkedList新增几个功能 ，如addFirst(),addLast(),getFirst(),getLast()等

数据结构：双向链表

链式存储，在内存中不是连续存储的，每个元素存储包括三部分，前一个元素的内存地址、数据部分、后一个元素内存地址，因此在进行元素的新增和删除时效率比较高，但查询时比较慢 链式存储方式与数组的连续存储方式相比，其实对内存的利用率更高

2.HashSet

HashSet是Set接口的实现类，最大的特点就是内部元素无序、并且不能重复（重复添加的话会默认覆盖上一个相同的元素），默认初始容量16

HashSet数据结构：哈希表（数组+链表）

HashSet存储原理：

1.Set set=new HashSet(); 2.set.add(object);

存储过程为: 定义x=object.hashCode,得到obj对象的哈希码x，再对x进行hash散列运算，对数组长度进行求余，假如长度为20，则返回一个0-19之间的值，然后这个值就是存在HashSet数组中的下标。如果下标位置没有对象，则把object加到该位置；如果已有对象，则用equals判断两对象是否相等，相等则舍弃object，不相等，则把object以链表的方式加在该对象下面

原则1：让equals相等的对象返回相同的hashCode（为了过滤掉相等的元素） 原则2：尽量保证equals不相同的对象返回不同的hashCode（为了添加不同的元素） HashSet的add()方法底层使用的是HashMap的存储方式，看源码可以知道

add()方法

HashSet检查重复 当HashSet添加元素时，HashSet会先计算元素的HashCode值是否在集合中已存在,若不存在，则直接加入，若HashCode值已存在, 则使用equals方法判断HashCode相同的两个元素的值是否相等，如果值相等则元素加入失败,也就是不能有复元素; ①如果两个对象相等，则HashCode- 定相等 ②两个对象相等，则equals方法返回为true ③如果两个对象的HashCode相等，,对象不一定相等

3.HashMap

map是存放键值对的。 HashMap是Map接口的实现类，也是采用了hash算法。

其实向HashSet中放值，就是向HashMap中放值

Key不可以一样，如果key一样，在内存中存储的位置相同，后一个会把前一个key覆盖，value可以一样key和value均可以为null，HashMap的存储键的过程和HashSet一样，不过HashMap在根据key获取value时的原理如下：

前面也是根据对象获取哈希码，进行哈希运算求下标（哈希码%容量），如果下标位置只有一对key-value,就直接取得value，如果有多个key-value键值对，然后再根据key获取value。

HashMap的数据结构 数组+单链表（数组中的每个元素都是单链表的头节点） 使用链表的原因是解决哈希冲突的（即不同的key映射到了数组的同一位置处，就将其放入单链表中）

HashMap是线程不安全的： HashTable是HashMap的兄弟。HashMap跟HashTable用法基本一样

它们两个区别就是HashTable是线程安全的

线程安全： 10个人同时操作HashTable，只有一个人操作，剩下的九个人等待。操作完毕后，剩下的9个人中的一个人操作HashTable,剩下8个人等待

线程不安全： 10个人同时操作

例子： 第一个人拿原始值， 如10 第二个人修改原始值 10-》20

如果二个人修改了原始值，会造成后面的人再拿数据时，会拿到第二个人修改后的数据（脏数据）

HashMap与Hashtable

线程安全，HashMap是线程不安全的，Hashtable是线程安全的Hashtable的每个方法都被synchronized修饰，每个方法都是同步的，但是效率低下，因此HashMap是效率比较高,但是线程不安全，Hashtable目前已被淘汰，可使用ConcurrentHashMap替代它;

HashMap可以有nul键, 但是在Hashtable不能有nul做为键，否则会报NPE即NullPointException空指针异常;

初始容量与扩容大小，创建时如果不指定容量大小，则会使用默认大小，Hashtable默认初始容量 大小为11,扩容为2n+1,HashMap默认初始容量大小为16，扩容为2n,若给定初始容量大小Hashtable则直接使用给定的值,HashMap将其扩充为2的幂次方大 小，也就是HashMap总是使用2的幂作为哈希表的大小;

底层数据结构, JDK1.8之 后HashMap中当链表的长度大于阈值(默认8) ，则将链表转化为红黑树，以减少搜索时间;

HashMap底层实现： JDK1.8之前使用的是数组加链表结合在-起的链表散列， HashMap通过key的HashCode经过扰动函数处理过后得到Hash值,然后通过(n-1)&hash判断当前元素存放的位置(这里的n指的是数组的长度)，如果当前位置存在元素，就判断该元素与添加的元素的hash值以及key是否相同，如果相同，直接覆盖，不相同就通过拉链法解决冲突。扰动函数指HashMap的hash方法， 使用hash方法是为了防止实现比较差的hashCode0方法为了减少碰撞;

HashMap的长度： 为了能让HashMap存取高效,尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了, Hash 值的范围值-2147483648到2147483647.前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难 出现碰撞的。

但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。之前还要先做对数组的长度取模运算,得到 的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“(n- 1) & hash"。(n代表数组长度) 。这也就解 释了HashMap的长度为什么是2的幂次方。

这个算法应该如何设计呢?

我们首先可能会想到采用%取余的操作来实现。但是，重点釕:”取余(%)操作中如果除数是2的幂次则等价于与其除数减- 的与(&)操作(也就是说hash%length= =hash&(length-1)的前提是length是2的n次方; )。”.并且采用二进制位操作&,相对于%能够提高运算效率，这就解释了HashMap的长度为什么是2的幂次方。

因为n永远是2的次幂，所以n-1通过二进制表示，永远都是尾端以连续1的形式表示(00001111, 0000011)当(n- 1)和hash做与运算时，会保留hash中后x位的1, 例如00001111 & 10000011 = 00000011 这样做有2个好处：

①&运算速度快,至少比%取模运算块 ②能保证索引值肯定在capacity中，不会超出数组长度 ③(n- 1) & hash,当n为2次幂时，会满足一个公式: (n- 1) & hash= hash % n

4.HashTable

HashTable和HashMap功能类似，都是用来保存键值对，但两者之间又有区别

区别：

HashTable中不允许保存null的，而HashMap可以保存空的null和valueHashTable线程安全，HashMap线程不安全Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map接口

5.Collection

Collection接口的子接口:List (序列) ,Queue,Set接口集合中不能存放基本数据类型数据，只能存放对象的引用;collection是list和set接口的父接口，是一个集合接口

6.Collections

Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类 常用方法如下：

Collections.sort()

Collections.reverse()

Collections.binarySearch()方法

为二分法查找，所以数组必须是有序的或者是用sort()方法排序之后的binarySearch(Object[], Object key) 方法的object[]参数是要查找的数组，key参数为要查找的key值。

Collection和Collections有什么区别?

Collection是集合体系的最顶层,包含了集合体系的共性， Collections是一个工具类，方法都是用于操作Collection。

7.ArrayList

ArrayList是List接口的实现类，一种大小可变数组，随着元素的增多，容量会自动扩充，默认初始容量值是10，也可以自己指定初始容量

采用的数据结构：数组 （线性表：数组、链表、队列、栈 非线性表：二叉树、堆、图等）

ArrayList优点：

查询速度快 ArrayList缺点： 新增和删除元素比较慢

查询速度快的原因：

ArrayList底层是数组实现的，根据下标查询，不需要比较，查询方式为，首地址+（元素长度＊下标），基于这个位置读取相应的字节数，所以非常快；

新增和删除慢的原因：

增删会带来元素的移动，增加数据会向后移动，删除数据会向前移动，所以影响效率

适用场景： 如果应用程序对数据有较多的随机访问使用ArrayList较好

ArrayList与LinkedList

两者都是线程不安全的集合；

底层数据结构的不同，ArrayList使用Object[]数组存储，LinkedList使用双向链表存储，JDK1.6之前为循环链表，JDK1.7取消了循环链表；

操作优劣，ArrayList使用数组存储，因此查询速度快，插入，删除速度慢，因为需要移动元素的位置，主要是指从指定位置插入删除速度，从末尾添加元素时间复杂度为O(1)，LinkedList使用链表存储，因此添加，删除速度快，无需移动元素即可完成，而查询速度慢，每次查询某个元素都需要从头部节点或尾部节点开始遍历，直到查找到指定元素；

内存空间占用比较，ArrayList使用数组存储，列表后面总是需要预留一部分空间，造成空间浪费，LinkedList的每个元素所占用的空间总是要比ArrayList每个元素的空间大，因为它需要存储前一个节点的位置和后一个节点的位置，从而占用了较多的空间；

ArrayList与Vector

ArrayList与Vector-样都是使用Object]数组作为底层数据结构,但是ArrayList的方法不是同步的，因此是线程不安全的集合，而Vector的每个方法都是同步的，因此是线程安全的，但是当有多个线程同时访问Vector时，只能有一个线程访问它，其他线程只能等待它完成，因此非常耗时;因此当操作不需要保证线程安全时使用ArrayList比较合适;

八、总结

①List Arayt-i-d-------- Object数组实现 Vector----- >Object数组实现 Linked-is------->双向链表，JDK1.6之 前为循环链表

②Set HashSet(无序，唯一）------> 基于HashMap实现 LinkedHash--------->基于HashSet,其内部是基于LinkedHashMap实现 TreeSet(有序，唯- ---->红黑树(自平衡的排序二叉树)

③Map HashMap JDK1.7---->由数组+链表组成; . JDK1-.8—>阈值大于8s时，链表转变成红黑树，减少搜索时间 LinkedHashMap 继承自HashMap，在HashMap 基础上,增加一条双向链表 Hashtable---->数组+链表 TreeMp------>红黑树(自平衡的排序二叉树)

HashMap JDK1-.7—>由数组+链表组成; JDK1.8—>阈值大于8s时，链表转变成红黑树,减少搜索时间

LinkedHashMap 继承自HashMap,在HashMap 基础上,增加一双向链表 Hashtabe---->数组+链表 TreeM------->红黑树(自平衡的排序二叉树)