Java学习 | 集合框架

本文将介绍Java集合框架中常用的数据结构。Java 集合可分为 Collection 和 Map 两大体系。

java.util.Collection：存储一个一个的数据
|——子接口List：存储有序的、可重复数据（“动态”数组）
|——ArrayList（主要实现类）、LinkedList、Vector

|——子接口Set：存储无序的、不可重复的数据
|——HashSet（主要实现类）、LinkedHashSet、TreeSet

java.util.Map：存储一对一对的数据（key-value）
|——HashMap（主要实现类）、LinkedHashMap、TreeMap、Hashtable、Properties

Collection接口继承树

Map接口继承树

一、ArrayList

ArrayList的特点

实现了List接口，存储有序的、可重复的数据；
底层使用Object[]数组存储；
线程不安全。

ArrayList源码解析

2.1 jdk7版本：(以jdk1.7.0_07为例)

//如下代码的执行：底层会初始化数组，数组的长度为10。
Object[] elementData = new Object[10];
ArrayList\<String> list = new ArrayList<>();

list.add("AA"); //elementData[0] = "AA";
list.add("BB");//elementData[1] = "BB";
...

当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。

2.2 jdk8版本:(以jdk1.8.0_271为例)

//如下代码的执行：底层会初始化数组，即：Object[] elementData = new Object[]{};
ArrayList\<String> list = new ArrayList<>();

list.add("AA"); //首次添加元素时，会初始化数组elementData = new Object[10];elementData[0] = "AA";
list.add("BB");//elementData[1] = "BB";
...

当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。

区别就是后者在添加数据时才初始化数组的长度。

二、Vector

Vector的特点

实现了List接口，存储有序的、可重复的数据；
底层使用Object[]数组存储；
线程安全。

Vector源码解析

Vector v = new Vector(); //底层初始化数组，长度为10。Object[] elementData = new Object[10];
v.add("AA"); //elementData[0] = "AA";
v.add("BB");//elementData[1] = "BB";
...

当添加第11个元素时，需要扩容。默认扩容为原来的2倍。

三、LinkedList

LinkedList的特点

实现了List接口，存储有序的、可重复的数据；
底层使用双向链表存储；
线程不安全。

LinkedList源码解析
因为LinkedList使用的是双向链表，不需要考虑扩容问题。

四、启示与开发建议

Vector基本不使用了。
ArrayList底层使用数组结构，查找和添加（尾部添加）操作效率高，时间复杂度为O(1)，删除和插入操作效率低，时间复杂度为O(n)；
LinkedList底层使用双向链表结构，删除和插入操作效率高，时间复杂度为O(1)，查找和添加（尾部添加）操作效率高，时间复杂度为O(n) (有可能添加操作是O(1))；
在选择了ArrayList的前提下，new ArrayList() : 底层创建长度为10的数组。
new ArrayList(int capacity)：底层创建指定capacity长度的数组。
如果开发中，大体确认数组的长度，则推荐使用ArrayList(int capacity)这个构造器，避免了底层的扩容、复制数组的操作。

五、HashMap

HashMap中元素的特点

线程不安全；
HashMap中的所有的key彼此之间是不可重复的、无序的。所有的key就构成一个Set集合。—>key所在的类要重写hashCode()和equals()；
HashMap中的所有的value彼此之间是可重复的、无序的。所有的value就构成一个Collection集合。—>value所在的类要重写equals()；
HashMap中的一个key-value，就构成了一个entry，所有的entry彼此之间是不可重复的、无序的。所有的entry就构成了一个Set集合。

HashMap源码解析
2.1 jdk7中创建对象和添加数据过程(以JDK1.7.0_07为例说明)：
添加/修改的过程：
将(key1,value1)添加到当前的map中：
首先，需要调用key1所在类的hashCode()方法，计算key1对应的哈希值1，此哈希值1经过某种算法(hash())之后，得到哈希值2。哈希值2再经过某种算法(indexFor())之后，就确定了(key1,value1)在数组table中的索引位置i。
1.1 如果此索引位置i的数组上没有元素，则(key1,value1)添加成功。 —->情况1
1.2 如果此索引位置i的数组上有元素(key2,value2),则需要继续比较key1和key2的哈希值2 —>哈希冲突
2.1 如果key1的哈希值2与key2的哈希值2不相同，则(key1,value1)添加成功。 —->情况2
2.2 如果key1的哈希值2与key2的哈希值2相同，则需要继续比较key1和key2的equals()。要调用key1所在类的equals(),将key2作为参数传递进去。
3.1 调用equals()，返回false: 则(key1,value1)添加成功。 —->情况3
3.2 调用equals()，返回true: 则认为key1和key2是相同的。默认情况下，value1替换原有的value2。
说明：情况1：将(key1,value1)存放到数组的索引i的位置；
情况2，情况3：(key1,value1)元素与现有的(key2,value2)构成单向链表结构，(key1,value1)指向(key2,value2)。
HashMap的扩容机制：
随着不断的添加元素，在满足如下的条件的情况下，会考虑扩容：
jdk1.7需要同时满足以下两个条件：(先判断是否扩容，再存入数据；头插法)
1、存放新值的时候当前已有元素的个数必须大于等于阈值；
2、存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）。
即：(size >= threshold) && (null != table[i])
当元素的个数达到临界值(数组的长度 * 加载因子)时，就考虑扩容。默认的临界值 threshold = 16 * 0.75 –> 12。默认扩容为原来的2倍。
jdk1.8只需要满足以下任意条件：（先存入数据，再判断是否扩容；尾插法）
1、当前存储的数量大于等于阈值；
2、存入数据到某一条链表时，该链表长度>=8，并且数组存储的结点数size() < 64时。
即：(size >= threshold) || (linkedList.size >= 8 && size < 64)
当元素的个数达到临界值(数组的长度 * 加载因子)时，就考虑扩容。默认的临界值 threshold = 16 * 0.75 –> 12。默认扩容为原来的2倍。
2.2 jdk8与jdk7的不同之处(以jdk1.8.0_271为例)：
① 在jdk8中，当我们创建了HashMap实例以后，底层并没有初始化table数组。当首次添加(key,value)时，进行判断，如果发现table尚未初始化，则对数组进行初始化。
② 在jdk8中，HashMap底层定义了Node内部类，替换jdk7中的Entry内部类。意味着，我们创建的数组是Node[]
③ 在jdk8中，如果当前的(key,value)经过一系列判断之后，可以添加到当前的数组角标i中。如果此时角标i位置上有元素。在jdk7中是将新的(key,value)指向已有的旧的元素（头插法），而在jdk8中是旧的元素指向新的(key,value)元素（尾插法）。 “七上八下”
④ jdk7: 数组+单向链表
jk8: 数组+单向链表+红黑树
什么时候会使用单向链表变为红黑树：如果数组索引 i 位置上的元素的个数达到8，并且数组的长度达到64时，我们就将此索引 i 位置上的多个元素改为使用红黑树的结构进行存储。（为什么修改呢？红黑树进行put()/get()/remove()操作的时间复杂度为O(logn)，比单向链表的时间复杂度O(n)的好。性能更高。
什么时候会使用红黑树变为单向链表：当使用红黑树的索引 i 位置上的元素的个数低于6的时候，就会将红黑树结构退化为单向链表。（为什么？节省空间）

六、LinkedHashMap

LinkedHashMap 与 HashMap 的关系:

LinkedHashMap是HashMap的子类；
LinkedHashMap在HashMap使用的数组+单向链表+红黑树的基础上，又增加了一对双向链表，记录添加的(key,value)的先后顺序。便于我们遍历所有的key-value。

LinkedHashMap重写了HashMap的如下方法：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

底层结构：LinkedHashMap 内部定义了一个 Entry

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; //增加的一对双向链表
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}