一、集合概述
我们要对对象进行存储
-
数组
- 弊端：声明时长度就固定
- 数组声明的时候的类型，就决定了元素初始化的类型。
- 不利于扩展，不便于进行添加，删除，插入等操作，效率低。
-
集合
- Java集合类可以用于存储数量不等的多个对象，还能保存具有映射关系的关联数组。
-
使用场景：客户端服务端交互，用集合List存储json对象。
Collection
Map
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-67Zuy0n7-1634393525096)(C:\Users\axi\AppData\Roaming\Typora\typora-user-images\image-20211014185326035.png)]](https://img-blog.csdnimg.cn/42f35281358842ab81dfa9c05b83a1e9.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5oiR5piv5LiA5Liq5aSn6KW_55OcLg==,size_15,color_FFFFFF,t_70,g_se,x_16)
二、Collection接口
- 是List Set 和 Queue 接口的父接口，这里定义的方法可用于操作他们仨。泛型。
1、接口方法
| 方法名 | 功能 |
|---|---|
| add(Obj) / addAll(Collecton col) | 添加 |
| size() | 获取有效元素个数。 |
| clear() | 清空集合 |
| isEmpty() | 是否为空集合 |
| contains(Obj) | 是否包含某一对象 通过equals方法比较 |
| containsAll(Collection col) | 是否包含集合中的对象。 |
| boolean remove(Obj) | 通过equals 判断是否删除 |
| removeAll(Collection col) | 是否删除全部 |
| retainAll(collection col) | 取当前集合的交集，结果存入当前集合。 |
| equals() | 集合是否相等 |
| toArray() | 转换成对象数组 |
| hashCode() | 获取对象的哈希值 |
| iterator() | 返回迭代器对象 |
length() append() indexOf() lastIndexOf() contains() replace() replaceAll() charAt() subString() split() startWith() endWith() toLowerCase() toUperCase() equalsIgnoreCase() isEmpty() trim()
三、List接口
概述
- List集合中的元素有序，可重复，集合中每个元素都有其对应的顺序索引。
- 可根据序号取出List中的元素。
- ArrayList LinkedList Vector
方法
| 方法 | 功能 |
|---|---|
| add(int index,Object o) | 在index位置上插入o |
| addAll(int index,Collection c) | 在index位置上插入c |
| get(index) | 获得index位置上的元素 |
| indexOf() | |
| lastIndexOf() | |
| remove(int index) | 移除指定位置的元素 |
| set(int index,Object o) | 设置指定位置的元素 |
| subList(int from,int to) | 截取list 不包含尾 |
四、ArrayList
- 是List 的主要实现类
- 本质上是ArrayList对象引用的一个**可变长**的数组
1、ArrayList 提供了三个构造器
- 空参构造器 -> 直接创建长度为10的数组 （java 7）先创建长度为0的数组，使用再10（java 8）
- 带参构造器 初始化容量 initialCapacity
- 另一个集合作为参数
2、ArrayList 在 JDK 1.8前后 的区别？
- JDK1.7 像饿汉式 直接创建一个长度为10的数组。
- JDK1.8 像懒汉式 一开始创建长度为0 的数组，添加第一个元素时再创建长度为10的数组。
Arrays.asList() 方法返回的值，是一个固定长度的List 集合。
频繁的遍历查找，建议使用ArrayList
3、ArrayList的底层原理与扩容机制
JDK7
创建：底层直接创建了一个长度为10的数组。
扩容：默认扩容为原来的1.5倍，同时将原数组复制到当前数组。
使用带参构造器，指定数组长度。
JDK8
创建：底层先创建一个长度为0的数组，第一次初始化创建容量为10的数组。
扩容：和JDK7 一样。
使用带参构造器，指定数组长度。
4、ArrayList 的方法
| 方法 | 功能 |
|---|---|
set() | 将元素替代列表中指定位置的元素，并返回原元素 |
add() | 将元素添加到列表的尾部，所有元素向后移1位，拷贝，若不够，扩容x1.5 |
addAll() | 将所有元素添加到列表尾部 |
get() | 支持快速随机访问，通过下标快速访问元素。 |
remove() | 指定下标删除，删除后的元素集体前移1，复制到新的数组中。 |
remove() | 指定对象删除，删除第一次出现的对象。 |
| ensureCapacity() | arrayList独有的方法，通过手动调整数组的方法进行容量控制。 |
| trimToSize() | 将底层数组调整为保存实际元素大小。 |
五、LinkedList
频繁插入删除元素，建议使用LinkedList,查找频繁使用ArrayList
- 底层是双向链表，内部未声明数组，定义了Node类型的first和last，用于记录首末元素。
- Node 定义了两个变量
- prev 记录前一个元素的位置
- next 记录后一个元素的位置
LinkedList 添加/删除 非头节点尾节点 时间复杂度为o(n)
| 方法 | 功能 |
|---|---|
| removeFirst()/push() | 删除头节点并返回（入队） |
| removeLast()/pop() | 删除尾节点并返回（出队） |
| remove() | 删除指定元素（指定下标的元素）并返回 |
| addFirst() | 添加头节点 |
| addLast() | 添加尾节点 |
| size() | 返回链表大小 |
| add() | 在尾部添加节点 |
| get() | 获得任意位置的节点 |
| set() | 设置任意下标的节点 |
| getFirst()/getLast() | 获得头/尾节点 |
六、Vector
底层长度为10的数组，扩容，原来数组的2倍。
常见问题
1、ArrayList与LinkedList的区别
-
线程安全，两者都不是线程安全的
-
底层结构：
- ArrayList 底层是Object数组
- LinkedList 底层是双向链表（JDK6是双向循环链表，JDK7取消了循环。）
-
插入删除元素是否受元素位置影响
- ArrayList 受元素位置影响，如果是add方法，默认插入到列表的尾部，时间复杂度为o(1)，如果需要将元素插入列表i位置，则时间复杂度为o(n-i) 因为底层是数组，需要逐个移动。
- LinkedList 若直接add 复杂度为 o(1) 插入指定位置，指针位移，为o(n) 删除为o(1)，直接指针操作。
-
是否支持快速随机访问
- ArrayList 实现了 RandomAccess 接口，可直接通过下标进行访问，get()
- LinkedList 不支持
-
内存空间占用
- ArrayList 体现在list列表会留有一定空间剩余
- LinkedList 体现在每个元素都要比ArrayList多占空间，要存储前驱后继
2、ArrayList 与 Vector
七、Set接口
特点：无序，不可重复
八、HashSet
无序，不可重复
判断元素相等的标准：1、hashCode 方法比较相等，equals 也相等
存在hashSet里的对象，一定要重写equals()与hashCode() 相等对象必须有相等的散列码。
若只重写equals，不重写hashcode，hashset在去重的时候，即使两个对象是相同的，调用object的hashcode算法，值不同，就不会去重，会导致set中有重复元素。
基于HashMap实现。
1、添加元素过程
- 当 向HashSet中存入一个元素时，会调用该对象的HashCode方法，确定该对象在底层数组的存储位置。
- 当两个元素的hashcode值相等，会继续调用equals值，若值相等，则失败，不等，将其以链表的方式继续进行连接。
- equals相同但hashcode不同，仍然添加成功。
2、存储原理
底层也是数组，初始长度16，若使用率超过0.75 就会扩大到原来的2倍。
九、TreeSet
- 向TreeSet中添加的数据要求是相同类的对象。不能添加不同类的对象。
- 按照添加的顺序从小到大排序。
1、两种排序方式
- 自然排序
- 定制排序
十、Map接口
1、概述
- 与Collection 并列存在，用于保存有映射关系的数据，键值对。
- key用set存放，不允许重复。必须重写equals hashcode方法、
- 常用String 作为Map的键。
- 一对一关系。
2、常用方法
Collection 是 add，因为他是线性的，增加元素，Map是个图，它要把元素put 放入集合中。
| 方法 | 功能 |
|---|---|
| put(key,value) | 添加/修改键值对 |
| putAll(Map map) | 全部添加键值对 |
| remove(key) | 移除键所对应的键值对 |
| clear() | 清空map |
| get(key) | 获得键对应的值 |
| containsKey(key) | 是否包含键 |
| containsValue(value) | 是否包含值 |
| size() | 返回map大小 |
| isEmpty() | 是否为空 |
| Set keySet() | 返回所有键的set集合 |
| Collection values() | 返回所有值的集合 |
| Set entrySet() | 返回键值对实体的set集合 |
十一、HashMap
1、数据结构
“链表散列” 数组和链表的结合体。
1、HashMap的底层原理
JDK7
HashMap hashMap = new HashMap();
-
实例化之后，底层创建了长度为16的一维数组，类型为entry[] table 。
-
map.put(k1,v1); (已经多次put)
- 调用k1所在类的hashcode方法，计算k1哈希值，次值经过算法计算，得到在entry数组中存放位置。
- 若此位置上的数据为空，k1，v1（entry）直接存入成功。
- 若此位置数据不为空，（意味着存在一个或多个数据），比较当前k1和已经存在的一个或多个数据的k的哈希值。
- 若都不同，则添加成功。
- 有相同，调用equals，不等，成功，等于，value2替换value1
- 调用k1所在类的hashcode方法，计算k1哈希值，次值经过算法计算，得到在entry数组中存放位置。
-
默认扩容为原来的2倍。
JDK8与JDK7的区别
1、new HashMap() 底层没有创建长度为16的数组。
2、底层数组是Node[] 而不是 entry[]
3、首次调用put方法时，底层创建长度为16的数组。
4、jdk7 底层结构只有数组 + 链表 ， jdk8 数组+链表+红黑树
? 当数组某个索引位置上的元素以链表形式存在的数据个数大于8且当前数组长度大于64，
? 此时此索引位置上的所有数据改为使用红黑树（二叉排序树）存储。
为什么不用b+树进行底层链表存储呢？
- b+ 树适用于存储大数据量，而在数据量不是很大的时候，会退化成链表，与原来没有区别。so。
2、HashMap长度算法
取余操作%，如果除数是2的幂次，则等价于与其除数减一的与&操作。并且，采用位运算，效率比&运算高。
所以哈希map长度为2的幂次方。
3、多线程导致的死循环问题
多线程不建议用hashmap，建议用ConcurrentHashMap
4、HashMap性能参数
初始容量：底层数组的长度
负载因子：负载因子越大，表示散列表的装填程度越高。
5、HashMap resize(rehash)
- hashMap 中的元素越来越多的时候，hash冲突的几率也越来越高，因为数组长度固定。
- 为了提高查询效率，对hashMap进行扩容，最耗性能的一点就是原数组中的数据必须重新计算其在新数组中的位置，并放进去。resize。
- 扩容时机：负载因子loadFactor 当 数组元素个数超过数组大小*负载因子 的时候，我们就要扩容。默认 长度16，负载因子0.75，将数组扩大为原来的二倍。
6、Fail-Fast机制
原理
快速失败机制，是集合中一种错误检测机制。在迭代集合过程中，该集合在结构上发生改变的时候，就可能发生fail-fast。这种机制并不保证在不同步修改下一定会抛出异常，尽最大努力抛出。仅用于检测bug。
- 迭代过程中，集合结构发生变化，比如remove一个元素，就会发生fail-fast
- 在迭代过程中，iterator调用next方法，每次都会调用checkForComodification();方法，来检验modCount是否变化。
- 注意，初始化时，expectedModCount是等于modCount的
- 当我们调用add，remove，clear等方法，modCount就会改变，就产生了错误。
解决
1、使用迭代器的remove
单线程遍历，使用迭代器的remove方法。局限性：只能remove当前遍历的元素。
十二、LinkedHashMap
- LinkedHashMap是HashMap的子类
- 在HashMap存储结构的基础上，使用一对双向链表记录添加元素的顺序。
- 可维护Map的迭代顺序，与键值对插入顺序一致。