java集合

集合

集合基础

对于数组而言，数组一旦创建长度不可变，集合创建初始长度为0，自动扩容

数组可以存储基本数据类型和引用数据类型，集合只能存储引用数据类型，基本数据类型需要转换成包装类存储

sout打印集合出现的不是地址值，是[]包裹的数据内容，因为底层实现了toString方法

ArrayList成员方法

单列集合Collection

list:有序(存和取的顺序一样),可重复,有索引,add永远返回true
set:无序,不重复,无索引(不能通过for遍历) ,add如果添加重复元素返回false

Collection成员方法

contains底层是一个equals方法,如果没有在JavaBean类中重写,就比较的是地址值

集合遍历方式

迭代器遍历

注意事项：

当结束遍历的时候,指针指向null,当再次调用next方法时候,报错
如果我们要继续第二次遍历集合,需要再次获取一个新的迭代器对象

迭代器遍历的时候不能用集合的方法去增加和删除元素
底层有一个计数器modcount，迭代器每执行一次next()指令的时候就会使modcount++
会检查modcount是否和刚刚创建对象的时候相同,如果不同就表示这个集合被操作了,返回异常

需要使用迭代器的删除方法删除元素 it.remove()

增强for遍历

Lmabda表达式遍历（forEach遍历）

-->

forEach底层是增强for，增强for底层是迭代器

使用场景：

List集合

成员方法

多了一些操作索引的增删改查

插入指定索引的元素会导致后面的元素依次往后移动

两个删除方法的比较

创建集合添加元素

此时调用list.remove(1)

删除的是1索引上的元素“2”，因为此时不会触发remove方法的自动装箱功能，如果要删除1这个元素，需要手动装箱

列表迭代器遍历

List有专属的迭代器Listiterator，多了一个add功能

ArrayList底层原理

JDK8以前空参构造创建的集合，会创建一个默认长度为10的数组，add满了之后会扩容1.5倍

JDK8以后空参构造创建的集合，先创建一个长度为0的数组，add第一个元素的时候会再创建一个新的长度为10的数组

带参构造的时候，底层会创建相应长度的数组，当add到数组满的时候会触发扩容机制，扩容原来的1.5倍，向下取整

JDK8以后是因为如果集合没有添加元素，可以减少空间浪费

size表示元素个数，不表示容量

存满时,会创建新数组(类型是object),长度为10*1.5=15个,然后把老数组中内容拷贝到新数组中
如果一次添加多个元素,1.5倍放不下,则创建的数组长度以实际为准

LinkedList

底层是一个双向链表

查询慢，因为内存不连续，需要一个个遍历过去，时间复杂度为O(n)，平均为O(n/2)
增删快，因为只需要更改相关节点的指针即可，不需要像数组一样插入或删除后需要移动后续大量元素来保持连续性

操作首尾元素速度特别快

Set集合

无序（存取顺序无序）sout无序

方法不变，但是没有get方法，因为没有索引

HashSet

底层是哈希表存储数据
哈希表是一种对于增删改查数据性能都比较好的结构

哈希表组成

JDK8以前：数组+链表
JDK8以后：数组+链表+红黑树

哈希值

String类和Integer类，日期类中已经重写了hashcode和equals方法
所以当集合属性是自定义类的时候需要重写hashcode和equals方法
当重写equals方法的时候,通常也需要重写hashCode方法,以确保两个逻辑上相等的对象具有相同的哈希码

遵循规范：
如果两个对象通过equals方法比较结果为true，那么他们的哈希值必须相等
如果两个对象的哈希值相等，不一定是同一个对象，会发生哈希碰撞（挂在了同一个位置）

HashSet底层原理

挂在同一个位置的元素，就是发生了哈希碰撞（不同的值计算出了相同的哈希桶位置）

hashCode用来计算元素的存储位置
equals用来比较相同位置的元素属性值是否一样

加载因子(扩容时机):默认为0.75,当数组存入元素等于16*0.75=12的时候,数组会自动扩容成原来的两倍32
当链表长度大于8而且数组长度大于等于64的时候,链表会自动变成红黑树(JDK8)
当链表长度小于6的时候，红黑树会变回链表，中间留出了一个缓冲区间（6 - 8），可以避免在元素数量接近 8 时频繁进行结构转换，从而减少不必要的性能开销。

扩容机制都是创建一个新数组，把老数组复制过去

为什么存和取的顺序不一样?

遍历:从数组的索引0开始往后遍历,遇到链表或者红黑树后,往下遍历

为什么无索引？

因为链表和红黑树没有索引

怎么保证元素的去重？

equals方法和hashCode方法同时保证了元素去重（具体阅读上文）

LinkedHashSet

有序，不重复，无索引

底层数据结构依然是哈希表，只是每个元素又额外多了一个双链表的机制记录存储顺序

每添加一个元素都会记录上一个和下一个元素的地址值，形成双向链表，遍历的时候从头结点开始遍历，所以存取顺序是一样的

TreeSet

不重复，无索引，可排序（存取顺序不一致，按照排序规则取）

底层只有红黑树结构，所以和HashCode方法，equals方法无关

默认排序规则

当排序对象是自定义对象的时候，就需要重写排序方法

1.自然排序
需要实现Comparable接口,并重写这个接口的抽象方法CompareTo,指定排序规则

他只有一个参数o,表示有序元素(已经排序好的元素),在这个重写的方法中,我们还需要用到this这个关键字来表示无序元素(准备要排序的元素)

2.自定义排序（当自然排序不能满足排序要求的使用）
需要实现Comparator接口,并重写这个接口的抽象方法compare,指定排序规则

他有两个参数o1和o2,分别表示无序元素(准备要排序的元素)和有序元素(已经排序好的元素)

双列集合Map

（Set底层就是创建了Map对象）

Map接口常见API
在这里插入图片描述

双列集合遍历方式

1.键找值

通过.keySet()方法,返回一个包含键的Set对象
然后遍历这个set获取key通过.get(key)方法,返回这个键对应的值

2.键值对

先通过entrySet()方法来获取带有键值对的Set,命名为entries
然后获取每一个键值对对象entry
通过这个entry对象来调取.getKey和.getValue方法来获取对应的键和值,最后打印

3.Lmabda表达式遍历

forEach源码

方法的底层就是利用键值对遍历的方法,依次获得键和值,再调用accept方法

HashMap

无序，不重复，无索引
都是由键决定，和值无关

数据结构和HashSet一致

创建一个长度为16,默认加载因子为0.75的数组
put方法底层会创建一个Entry对象,Entry对象存储的就是键和值
然后计算键的哈希值,找到index,如果为null就存
如果不为null,用equals方法比较键的属性值
如果键的属性值一样,会覆盖,而HashSet直接不存
如果不一样（发生哈希冲突，不同的key计算出了相同的哈希桶位置）
JDK8以前新元素会添加到数组当中,原先的会挂到上面形成链表
而JDK8以后,新元素会挂到上面,和HashSet一样,链表长度超过8而且数组长度大于等于64,链表自动转成红黑树
当链表长度小于6的时候，红黑树会变回链表。
扩容时机：16*0.75=12,当数组超过12扩容到原来的2倍,并把数据全部转移到新的哈希表中(resize方法)

在这里插入图片描述