Java常用集合扩容机制及源码解析

我会带着你远行 2023-09-28 16:27 23阅读 0赞

# Java常用集合扩容机制及源码解析 #

## 集合的框架体系 ##

> ##### Java的集合类有很多，主要分成两大类，即Collection、Map #####

##### 如下图（背，给我背）： #####

![在这里插入图片描述][6e827b3a8f494eb5a26555add3c57dcf.png]  
![在这里插入图片描述][6458195fe3cc4756b658a1992a54486c.png]

> 1.  **集合主要是两组(单列集合 , 双列集合)**
> 2.  **Collection 接口有两个重要的子接口 List Set , 他们的实现子类都是单列集合**
> 3.  \*\*Map 接口的实现子类 是双列集合，存放的 K-V \*\*

##### 注：本文针对集合扩容，将尽可能避免集合方法演示 #####

## ArrayList底层实现及源码解析 ##

注：

*  ArrayList可以加入null，并且可以加入多个
 *  ArrayList是由数组实现数据存储
 *  ArrayLIst与Vector基本一致，区别于ArrayList是线程不安全的，但是ArrayLIst执行效率高于Vector。

#### ArrayList底层实现 ####

ArrayList中维护了一个Object类型的数组elementData  
![在这里插入图片描述][19631603a94a4f6a822b3e423654646e.png]  
当创建ArrayList对象时，如果使用无参构造，则初始elementData为0，第一次添加，检查时发现不足，则扩容elementData为10，如需要再次扩容，则扩容为elementData的1.5倍。  
![在这里插入图片描述][8aecb12c13dd492b8812e4df3c81d144.png]

![在这里插入图片描述][40b38a0cbe544d06b8f6bb61fdaa39fa.png]  
ArrayList扩容在每次添加（add方法）数据时检查是否需要扩容  
![在这里插入图片描述][047d94118820444eb1fe5a21427d7936.png]

如果使用指定大小的构造器，则初始化elementData容量即为指定大小。如需要扩容，则直接扩容为elementData的1.5倍。

## Vector底层实现及源码解析 ##

Vector底层也是一个对象数组 protected Object\[\] elementData;  
![在这里插入图片描述][3d35b9863c8c400ab881eff2884e094a.png]

Vector是线程同步的（线程安全），Vector的方法带有synchronized，在多线程开发中可以考虑  
![在这里插入图片描述][90c06de3b9604dcca4923b560ceaea2c.png]

使用无参构造时，容量默认为10  
![在这里插入图片描述][dc05b1564bee418dbe4ad24de20d252c.png]

有参的话就容量为参…

扩容机制同样是在没错添加数据时候检查是否需要扩容，但是Vector的扩容为elementData的两倍  
![在这里插入图片描述][34d2af848fa143ffb701a1cd08078a25.png]

## LinkedList ##

> LinkedList底层实现了双向链表和双端队列
> 
> 可以添加任何元素，可以重复，包括null
> 
> 没有实现线程安全

### LinkedList底层实现 ###

LinkedList底层维护了一个双向链表

LinkedList中维护了两个属性first和last分别指向首节点和尾节点  
![在这里插入图片描述][06c029752d964e728ac11b3054757cb7.png]

每个节点（Node对象），里面又维护了prev、next、item三个属性，其中通过perv指向前一个节点、通过next指向下一个节点，实现的双向链表。

![在这里插入图片描述][8d9a156b395549b09f1216abf20f7712.png]

由此可知，LinkedList的元素添加和删除，不是通过数组完成的，相对效率较高。

至此本文介绍的List结束，接下来让我们一起看看Set的实现。

## Set接口 ##

介绍：

1.  无序（添加的顺序和取出的顺序不一致），没有索引，可以使用迭代器或者增强for遍历。
2.  不允许重复元素，可以存NUll

### HashSet ###

HashSet实际上就是HashMap的key  
![在这里插入图片描述][e3c6bc58c33043868632121465bce740.png]

HashSet的底层是HashMap，HashMap的底层是数组+链表+红黑树

HashSet的添加，原理上是将要存入的值充当HashMap的K，而V则由一个空的Object代替  
![在这里插入图片描述][4173e3b111514499aa90e64556303f58.png]

扩容机制以及hash皆与HashMap一致 ，加载因子为0.75，满足扩容则会扩容为原来的2倍，当满足一条链表的元素到达8或以上，且table大小达到64或以上，就会进行树化。

### LinkedHashSet ###

LinkedHashSet是HashSet的子集，底层是一个LinkedHashMap，底层维护了一个数组+双向链表。  
![在这里插入图片描述][08a93e01f6114c768f7285656bf968c1.png]

LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序（图），这使得元素看起来是以插入顺序保存的。

LinkedHashSet不允许添重复元素

至此，我们结束了Collection的介绍。

## Map接口 ##

>  *  Map与Collection并列存在。由于保存具有映射关系的K-V。
>  *  Map中的key和value可以是任何引用类型的数据，会封装到HashMap$Node对象中。
>  *  Map中的key不允许重复，原因和HashSet一样，Map中的value可以重复。
>  *  Map的key可以为null，value也可以为null。注意key为null，只能有一个。value为null，可以多个。常用String类作为Map的key。
>  *  key和value之间存在单向一对一关系，即通过指定的key总能找到对应的value。

### HashMap ###

>  *  key不能重复，但是值可以重复，允许使用null键和null值。
>  *  如果添加相同的key,则会覆盖原来的key-val,等同于修改(k不会替换，v会替换)
>  *  不保证映射的顺序，因为底层是以hash表的方式来存储的(jdk8的hashMap底层数组+链表+红黑树)
>  *  HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized

#### 底层实现与扩容机制： ####

*  HashMap底层维护了Node类型的数组table,默认为null
 *  当创建对象时，将加载因子loadfactor初始化为0.75。
 *  当添加key-val时，通过key的哈希值得到在tablel的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key是否等，如果相等，则直接替换v；如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
 *  第1次添加，则需要扩容table容量为16，临界值(threshold为12(16\*0.75)，以后再扩容，则需要扩容table容量为原来的2倍(32)，临界值为原来的2倍，即24，依次类推.
 *  在Java8中，如果一条链表的元素个数超过TREEIFY THRESHOLD(默认是8)，并且tablel的大小>=MIN TREEIFY CAPACITY(默认64)，就会进行树化（红黑树）

### Hashtable ###

*  存放的元素是键值对：即K-V
 *  hashtable的键和值都不能为null,否则会抛出NullPointerException
 *  hashTable使用方法基本上和HashMap一样
 *  hashTable是线程安全的(synchronized)，hashMap是线程不安全的

### Properties ###

>  *  Properties类继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形式来保存数据。他的使用特点和Hashtable类似  
>     tion

*  hashTable使用方法基本上和HashMap一样
 *  hashTable是线程安全的(synchronized)，hashMap是线程不安全的

### Properties ###

>  *  Properties类继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形式来保存数据。他的使用特点和Hashtable类似
>  *  Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象，并进行读取和修改

[6e827b3a8f494eb5a26555add3c57dcf.png]: https://img-blog.csdnimg.cn/6e827b3a8f494eb5a26555add3c57dcf.png
[6458195fe3cc4756b658a1992a54486c.png]: https://img-blog.csdnimg.cn/6458195fe3cc4756b658a1992a54486c.png
[19631603a94a4f6a822b3e423654646e.png]: https://img-blog.csdnimg.cn/19631603a94a4f6a822b3e423654646e.png
[8aecb12c13dd492b8812e4df3c81d144.png]: https://img-blog.csdnimg.cn/8aecb12c13dd492b8812e4df3c81d144.png
[40b38a0cbe544d06b8f6bb61fdaa39fa.png]: https://img-blog.csdnimg.cn/40b38a0cbe544d06b8f6bb61fdaa39fa.png
[047d94118820444eb1fe5a21427d7936.png]: https://img-blog.csdnimg.cn/047d94118820444eb1fe5a21427d7936.png
[3d35b9863c8c400ab881eff2884e094a.png]: https://img-blog.csdnimg.cn/3d35b9863c8c400ab881eff2884e094a.png
[90c06de3b9604dcca4923b560ceaea2c.png]: https://img-blog.csdnimg.cn/90c06de3b9604dcca4923b560ceaea2c.png
[dc05b1564bee418dbe4ad24de20d252c.png]: https://img-blog.csdnimg.cn/dc05b1564bee418dbe4ad24de20d252c.png
[34d2af848fa143ffb701a1cd08078a25.png]: https://img-blog.csdnimg.cn/34d2af848fa143ffb701a1cd08078a25.png
[06c029752d964e728ac11b3054757cb7.png]: https://img-blog.csdnimg.cn/06c029752d964e728ac11b3054757cb7.png
[8d9a156b395549b09f1216abf20f7712.png]: https://img-blog.csdnimg.cn/8d9a156b395549b09f1216abf20f7712.png
[e3c6bc58c33043868632121465bce740.png]: https://img-blog.csdnimg.cn/e3c6bc58c33043868632121465bce740.png
[4173e3b111514499aa90e64556303f58.png]: https://img-blog.csdnimg.cn/4173e3b111514499aa90e64556303f58.png
[08a93e01f6114c768f7285656bf968c1.png]: https://img-blog.csdnimg.cn/08a93e01f6114c768f7285656bf968c1.png