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

集合的框架体系

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

如下图（背，给我背）：

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

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

ArrayList底层实现及源码解析

注：

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

ArrayList底层实现

ArrayList中维护了一个Object类型的数组elementData

当创建ArrayList对象时，如果使用无参构造，则初始elementData为0，第一次添加，检查时发现不足，则扩容elementData为10，如需要再次扩容，则扩容为elementData的1.5倍。

ArrayList扩容在每次添加（add方法）数据时检查是否需要扩容

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

Vector底层实现及源码解析

Vector底层也是一个对象数组 protected Object[] elementData;

Vector是线程同步的（线程安全），Vector的方法带有synchronized，在多线程开发中可以考虑

​ 使用无参构造时，容量默认为10

有参的话就容量为参…

扩容机制同样是在没错添加数据时候检查是否需要扩容，但是Vector的扩容为elementData的两倍

LinkedList

LinkedList底层实现了双向链表和双端队列

可以添加任何元素，可以重复，包括null

没有实现线程安全

LinkedList底层实现

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

LinkedList中维护了两个属性first和last分别指向首节点和尾节点

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

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

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

Set接口

介绍：

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

HashSet

HashSet实际上就是HashMap的key

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

HashSet的添加，原理上是将要存入的值充当HashMap的K，而V则由一个空的Object代替

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

LinkedHashSet

LinkedHashSet是HashSet的子集，底层是一个LinkedHashMap，底层维护了一个数组+双向链表。

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类对象，并进行读取和修改