Java集合理论及底层原理_java集合的底层原理

一、Java集合

1、概述

集合、数组都是对多个数据进行存储操作的结构，简称 Java 容器。内存层面的存储，不涉及持久化存储。

使用 Array 存储对象方面具有一些弊端，而 Java 集合就像一种容器，可以动态地把多个对象的引用放入容器中。

Java 集合类可以用于存储数量不等的多个对象，还可用于保存具有映射关系的 关联数组。

数组在内存存储方面的特点：

数组初始化以后，长度就确定了。
数组声明的类型，就决定了进行元素初始化时的类型。
数组在存储数据方面的弊端：

数组初始化以后，长度就不可变了，不便于扩展。
数组中提供的属性和方法有限，不便于进行添加、删除、插入等操作，且效率不高。
数组没有现成的属性或方法获取数组中实际元素的个数。
初始化一个数组的时候，jvm 会在内存上分配一块连续的内存空间，每一个内存空间存一个元素，从首地址开始连续存放，所以数组是有序的，并且存储的数据可以重复的。
Java 集合在开发中的应用：

在持久化层通过 SQL 语句查询到的多条数据映射到 Java 实体类对象，然后通过集合存储多个实体类对象，返回到业务层。

2、集合体系

Java 集合可分为 Collection 和 Map 两种体系：

Collection 接口：单列集合，用来存储一个一个的对象
List：元素有序、有索引、可重复的集合
Set：元素无序、不可重复、无索引的集合
Map 接口：双列数据，存储key-value对的数据 

二、Collection集合

1、Collection接口

1、Collection接口

2、Collection接口常用方法

Collection 接口是 List、Set 和 Queue 接口的父接口，该接口里定义的方法既可用于操作 Set 集合，也可用于操作 List 和 Queue 集合。

JDK5 之前，Java 集合会丢失容器中所有对象的数据类型，把所有对象都作为 Object 类型处理。从 JDK5 增加了泛型以后，Java 集合可以记住容器中对象的数据类型。

Collection是单列集合的父类，它规定的方法（功能）是全部单列集合都会继承的。

常用方法如下：

3、Collection的遍历方式

1、迭代器

迭代器是用来遍历集合的一种方式，在Java中迭代器的代表是Iterator。

Collection集合获取迭代器的方法：

代码实现：

Iterator iterator = coll.iterator();
//hasNext():判断是否还下一个元素
while(iterator.hasNext()){
    //next():①指针下移 ②将下移以后集合位置上的元素返回
    System.out.println(iterator.next());
}

原理：

2、增强for循环（foreach循环）

增强for遍历集合，本质就是迭代器遍历集合的简化写法。

增强for循环可以遍历集合和数组

代码格式：

for (元素的数据类型 变量名 : 数组或者集合) {
         
}

Collection<String> c = new ArrayList<>();
...
for(String s : c) {
    System.out.println(s);
}

快捷方式

单列集合名 或者 数组名.for。

3、forEach（Lambda表达式）

因为Collection接口中包含Set集合子接口，Set子接口无索引，所以不能用for循环遍历。

2、、List接口

List系列集合特点:   有序，可重复，有索引  

ArrayList：有序，可重复，有索引。  

LinkedList：有序，可重复，有索引。

1、List特有方法

List集合因为支持索引，所以多了很多与索引相关的方法，当然，Collection的功能List也都继承了。

2、遍历方式

for循环（因为List集合有索引）

迭代器

增强for循环

forEach（Lambda表达式）

3、ArrayList集合的底层原理

ArrayList基于数组实现的。

查询速度快（注意：是根据索引查询数据快）：查询数据通过地址值和索引定位，查询任意数据耗时相同。

删除效率低：可能需要把后面很多的数据进行前移。

添加效率极低：可能需要把后面很多的数据后移，再添加元素；或者也可能需要进行数组的扩容。

应用场景：

4、LinkedList集合的底层原理

LinkedList是基于双链表实现的。

特点：查询慢，增删相对较快，但对首尾元素进行增删改查的速度是极快的。

LinkedList新增了：很多首尾操作的特有方法

LinkedList的应用场景之一：可以用来设计队列

LinkedList的应用场景之一：可以用来设计栈

push、pop方法底层还是使用LinkedList的首尾操作方法；

3、Set接口

Set系列集合特点：无序：添加数据的顺序和获取出的数据顺序不一致；  不重复； 无索引;

HashSet : 无序、不重复、无索引。

LinkedHashSet：有序、不重复、无索引。

TreeSet：排序、不重复、无索引。

Set要用到的常用方法，基本上就是Collection提供的！！

1、HashSet集合的底层原理

前置知识：哈希值（hash值）

就是一个int类型的数值，Java中每个对象都有一个哈希值。

Java中的所有对象，都可以调用Obejct类提供的hashCode方法，返回该对象自己的哈希值。

public int hashCode()：返回对象的哈希码值。 

对象哈希值的特点：

同一个对象多次调用hashCode()方法返回的哈希值是相同的。

不同的对象，它们的哈希值一般不相同，但也有可能会相同(哈希碰撞)。

HashSet的底层原理：

基于哈希表实现。 哈希表是一种增删改查数据，性能都较好的数据结构。

哈希表

JDK8之前，哈希表 = 数组+链表

JDK8开始，哈希表 = 数组+链表+红黑树

深入理解HashSet集合去重复的机制：

HashSet集合默认不能对内容一样的两个不同对象去重复！ 

比如内容一样的两个学生对象存入到HashSet集合中去 , HashSet集合是不能去重复的！

如果希望Set集合认为2个内容一样的对象是重复的， 必须重写对象的hashCode()和equals()方法。

2、LinkedHashSet底层原理

依然是基于哈希表(数组、链表、红黑树)实现的。

但是，它的每个元素都额外的多了一个双链表的机制记录它前后元素的位置。

3、TreeSet底层原理

特点：不重复、无索引、可排序（默认升序排序 ，按照元素的大小，由小到大排序） 底层是基于红黑树实现的排序。

需要注意的是：

对于数值类型：Integer , Double，默认按照数值本身的大小进行升序排序。

对于字符串类型：默认按照首字符的编号升序排序。

对于自定义类型如Student对象，TreeSet默认是无法直接排序的。

TreeSet集合存储自定义类型的对象时，必须指定排序规则，支持如下两种方式来指定比较规则。

方式一  让自定义的类（如学生类）实现Comparable接口，重写里面的compareTo方法来指定比较规则。

方式二 通过调用TreeSet集合有参数构造器，可以设置Comparator对象（比较器对象，用于指定比较规则。

两种方式中，关于返回值的规则：

如果认为第一个元素 >  第二个元素 返回正整数即可。 如果认为第一个元素 < 第二个元素返回负整数即可。

如果认为第一个元素 = 第二个元素返回0即可，此时Treeset集合只会保留一个元素，认为两者重复。

注意：如果类本身有实现Comparable接口，TreeSet集合同时也自带比较器，默认使用集合自带的比较器排序

4、Collection集合总结

1、场景选择

2、集合并发修改异常

使用迭代器遍历集合时，又同时在删除集合中的数据，程序就会出现并发修改异常的错误。

由于增强for循环遍历集合就是迭代器遍历集合的简化写法，因此，使用增强for循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误

怎么保证遍历集合同时删除数据时不出bug？

使用迭代器遍历集合，但用迭代器自己的删除方法删除数据即可。

如果能用for循环遍历时：可以倒着遍历并删除；或者从前往后遍历，但删除元素后做i --操作。

5、Collections工具类

Collections是Java提供的类,专门用于操作集合 由于构造被私有, 方法都是静态, 所以被称之为工具类

Collections提供的常用静态方法：

三、Map集合

1、概述

1、特点

Map集合称为双列集合，格式：{key1=value1 , key2=value2 , key3=value3 , ...}， 一次需要存一对数据做为一个元素.

Map集合的每个元素“key=value”称为一个键值对/键值对对象/一个Entry对象，Map集合也被叫做“键值对集合”

Map集合的所有键是不允许重复的，但值可以重复，键和值是一一对应的，每一个键只能找到自己对应的值

2、Map集合体系特点

注意：Map系列集合的特点都是由键决定的，值只是一个附属品，值是不做要求的

HashMap（由键决定特点）: 无序、不重复、无索引；  （用的最多）

LinkedHashMap （由键决定特点）:有序、不重复、无索引；

TreeMap （由键决定特点）:按照大小默认升序排序、不重复、无索引。

3、常用方法

Map是双列集合的父类，它的功能是全部双列集合都可以继承过来使用的。

Map的常用方法如下：

4、遍历方式

1、键找值

先获取Map集合全部的键，再通过遍历键来找值

需要用到Map的如下方法：

获取键的集合后，可通过循环获取键对应的值。

2、键值对

3、Lambda

需要用到Map的如下方法：

内部使用entrySet()。

map.forEach((k,v))->{
    System.out.println(k+"--->"+v);
}

2、HashMap底层原理及应用场景

1、HashMap的put方法的具体流程

文字描述：

2、HashMap的扩容机制

3、LinkedHashMap集合的原理

底层数据结构依然是基于哈希表实现的，只是每个键值对元素又额外的多了一个双链表的机制记录元素顺序(保证有序)。

实际上：LinkedHashSet集合的底层原理就是LinkedHashMap。

4、TreeMap集合的原理

特点：不重复、无索引、可排序(按照键的大小默认升序排序，只能对键排序)

原理：TreeMap跟TreeSet集合的底层原理是一样的，都是基于红黑树实现的排序。

TreeMap集合同样也支持两种方式来指定排序规则

让类实现Comparable接口，重写比较规则。

TreeMap集合有一个有参数构造器，支持创建Comparator比较器对象，以便用来指定比较规则。

5、集合的嵌套

homie可自行学习，比较简单，主要是集合中的类型选择