Java集合底层原理 Java基础学习之集合底层原理

一、Collection集合

Collection接口是单列集合类的父接口，这种集合可以将数据一个一个的存放到集合中。它有两个重要的子接口，分别是 java.util.List 和 java.util.Set

二、List接口

1、特点

•  List是一种有序的集合
• List是一种带索引的集合
• List是一种可以存放重复数据的集合

2、List接口三个主要实现类

3、【面试题】ArrayList、LinkedList、Vector的区别

①ArrayList：线程不安全，查询效率高，插入、删除效率低；底层使用数组存储；
②LinkedList：对于频繁的插入、删除操作效率比ArrayList高，但是查询效率低；底层使用双向链表；
③Vector：线程安全，查询效率高，插入、删除效率低；底层使用数组存储；

源码分析：ArrayList

jdk7

创建对象时底层会创建一个长度为10的数组，默认情况下，扩容为原来的1.5倍，同时将数组复制到新数组中。

jkd8

创建对象时底层不会创建长度为10的数组，而是等到有数据添加进来时才创建。（节约空间，提高效率）

Vector

jdk7和8中创建对象时，底层都创建了长度为10的数组，扩容为原来的2倍

三、Set（Set底层是由Map实现的，所以一般都是问Map）

1、特点

能存储无序、不可重复的元素。
底层：数组+链表

2、无序性

无序性：不等于随机性。存储的数据在底层数组中并非照数组索引的顺序添加，而是根据数据的哈希值决定的。

3、不可重复性

保证添加的元素照equals()判断时，不能返回true.即：相同的元素只能添加一个。

四、Map

1、特点

无序的，不可重复的，由K-V键值对组成。

2、HashMap的源码分析

• jdk7

在创建对象之后，底层会创建长度为16的一维数组Entry，当元素个数超过加载因子乘以数组长度时，并且当前添加元素发生了碰撞，就会进行扩容，扩容为原来的2倍，并复制到新数组中

• jdk8

在创建对象之后底层没有创建长度为16的数组；
首次添加元素时才创建长度为16的数组
jkd8中数Node[],jdk7时Entry[]（就只有名字不同）
jdk7底层是数组+链表；而jdk8中是数组+链表+红黑树
形成链表时，jdk7是新元素指向旧元素；jdk8是旧元素指向新元素（防止高并发造成的死循环）
当链表长度大于8并且数组长度大于64时，才会变成红黑树（提高查找效率）

3、LinkedHashMap

继承于HashMap，用于实现LUR算法

4、Hashtable

线程安全的，k-v都不能为空。
创建对象时默认为11，扩容为原来的2倍加1