Java集合详解
Java集合详解
笙沉一、集合概述
Java使用数组对多个对象进行存储具有一些弊端，而Java集合可以动态的将多个对象的引用存入到容器中（内存层面的存储，不涉及持久化存储）。
- 数组在存储时的缺点：
- 数组初始化后，长度就确定了，不利于扩展。
- 数组所提供的属性和方法较少，不便于添加、删除、插入等操作，且效率不高。同时无法直接获取存储元素的个数
- 数组存储的数据是有序的，可重复的。对于无序、不可重复的数据无法满足需求。
- 数组在存储时的缺点：
Java集合的继承及实现关系图：
Java集合可以分为Collection和Map两种体系
- Collection接口：单列数据，定义了存取一组对象的方法集合
- List：存储有序、可重复的集合（可以理解为“动态”数组）
- ArrayList、LinkedList、Vector
- Set：存储无序、不可重复的集合（可以理解为数学上的集合）
- HashSet、LinkedHashSet、TreeSet
- List：存储有序、可重复的集合（可以理解为“动态”数组）
- Map接口：双列数据，保存具有映射关系的Key—value键值对的集合（可以理解为数学上的函数：y = f(x)）
- HashMap、LinkedHashMap、TreeMap、Hashtable、Properties
- Collection接口：单列数据，定义了存取一组对象的方法集合
二、Collection接口
1、Collection常用方法
add(E e)：将元素添加到集合中。size()：获取集合元素的个数。addAll(Collection<? extends E> c)：将另一个集合元素添加到此集合中。clear()：清空集合元素。isEmpty()：判断集合是否为空。contains(Object o)：判断集合中是否存在o。- 注意：使用此方法必须确保对象o所在的类重写了equals()方法，因为其默认调用了equals()方法
containsAll(Collection<?> c)：判断c中的所有元素是否都存在于当前集合中。remove(Object o)：从当前集合移除元素o。removeAll(Collection<?> c)：从当前集合中移除和集合c共有的元素（差集）。retainAll(Collection<?> c)：获取当前集合和集合c共有的元素（交集）。equals(Object o)：判断当前集合和o（也必须是集合）的元素是否相同。hashCode()：返回当前对象哈希值。toArray()：将集合转换为数组，并返回。- 补充：
Arrays.asList(T.. a)：将数组转换为集合，注意：形参不要使用基本数据类型数组。
- 补充：
iterator()：返回iterator接口实例，用于遍历集合元素
2、Iterator迭代器
2.1、Iterator遍历集合元素：
1 |
|
- Iterator迭代流程：创建Iterator对象时，初始指针在集合之前，每次调用hasNext()，会判断当前指针所在位置的下一个元素是否存在，如果存在，则调用next()，此时，指针下移，然后将当前位置的元素返回，直到hasNext()返回为false，才停止循环。
2.2、Iterator中的remove()方法
用于在遍历时候删除集合中的元素。
注意：
- 区别于集合的remove()方法。
- 如果还未调用next()就直接调用remove()会报异常。
- 在上一次调用next()后已经调用了remove()，那么再次调用remove()会报异常。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public void test2(){
Collection c = new ArrayList();
c.add(123);
c.add("WW");
c.add(new String("AA"));
c.add(false);
c.add(new Person("Tom",18));
Iterator iterator = c.iterator();
while (iterator.hasNext()){
//注意：一定要在调用next()之后调用remove()，因为此时指针指向空
Object next = iterator.next();
//若存在元素"AA"则删除
if(next.equals("AA")){
iterator.remove();
}
}
//遍历结果
iterator = c.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
/* 123
WW
false
Person{name='Tom', age=18}*/
3、增强for循环
增强for循环（foreach循环），用于遍历集合、数组。
本质上内部仍然是调用了迭代器。
格式：
1
2
3
4
5
6
7
8/*
1：遍历出来的元素类型
2：元素名，自己取名，类似局部变量
3：要遍历的集合、数组对象
*/
for(1 2 : 3){
//循环体
}例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void test2() {
Collection c = new ArrayList();
c.add(123);
c.add("WW");
c.add(new String("AA"));
c.add(false);
c.add(new Person("Tom", 18));
for(Object obj : c){
System.out.println(obj);
}
}
/* 123
WW
AA
false
Person{name='Tom', age=18}*/
4、List接口
- 因为Java中数组的局限性，我们通常使用List代替数组
- List集合类中元素有序、且可重复，集合的每个元素都有其对应的顺序索引。
- List容器中的元素都对应一个整数型的序号记载其在容器中对应的位置，可以根据序号存取容器中的元素。
- List接口常用的实现类有：ArrayList、LinkedList和Vector。
4.1、ArrayList、LinkedList和Vector三者异同
- 同：三个类都实现了List接口，存储数据的特点相同，都存储有序可重复数据。
- 不同：
- ArrayList：作为List最主要的实现类，线程不安全，效率高；底层使用Object[]存储
- LinkedList：对于频繁的增删操作，效率比ArrayList高，底层使用双向链表存储
- Vector：作为List的古老实现类，线程安全，效率低；底层使用Object[]存储
4.2、ArrayList源码简单解析
JDK7及之前
1
2
3
4
5
6
7ArrayList list = new ArrayList(); //底层创建了长度是10的Object[]数组elementData
list.add(123); //相当于：elementData[0] = new Integer(123);
list.add(456);
/*如果此次添加导致底层elementData数组容量不够，则会扩容，默认情况扩容到原来的1.5倍，
同时将原来数组的数据复制到新的数组中*/
//因此建议开发使用带参构造器：public ArrayList(int initialCapacity){...}可以规定初始长度，无需频繁扩容JDK8中ArrayList的变化
1
2
3
4
5
6ArrayList list = new ArrayList(); //底层Object[] elementData初始化为{},并没有创建长度是10的数组
list.add(123); //第一次调用add()时，底层才创建长度10的数组，并添加数据123到elementData中
list.add(456);
//扩容操作和JDK7一样.....
//此过程类似于单例懒汉式
4.3、LinkedList源码简单解析
1 | LinkedList list = new LinkedList(); //内部声明了Node类型的first和last属性，默认值是null |
4.4、Vector不常用，故省略，其底层也是创建长度为10的数组，只有扩容机制和ArrayList稍有区别，ArrayList默认扩容1.5倍，而Vector扩容两倍。
4.5、List接口独有方法
- List除了从Collection集合继承的方法外。自身还添加了一些根据索引来操作元素的方法。
void add(int index,Object ele)：在index位置添加ele元素。boolean addAll(int index, Collection eles)：从index位置开始将eles中的所有元素添加进来。Object get(int index)：获取指定index位置元素。int indexOf(Object obj)：返回obj在集合首次出现的位置。int lastIndexOf(Object obj)：返回obj在集合末次出现的位置。Object remove(int index)：移除指定的index位置的元素，并返回此元素。Object set(int index,Object ele)：设置指定index位置元素为ele。List subList(int fromIndex,int toIndex)：返回从fromIndex到toIndex位置的子集合。
5、Set接口
- Set接口是Collection的子接口，set没有提供额外的方法，都是继承的Collection的方法。
- Set集合类中元素无序、且不可重复。
- Set接口常用的实现类有：HashSet、LinkedHashSet和TreeSet。
5.1、HashSet、LinkedHashSet和TreeSet三者的区别及特点
- HashSet：作为Set接口的主要实现类；线程不安全；可存储null值。
- LinkedHashSet：HashSet子类，遍历数据时，可以按照添加顺序遍历；
- TreeSet：底层使用了红黑树结构，可以按照添加对象的指定属性进行排序。
5.2、理解无序性及不可重复性（以HashSet为例）。
先看代码案例的输出结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public void test1(){
Set set = new HashSet();
set.add(123);
set.add(456);
set.add(456);
set.add("AA");
set.add("DD");
//注意：此时Person没有重写equals()和hashCode()
set.add(new Person("Tom",18));
set.add(new Person("Tom",18));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
/*
输出：
AA
DD
Person{name='Tom', age=18}
Person{name='Tom', age=18}
456
123
*/
public void test2(){
Set set = new HashSet();
set.add(123);
set.add(456);
set.add(456);
set.add("AA");
set.add("DD");
//注意：此时Person只重写了equals()，并没有重写hashCode()
set.add(new Person("Tom",18));
set.add(new Person("Tom",18));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
/*
输出：
AA
DD
Person{name='Tom', age=18}
Person{name='Tom', age=18}
456
123
*/
public void test3(){
Set set = new HashSet();
set.add(123);
set.add(456);
set.add(456);
set.add("AA");
set.add("DD");
//注意：此时Person重写了equals()和hashCode()
set.add(new Person("Tom",18));
set.add(new Person("Tom",18));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
/*
输出：
AA
DD
Person{name='Tom', age=18}
456
123
*/从上面代码运行结果可以看出：
- 元素输出的顺序和添加的顺序不一致，但却不是随机输出的，因为多次的运行结果并不改变。
- 添加了两次的456最后只输出了一次。
- 没有重写HashCode()和equals()前，person输出了两次；但是两者都被重写后，却只输出一次。
结论：
- 无序性：不等于随机性。存储数据在底层的的数组中并不是按照数组索引进行顺序添加，而是根据数据的哈希值决定。
- 不可重复性：即相同元素只能添加一个。这里的相同的意思为添加的元素按照equals()判断时，不能返回true。
5.3、HashSet添加元素的过程（以HashSet为例）
首先HashSet在底层创建了一个长度是16的数组。
接着调用了需要添加的元素的hashCode()方法，获得了一个哈希值。
然后通过了某种算法对哈希值进行计算（简单点就当作取模运算），得到了这个元素应该存储在哪（即数组下标）。
情况1：如果此下标没有元素，则直接将此元素加入数组对应的下标位置。
情况2：如果某个元素通过计算后发现其应该存放位置的下标为1，但是下标为1的地方已经被另一个元素占据了（这个元素在前面且计算得出也应该存放在下标为1的位置），就比较两者哈希值。
情况2.1：若此元素哈希值和这个元素不相同，则直接通过链表方式存储下去。
情况2.2：若此元素哈希值恰巧和这个元素相同，就会调用这个元素的equals()方法，若返回true则添加失败，若返回false，这时也会以链表的方式将这个元素存储下去（JDK7采用头插法，JDK8为尾插法）。
其结构如下图：
- 因此HashSet底层：数组+链表实现
- 其底层其实是HashMap，存储的值相当于是HashMap中的Key。
- 扩容方式：在下面的HashMap中详解
5.4、LinkedHashSet的使用
1 |
|
- LinkedHashSet作为HashSet子类，虽然输出结果顺序和添加顺序一致，但是不能说LinkedHashSet是有序的，其内存中仍然是无序存储；只不过在存储的每个元素中增加了头尾索引，用于记录前后元素存放的位置，因此它可以按照添加顺序输出。也因此，对于频繁的遍历操作，效率高于HashSet。
5.5、TreeSet的使用
1 |
|
- 向TreeSet中添加的数据，必须是同一个类的对象。
- 两种排序方式：自然排序 和 定制排序（详见Java常见类的比较器）
三、Map接口
Map接口常用方法
Object put(Object key, Object value)：将指定的key-value添加或修改到当前map对象中。void putAll(Map m)：将m中所有的key-value对存放到当前map中。Object remove(Object key)：移除指定的key对应的key-value对，并返回value。void clear()：清空当前的map中所有数据。Object get(Object key)：获取指定key对应的value。boolean containsKey(Object key)：是否包含指定的key。boolean containsValue(Object value)：是否包含指定的value。int size()：返回map中key-value的个数。boolean isEmpty()：判断当前map是否为空。boolean equals(Object obj)：判断当前map和参数对象obj是否相等。Set keySet()：返回所有的key构成的Set集合。Collection values()：返回所有的value构成的Collection集合。Set entrySet()：返回所有key-value构成的Set集合。
Map各种实现类的特点和区别
1
2
3
4
5
6
7
8
9|———Map：双列数据，存储key-value结构的数据，key不能重复，value可以重复———>类似于数学上的函数：y=f(x)
|———HashMap：作为Map的主要实现类；线程不安全，效率高；可以存储为null的key和value
|———LinkedHashMap：在HashMap基础上，添加了一对指针，指向前后元素，
可以保证在遍历map时，可以按照添加顺序遍历。
对于频繁的遍历操作，执行效率高于HashMap。
|———TreeMap：可以按照添加的key-value键值对进行排序，实现排序遍历。
按照key进行自然排序或定制排序。底层使用红黑树。
|———Hashtable：作为Map的古老实现类；线程安全，效率低；不能存储为null的key和value
|———Properties：常用来处理配置文件。key和value都是String类型Map结构的理解(HashMap为例)：
- Map中的key：无序的，不可重复的，使用Set存储所有的key———>key所在的类要重写equals()和hashCode()
- Map中的value：无序的，可重复的，使用Collection存储所有的value———>value所在类要重写equals()
- 一个键值对：key-value构成了一个Entry对象。
- Map中的entry：无序的、不可重复的，使用set存储所有的entry。
1、HashMap底层原理
1.1、JDK7及之前：
底层原理解读：
1
2
3
4
5
6
7
8
9
10
11
12
13
14HashMap map = new HashMap(); //初始化，会在底层创建了长度是16的一维数组Entry[] table。
....... //假设已经执行过多次put()
map.put(key1,value1);
/*
首先会调用key1所在类的hashCode()方法计算key1的哈希值，此哈希值经过某种计算，得到在Entry数组的存放位置
1、如果此位置数据为空，此时key1-value1添加成功
2、如果此位置数据不为空（即此位置存在一个或多个数据（以链表形式存在）），则比较key1和已经存在的一个或多个数据的哈希值
2.1、如果key1的哈希值和已经存在的数据哈希值都不同，则key1-value1以链表形式添加成功
2.2、如果key1的哈希值和已经存在的某一个数据的哈希值相同，则调用key1所在的equals()进行比较
2.2.1、如果equals()返回false，则key1-value1以链表形式添加成功添加成功
2.2.2、如果equals()返回true，则使用value1覆盖原有的value值。
*/
//在不断添加的过程中，会涉及扩容问题，默认扩容方式：扩容为原来两倍，并将原来的数据复制过来结构图
源码分析：
Entry类的结构：
1
2
3
4
5
6
7
8
9
10
11/**
* Entry类实现了Map.Entry接口
* 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
**/
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 存储的键
V value; // 存储的值
Entry<K,V> next; // 链表中指向下一个元素的指针
final int hash; // hash值，用来确定链表上元素存储或取出的位置
........
}重要的属性参数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33/* 1. 容量（capacity）： HashMap中数组的长度
a. 容量范围：必须是2的次幂 & <最大容量（2的30次方）
b. 初始容量 = 哈希表创建时的容量 */
// 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 = 2的30次方（若传入的容量过大，将被最大值替换）
static final int MAXIMUM_CAPACITY = 1 << 30;
/* 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
a. 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）
b. 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高（链表不长）*/
// 实际加载因子
final float loadFactor;
// 默认加载因子 = 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/* 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）
a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
b. 扩容阈值 = 容量 x 加载因子*/
int threshold;
// 4. 其他
// 存储数据的Entry类型 数组，长度 = 2的幂
// HashMap的实现方式 = 拉链法，Entry数组上的每个元素本质上是一个单向链表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// HashMap的大小，即 HashMap中存储的键值对的数量
transient int size;
/* HashMap扩容和结构改变的次数。
结构性变更是指map的元素数量的变化，比如rehash操作。
用于HashMap快速失败操作，比如在遍历时发生了结构性变更，就会抛出ConcurrentModificationException。*/
transient int modCount;构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44//参数：指定一个初始容量，加载因子使用默认值0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//无参构造函数，哈希表数组默认长度是16，默认加载因子是0.75
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//参数一：指定的初始容量
//参数二：指定的加载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)//判断初始容量是否教育0
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//判断初始容量是否超过限制的最大值
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))//判断加载因子是否合法
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
int capacity = 1;
//确保数组长度是2的次幂
while (capacity < initialCapacity)
capacity <<= 1;
//设置加载因子
this.loadFactor = loadFactor;
//设置扩容阈值
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity]; //创建了一个Entry[]数组，默认长度16
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// 一个空方法用于未来的子对象扩展
init();
}
//构造包含子Map的HashMap,y也就是构造的HashMap传入的是键值对
//使用默认的加载因子0.75f，和默认容量16
public HashMap(Map<? extends K, ? extends V> m) {
//设置默认容量和加载因子
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
//将传入的map添加到HashMap中
putAllForCreate(m);
}put()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
* HashMap的put函数
*/
public V put(K key, V value)
//判断key是否为空值null
//若key == null，则将该键值对存放到数组table中的第1个位置，即table[0]
//（本质：key = Null时，hash值 = 0，故存放到table[0]中）
if (key == null)
return putForNullKey(value);
//若 key != null，则计算出存放数组 table 中的位置（下标、索引）
// a. 根据键值key计算hash值
int hash = hash(key.hashCode());
// b. 根据hash值 最终获得 key对应存放的数组Table中位置
int i = indexFor(hash, table.length);
//判断该key对应的值是否已存在（通过遍历 以该数组元素为头结点的链表 逐个判断）
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//若该key已存在（即 key-value已存在 ），则用 新value 替换 旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue; //并返回旧的value
}
}
modCount++;
//若该key不存在，则将“key-value”添加到table中
addEntry(hash, key, value, i);
return null;
}
/**
* addEntry()方法
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//threshold 扩容的临界值
//当size >= 16*0.75 = 12的时候 且这个位置的元素不为空的时候二倍扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //resize()方法见“扩容问题”
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//创建并插入新节点
createEntry(hash, key, value, bucketIndex);
}
/**
* 头插法
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
//取出table[i]位置对应的bucket上原先存在的Entry对象。
Entry<K,V> e = table[bucketIndex];
//new一个新节点，把取出来的e作为新节点的next的结点，即头插法
table[bucketIndex] = new Entry<>(hash, key, value, e);
//HashMap存储的元素个数加1。
size++;
}resize()方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 数组最大扩容到2的30次方
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
// 把旧数组的所有元素拷贝到新数组里
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
// 扩容后，重新计算阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 把旧数组的所有元素拷贝到新数组里
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历数组所有元素
for (Entry<K,V> e : table) {
// 遍历该下标位置上的链表
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 重新计算新数组的下标位置
int i = indexFor(e.hash, newCapacity);
// 头插法
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
1.2、JDK8及之后：
相较于JDK7的不同：
new HashMap()：此时没有创建长度是16的数组
JDK8底层的数组是：Node[]，不是Entry[]数组
首次调用put()方法时，底层才创建长度是16的数组
JDK7底层结构是数组+链表；JDK8底层结构：数组+链表+红黑树（当数组的某一个索引位置上的元素以链表形式存在的数据的个数>8，且当前数组长度超过64时，此索引位置所有的数据会改为红黑树存储）
源码分析：
Node类的结构：
1
2
3
4
5
6
7
8
9
10
11/**
* 相比较于Entry类几乎就是换了个名字
* 也实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
......
}TreeNode 红黑树节点的定义：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* 红黑树节点 实现类：继承自LinkedHashMap.Entry<K,V>类
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 属性 = 父节点、左子树、右子树、删除辅助节点 + 颜色
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
// 构造函数
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 返回当前节点的根节点
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}重要的属性参数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/**
* 主要参数同JDK1.7
* 即：容量、加载因子、扩容阈值（要求、范围均相同）
*/
.........
.........
/**
* 新增与红黑树相关的参数
*/
// 1. 桶的树化阈值：即链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 2. 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 3. 最小树形化容量阈值：即当哈希表中的容量 > 该值时，才允许树形化链表（即将链表转换成红黑树）
// 否则，若桶内元素太多时，则直接扩容，而不是树形化
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/**
* 构造函数1：默认构造函数（无参）
*/
public HashMap() {
//单纯的设置了一下默认加载因子0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
/**
* 构造函数2：指定“容量大小”的构造函数
*/
public HashMap(int initialCapacity) {
// 实际上也只是单纯的设置了一下参数，没有初始化数组
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 构造函数3：指定“容量大小”和“加载因子”的构造函数
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// 设置加载因子
this.loadFactor = loadFactor;
// 设置扩容阈值
// 注：此处不是真正的阈值，仅仅只是将传入的容量大小转化为：>传入容量大小的最小的2的幂，该阈值后面会重新计算
// 见最下方 ->> 分析1
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 构造函数4：包含“子Map”的构造函数
* 即 构造出来的HashMap包含传入Map的映射关系
* 加载因子 & 容量 = 默认
*/
public HashMap(Map<? extends K, ? extends V> m) {
// 设置容量大小 & 加载因子 = 默认
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将传入的子Map中的全部元素逐个添加到HashMap中
putMapEntries(m, false);
}
/**
* 分析1：tableSizeFor(initialCapacity)
* 作用：将传入的容量大小转化为：>传入容量大小的最小的2的幂
* 类似于JDK1.7中的：
* int capacity = 1;
* while (capacity < initialCapacity)
* capacity <<= 1;
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}put()方法
先看一张流程图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134//对外暴露使用
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//put()的真正执行者
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//定义一个数组，一个链表，n用于存放数组长度，
//i用于存放key的hash计算后的值，即key在数组中的索引
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 若哈希表的数组tab为空，则通过resize()创建
// 所以，初始化哈希表的时机 = 第1次调用put函数时，即调用resize()初始化创建
// 关于resize()的源码分析将在下面讲解扩容时详细分析，此处先跳过
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//同时让n等于实例化tab后的长度
//根据key经过hash()方法得到的hash值与数组最大索引做与运算得到当前key所在的索引值i，
// 此处的索引计算方式 = i = (n - 1) & hash，相当于JDK 7中的indexFor()
//并且将当前索引上的Node赋予给p并判断该Node是否存在
if ((p = tab[i = (n - 1) & hash]) == null)
//A.若不存在（即当前table[i] == null），则直接将key-value插入该位置上。
tab[i] = newNode(hash, key, value, null);
//B.否则，代表存在Hash冲突，即当前存储位置已存在节点，
//则依次往下判断: a.当前位置的key是否与需插入的key相同
// b.判断需插入的数据结构是否为红黑树 or 链表
else {
Node<K,V> e; K k; //重新定义一个Node，和一个k
// a.判断table[i]的元素的key是否与需插入的key一样
//（即判断：该位置上数据Key计算后的hash等于要存放的Key计算后的hash，
//并且该位置上的Key等于要存放的Key）
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p; //若相同则直接用新value覆盖旧value
// b，继续判断：需插入的数据结构是否为红黑树 or 链表
// b1.若是红黑树，则直接在树中插入 or 更新键值对
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//->>见下方分析
// b2.若是链表,则在链表中插入 or 更新键值对
// i.遍历table[i]，判断Key是否已存在：若已存在，则直接用新value覆盖旧value
// ii. 遍历完毕后key不重复，则直接在链表尾部插入数据
// 注：新增节点后，需判断链表长度是否>8（8 = 桶的树化阈值）：若是，则把链表转换为红黑树
else {
//遍历当前位置链表
for (int binCount = 0; ; ++binCount) {
//对于ii：若链表的下一个位置为空，表示已到表尾也没有找到key值相同节点
if ((e = p.next) == null) {
//直接将数据写到下个节点
//注：此处是尾插法，与JDK7不同(JDk7：头插)
p.next = newNode(hash, key, value, null);
//新增节点后，若链表节点>数阈值8，则将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
//此处不一定会变成树，treeifyBin()里面还会判断数组长度是否小于64
//如果小于64，不变成树，而是进行数组扩容
//如果大于64，就转成树
treeifyBin(tab, hash);
break;
}
//对于i
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
//更新p指向下一个节点，继续遍历
p = e;
}
}
// 对i情况的后续操作：发现key已存在，直接用新value覆盖旧value并且返回旧value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//插入成功后，判断实际存在的键值对数量size > 最大容量threshold
//若> ，则调用resize()进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);// 插入成功时会调用的方法（默认实现为空）
return null;
}
/**
* 对于37行的解析：putTreeVal(this, tab, hash, key, value)
* 作用：向红黑树插入 or 更新数据（键值对）
* 过程：遍历红黑树判断该节点的key是否与需插入的key相同：
* a.若相同，则新value覆盖旧value
* b.若不相同，则插入
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}resize()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90/**
* resize（）
* 该函数有2种使用情况：1.初始化哈希表 2.当前数组容量过小，需扩容
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 扩容前的数组（当前数组）
int oldCap = (oldTab == null) ? 0 : oldTab.length; //扩容前的数组的容量=长度
int oldThr = threshold;//扩容前的数组的阈值
int newCap, newThr = 0;//定义新的容量和临界值
// 针对情况2：若扩容前的数组容量超过最大值，则不再扩充
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 针对情况2：若未超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 通过右移扩充2倍
}
// 针对情况1：初始化哈希表（采用指定 or 默认值）
else if (oldThr > 0) //当前容量为0，但是当前临界值不为0，让新的容量等于当前临界值
newCap = oldThr;
else { //当前容量和临界值都为0,让新的容量为默认值，临界值=初始容量*默认加载因子
newCap = DEFAULT_INITIAL_CAPACITY; //新的容量 = 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的临界值=12
}
// 计算新的resize上限
if (newThr == 0) { //如果新的临界值为0
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//临界值赋值
threshold = newThr;
//扩容table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;//此时newCap = oldCap*2
else if (e instanceof TreeNode) //节点为红黑树，进行切割操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {//链表的下一个节点还有值，但节点位置又没有超过8
//lo就是扩容后仍然在原地的元素链表
//hi就是扩容后下标为 原位置+原容量 的元素链表，从而不需要重新计算hash。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//循环链表直到链表末再无节点
do {
next = e.next;
//判断元素位置是否还在原位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//循环链表结束，通过判断loTail是否为空来拷贝整个链表到扩容后table
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
2、LinkedHashMap
LinkedHashMap输出顺序和存入的顺序一致，不会像HashMap一样改变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void test1(){
HashMap map = new HashMap();
map.put(123,"AA");
map.put(765,"EE");
map.put(999,"KK");
System.out.println(map);
//输出：{999=KK, 123=AA, 765=EE}
HashMap map2 = new LinkedHashMap();
map2.put(123,"AA");
map2.put(765,"EE");
map2.put(999,"KK");
System.out.println(map2);
//输出：{123=AA, 765=EE, 999=KK}
}LinkedHashMap是HashMap的子类， 其构造方法本质上也是调用HashMap对应的构造方法，其内部结构也只是在HashMap的Node结构上又增加了before和after两个索引，用于指向其前后结点所在位置，因此它可以按照顺序输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29//LinkedHashMap类的声明
public class LinkedHashMap<K,V>
extends HashMap<K,V> //是HashMap子类
implements Map<K,V>
//LinkedHashMap的空参构造器
public LinkedHashMap() {
super(); //调用HashMap对应的构造函数
accessOrder = false; // 迭代顺序的默认值
}
/**
* HashMap的内部类Node
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
/**
* LinkedHashMap的内部类Entry
* 也是继承于HashMap.Node类
*/
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);
}
}所以，对于频繁的遍历操作，可以用LinkedHashMap替代HashMap。
3、TreeMap
- TreeMap中的key必须是由同一个类创建的对象。
- 因为要按照key进行排序：自然排序、定制排序
- 使用方法基本类似于TreeSet，因此不过多赘述，会用即可（注意重写compareTo()方法）。
4、Properties
Properties是Hashtable的子类，该对象用于处理属性文件（通常用作配置文件）
由于属性文件里面的key和value都是字符串类型，所以Properties里面的key-value也都是字符串类型
存取数据时，建议使用
setProperties(String key, String value)和getProperties(String key)方法1
2
3#jdbc.properties文件
username=Tom
password=1234561
2
3
4
5
6
7
8
9
10
11
12
13
public void test1() throws Exception {
Properties properties = new Properties();
FileInputStream fileInputStream = new FileInputStream("jdbc.properties");
properties.load(fileInputStream);
String username = properties.getProperty("username");
String password = properties.getProperty("password");
System.out.println("username：" + username + "\npassword：" + password);
fileInputStream.close();
}
//输出：
//username：Tom
//password：123456
四、Collections工具类
1、概述
- Collections是一个操作Set、List和Map等集合的工具类。
- Collections中提供了一系列静态方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法
2、排序操作
reverse(List)：反转List中元素的顺序。shuffle(List)：对List集合元素进行随机排序。sort(List)：根据元素的自然顺序对指定List集合元素按升序排序。sort(List, comparator)：根据指定的Comparator产生的顺序对List集合元素进行排序。swap(List, int, int)：将指定List集合中的i处元素和j处元素进行交换。
3、查找、替换
Object max(Collection)：根据元素自然顺序，返回给指定集合中的最大元素。Object max(Collection, Comparator)：根据Comparator指定的顺序，返回给定集合中的最大元素。Object min(Collection)：根据元素自然顺序，返回给指定集合中的最小元素。Object min(Collection, Comparator)：根据Comparator指定的顺序，返回给定集合中的最小元素。int frequency(Collection, Object)：返回指定集合中指定元素的出现次数。void copy(List dest,List src)：将src中的内容复制到dest中。boolean replaceAll(List list, Object oldVal, Object newVal)：使用新值替换List对象所有旧值。
4、同步控制
- Collections类中提供了多个synchronizedXxx()方法，该方法可将指定的集合包装成线程同步集合，从而解决多线程并发访问集合时的线程安全问题。
synchronizedCollection(Collection)synchronizedList(List)synchronizedMap(Map)synchronizedSet(Set)
