集合框架概述

  • 一方面, 面向对象语言对事物的体现都是以对象的形式,为了方便对多个对象的操作,就要对对象进行存储。另一方面,使用Array存储对象方面具有一些弊端,而Java 集合就像一种容器,可以动态地把多个对象的引用放入容器中。

    • 数组在内存存储方面的特点:
      • 数组初始化以后,长度就确定了。
      • 数组声明的类型,就决定了进行元素初始化时的类型
    • 数组在存储数据方面的弊端:
      • 数组初始化以后,长度就不可变了,不便于扩展
      • 数组中提供的属性和方法少,不便于进行添加、删除、插入等操作,且效率不高。同时无法直接获取存储元素的个数
      • 数组存储的数据是有序的、可以重复的。—->存储数据的特点单一
  • Java 集合类可以用于存储数量不等的多个对象,还可用于保存具有映射关系的关联数组。


Java 集合可分为 Collection 和 Map 两种体系

  • Collection接口:单列数据,定义了存取一组对象的方法的集合

    • List元素有序、可重复的集合
    • Set元素无序、不可重复的集合
  • Map接口:双列数据,保存具有映射关系“key-value对”的集合


JDK提供的集合API位于java.util包内

Collection接口继承树:

Map接口继承树:

Collection接口方法

  • Collection 接口是 List、Set 和 Queue 接口的父接口,该接口里定义的方法既可用于操作 Set 集合,也可用于操作 List 和 Queue 集合。

  • JDK不提供此接口的任何直接实现,而是提供更具体的子接口(如:Set和List)实现。

  • 在 Java5 之前,Java 集合会丢失容器中所有对象的数据类型,把所有对象都当成 Object 类型处理;从 JDK 5.0 增加了泛型以后,Java 集合可以记住容器中对象的数据类型。

1、添加

add(Object obj)

addAll(Collection coll)

2、获取有效元素的个数

int size()

3、清空集合

void clear()

4、是否是空集合

boolean isEmpty()

5、是否包含某个元素

boolean contains(Object obj):是通过元素的equals方法来判断是否是同一个对象。

boolean containsAll(Collection c):也是调用元素的equals方法来比较的。拿两个集合的元素挨个比较。

6、删除

boolean remove(Object obj) :通过元素的equals方法判断是否是要删除的那个元素。只会删除找到的第一个元素

boolean removeAll(Collection coll):取当前集合的差集

7、取两个集合的交集

boolean retainAll(Collection c):把交集的结果存在当前集合中,不影响c

8、集合是否相等

boolean equals(Object obj)

9、转成对象数组

Object[] toArray()

10、获取集合对象的哈希值

hashCode()

11、遍历

iterator():返回迭代器对象,用于集合遍历

方法测试:

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
package com.nanzx.collection;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

/**
* Collection接口中声明的方法的测试
* 结论:
* 向Collection接口的实现类的对象中添加数据obj时,要求obj所在类要重写equals().
*/
public class CollectionTest {
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);

//1.contains(Object obj):判断当前集合中是否包含obj
//我们在判断时会调用obj对象所在类的equals()!!!
boolean contains = coll.contains(123);
System.out.println(contains);//true
System.out.println(coll.contains(new String("Tom")));//true,String类有重写equals()
System.out.println(coll.contains(new Person("Jerry",20)));//重写前false -->重写后true

//2.containsAll(Collection coll1):判断形参coll1中的所有元素是否都存在于当前集合中。
Collection coll1 = Arrays.asList(123,4567);
System.out.println(coll.containsAll(coll1));//false
}

@Test
public void test2(){
//3.remove(Object obj):从当前集合中移除obj元素。
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);

coll.remove(1234);
System.out.println(coll);//[123, 456, Person{name='Jerry', age=20}, Tom, false]

coll.remove(new Person("Jerry",20));
System.out.println(coll);//[123, 456, Tom, false]

//4. removeAll(Collection coll1):差集:从当前集合中移除coll1中所有的元素。
Collection coll1 = Arrays.asList(123,456);
coll.removeAll(coll1);
System.out.println(coll);//[Tom, false]
}

@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);

//5.retainAll(Collection coll1):交集:获取当前集合和coll1集合的交集,并返回给当前集合
Collection coll1 = Arrays.asList(123,456,789);
coll.retainAll(coll1);
System.out.println(coll);//[123, 456]

//6.equals(Object obj):要想返回true,需要当前集合和形参集合的元素都相同。
Collection coll2 = new ArrayList();
coll2.add(456);
coll2.add(123);
coll2.add(new Person("Jerry",20));
coll2.add(new String("Tom"));
coll2.add(false);

System.out.println(coll.equals(coll2));//false,因为元素相同但顺序不同,与ArrayList有关
}

@Test
public void test4(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);

//7.hashCode():返回当前对象的哈希值
System.out.println(coll.hashCode());//-1200490100

//8.集合 --->数组:toArray()
Object[] arr = coll.toArray();
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}

//拓展:数组 --->集合:调用Arrays类的静态方法asList()
List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
System.out.println(list);//[AA, BB, CC]

List arr1 = Arrays.asList(new int[]{123, 456});
System.out.println(arr1.size());//1 [[I@32a1bec0]

List arr2 = Arrays.asList(new Integer[]{123, 456});
System.out.println(arr2.size());//2 [123, 456]
}
}

Iterator迭代器接口

使用 Iterator 接口遍历集合元素

  • Iterator对象称为迭代器(设计模式的一种),主要用于遍历 Collection 集合中的元素。

  • GOF给迭代器模式的定义为:提供一种方法访问一个容器(container)对象中各个元素,而又不需暴露该对象的内部细节。迭代器模式,就是为容器而生。类似于“公交车上的售票员”、“火车上的乘务员”、“空姐”。

  • Collection接口继承了java.lang.Iterable接口,该接口有一个iterator()方法,那么所有实现了Collection接口的集合类都有一个iterator()方法,用以返回一个实现了Iterator接口的对象。

  • Iterator 仅用于遍历集合,Iterator 本身并不提供承装对象的能力。如果需要创建Iterator 对象,则必须有一个被迭代的集合。

  • 集合对象每次调用iterator()方法都得到一个全新的迭代器对象,默认游标都在集合的第一个元素之前。

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
package com.nanzx.collection;

import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

/**
* 集合元素的遍历操作,使用迭代器Iterator接口
* 1.内部的方法:hasNext() 和 next()
* 2.集合对象每次调用iterator()方法都得到一个全新的迭代器对象,
* 默认游标都在集合的第一个元素之前。
* 3.内部定义了remove(),可以在遍历的时候,删除集合中的元素。此方法不同于集合直接调用remove()
*/
public class IteratorTest {

@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);

Iterator iterator = coll.iterator();
//方式一:
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// //报异常:NoSuchElementException
// System.out.println(iterator.next());

//方式二:不推荐
// for(int i = 0;i < coll.size();i++){
// System.out.println(iterator.next());
// }

//方式三:推荐
////hasNext():判断是否还有下一个元素
while(iterator.hasNext()){
//next():①指针下移 ②将下移以后集合位置上的元素返回
System.out.println(iterator.next());
}
}

@Test
public void test2(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);

//错误方式一:
Iterator iterator = coll.iterator();
while((iterator.next()) != null){
System.out.println(iterator.next());//跳着输出,最后报NoSuchElementException异常
}

//错误方式二:
//集合对象每次调用iterator()方法都得到一个全新的迭代器对象,默认游标都在集合的第一个元素之前。
// while (coll.iterator().hasNext()){
// System.out.println(coll.iterator().next());//循环打出123
// }
}

//测试Iterator中的remove()
//如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法,
// 再调用remove都会报IllegalStateException。
@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);

//删除集合中"Tom"
Iterator iterator = coll.iterator();
while (iterator.hasNext()){
// iterator.remove();
Object obj = iterator.next();
if("Tom".equals(obj)){
iterator.remove();
// iterator.remove();
}

}
//遍历集合
iterator = coll.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
  • 注意:
    • Iterator可以删除集合的元素,但是是遍历过程中通过迭代器对象的remove方法,不是集合对象的remove方法。
    • 如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法,再调用remove都会报IllegalStateException。

使用 foreach 循环遍历集合元素

  • Java 5.0 提供了 foreach 循环迭代访问 Collection 和 数组

  • 遍历操作不需获取Collection或数组的长度,无需使用索引访问元素。

  • 遍历集合的底层调用Iterator完成操作。

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
package com.nanzx.collection;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collection;

public class ForTest {
@Test
public void test1() {
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry", 20));
coll.add(new String("Tom"));
coll.add(false);

//for(集合元素的类型 局部变量 : 集合对象)
//内部仍然调用了迭代器。
for (Object obj : coll) {
System.out.println(obj);
}
}

@Test
public void test2() {
int[] arr = new int[]{1, 2, 3, 4, 5, 6};
//for(数组元素的类型 局部变量 : 数组对象)
for (int i : arr) {
System.out.println(i);
}
}

//练习题
@Test
public void test3() {
String[] arr = new String[]{"MM", "MM", "MM"};

// //方式一:普通for赋值
// for(int i = 0;i < arr.length;i++){
// arr[i] = "GG";//原数组值改变
// }

//方式二:增强for循环
for (String s : arr) {
s = "GG";//没有改变原数组
}

for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}

List接口

概述

List接口框架

  • |—-Collection接口:单列集合,用来存储一个一个的对象
    • |—-List接口:存储有序的、可重复的数据。 –> 动态数组,替换原有的数组,实现类要重写equals()
      • |—-ArrayList:List接口的主要实现类;线程不安全,效率高;底层使用Object[] elementData存储
      • |—-LinkedList:对于频繁的插入、删除操作,使用此类效率比ArrayList高;底层使用双向链表存储
      • |—-Vector:List接口的古老实现类;线程安全,效率低;底层使用Object[] elementData存储

源码分析

  1. ArrayList的源码分析:

    ① jdk 7情况下

    • ArrayList list = new ArrayList(); //底层创建了长度是10的Object[]数组elementData

    • list.add(123);//elementData[0] = new Integer(123);

    • list.add(11);//如果此次的添加导致底层elementData数组容量不够,则扩容。

    • 默认情况下,扩容为原来的容量的1.5倍,同时需要将原有数组中的数据复制到新的数组中。

    • 结论:建议开发中使用带参的构造器:ArrayList list = new ArrayList(int capacity)

    ② jdk 8中ArrayList的变化:

    • ArrayList list = new ArrayList();//底层Object[] elementData初始化为{}.并没有创建长度为10的数组

    • list.add(123);//第一次调用add()时,底层才创建了长度10的数组,并将数据123添加到elementData[0]

    • 后续的添加和扩容操作与jdk 7 无异。

    • 小结:jdk7中的ArrayList的对象的创建类似于单例的饿汉式,而jdk8中的ArrayList的对象的创建类似于单例的懒汉式,延迟了数组的创建,节省内存

    • 注意:Arrays.asList(…) 方法返回的 List 集合,既不是 ArrayList 实例,也不是Vector 实例。 Arrays.asList(…) 返回值是一个固定长度的 List 集合。


  1. LinkedList的源码分析:

    • LinkedList list = new LinkedList(); 内部声明了Node类型的first和last属性,默认值为null,没有声明数组

    • list.add(123); //将123封装到Node中,创建了Node对象。

    • 其中,Node定义为:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    private static class Node<E> { // 体现了LinkedList的双向链表的说法
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
    }
    }
  • 新增方法:

    • void addFirst(Object obj)

    • void addLast(Object obj)

    • Object getFirst()

    • Object getLast()

    • Object removeFirst()

    • Object removeLast()


  1. Vector的源码分析:

    • jdk7和jdk8中通过Vector()构造器创建对象时,底层都创建了长度为10的数组。

    • 在扩容方面,默认扩容为原来的数组长度的2倍。

    • 新增方法:

    • void addElement(Object obj)

    • void insertElementAt(Object obj,int index)

    • void setElementAt(Object obj,int index)

    • void removeElement(Object obj)

    • void removeAllElements()

接口方法

List除了从Collection集合继承的方法外,List 集合里添加了一些根据索引来操作集合元素的方法。

  • 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位置的左闭右开区间子集合

总结:常用方法

增:add(Object obj)
删:remove(int index) / remove(Object obj)
改:set(int index, Object ele)
查:get(int index)
插:add(int index, Object ele)
长度:size()
遍历:① Iterator迭代器方式 ② 增强for循环 ③ 普通的循环

经典面试题

1
2
3
4
5
6
7
8
9
10
11
12
@Test
public void testListRemove() {
List list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
updateList(list);
System.out.println(list);
}
private static void updateList(List list) {
list.remove(2);
}

这里考察的是updateList调用的remove方法是Collection接口的方法还是List接口的方法

List:remove(int index) / Collection:remove(Object obj)

这里显然调用的是List的remove方法,删除索引为2的元素,如果想删除元素值为2的元素,则是:

list.remove(new Integer(2))


ArrayList和LinkedList的异同:

二者都线程不安全,相对线程安全的Vector,执行效率高。

此外,ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。对于随机访问get和set,ArrayList绝对优于LinkedList,因为LinkedList要移动指针。对于新增和删除操作add(特指插入)和remove,LinkedList比较占优势,因为ArrayList要移动数据。

ArrayList和Vector的区别:

Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized),属于强同步类。因此开销就比ArrayList要大,访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间,而ArrayList是1.5倍。Vector还有一个子类Stack。

Set接口

概述

  • |—-Collection接口:单列集合,用来存储一个一个的对象
    • |—-Set接口:存储无序的、不可重复的数据 –>高中讲的“集合”
      • |—-HashSet:作为Set接口的主要实现类;线程不安全的;可以存储null值
        • |—-LinkedHashSet:作为HashSet的子类;遍历其内部数据时,可以按照添加的顺序遍历,LinkedHashSet效率高于HashSet
      • |—-TreeSet:可以按照添加对象的指定属性,进行排序
        • Set接口中没有额外定义新的方法,使用的都是Collection中声明过的方法。
        • 要求:向Set(主要指:HashSet、LinkedHashSet)中添加的数据,其所在的类一定要重写hashCode()和equals(),重写的hashCode()和equals()尽可能保持一致性:相等的对象必须具有相等的散列码

hashCode() 和 equals()

重写 hashCode() 方法的基本原则:

  1. 在程序运行时,同一个对象多次调用 hashCode() 方法应该返回相同的值。

  2. 当两个对象的 equals() 方法比较返回 true 时,这两个对象的 hashCode() 方法的返回值也应相等。

  3. 对象中用作 equals() 方法比较的 Field,都应该用来计算 hashCode 值。


重写 equals() 方法的基本原则:

以自定义的Customer类为例,何时需要重写equals()?

  1. 默认情况下,也就是从超类Object继承而来的equals方法与‘==’是完全等价的,比较的都是对象的内存地址,但我们可以重写equals方法,使其按照我们的需求的方式进行比较,如String类重写了equals方法,使其比较的是字符的序列,而不再是内存地址。

  2. 当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候,总是要改写hashCode()。根据一个类的equals方法(只改写了equals()方法),两个截然不同的实例有可能在逻辑上是相等的,但是,根据继承的Object.hashCode()方法,它们仅仅是两个对象。因此,违反了“相等的对象必须具有相等的散列码”,需要重写hashCode方法。

    结论:复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。


Eclipse/IDEA工具里hashCode() 和 equals() 的重写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

Person person = (Person) o;

if (age != person.age) return false;
return name != null ? name.equals(person.name) : person.name == null;
}

@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}

为什么用Eclipse/IDEA复写hashCode方法,有31这个数字?

  • 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大,所谓的“冲突”就越少,查找起来效率也会提高。(减少冲突)

  • 并且31只占用5bits,相乘造成数据溢出的概率较小。

  • 31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。(提高算法效率)

  • 31是一个素数,素数作用就是如果我用一个数字来乘以这个素数,那么最终出来的结果只能被素数本身和被乘数还有1来整除!(减少冲突)

HashSet

  • HashSet 按 Hash 算法来存储集合中的元素,因此具有很好的存取、查找、删除性能。

  • HashSet 具有以下特点:

    1. 不能保证元素的排列顺序

    2. HashSet 不是线程安全的

    3. 集合元素可以是 null

  • HashSet 集合判断两个元素相等的标准:两个对象通过 hashCode() 方法比较相等,并且两个对象的 equals() 方法返回值也相等。

添加元素的过程:

  1. 我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法,计算元素a的哈希值,此哈希值接着通过某种散列函数计算出在HashSet底层数组中的存放位置(即为:索引位置)
  2. 判断数组此位置上是否已经有元素:
    • 如果此位置上没有其他元素,则元素a添加成功。 —>情况1
    • 如果此位置上有其他元素b(或以链表形式存在的多个元素),则比较元素a与元素b的hash值:
      • 如果hash值不相同,则元素a添加成功。—>情况2
      • 如果hash值相同,进而需要调用元素a所在类的equals()方法:
        equals()返回true,元素a添加失败
        equals()返回false,则元素a添加成功。--->情况3

对于添加成功的情况2和情况3而言:元素a与已经存在指定索引位置上数据以链表的方式存储。

jdk 7 :元素a放到数组中,指向数组中原来的元素。
jdk 8 :原来的元素在数组中,指向元素a。

HashSet底层:数组+链表的结构

底层数组,初始容量为16,当如果使用率超过0.75,(16*0.75=12)就会扩大容量为原来的2倍。(16扩容为32,依次为64,128....等)

LinkedSet

  • LinkedHashSet 是 HashSet 的子类

  • LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入顺序保存的。

  • LinkedHashSet 插入性能略低于 HashSet,但在迭代访问 Set 里的全部元素时有很好的性能

  • LinkedHashSet 不允许集合元素重复。

TreeSet

  • TreeSet 是 SortedSet 接口的实现类,TreeSet 可以确保集合元素处于排序状态。

  • TreeSet底层使用红黑树结构存储数据

  • 新增的方法如下: (了解)

    • Comparator comparator()

    • Object first()

    • Object last()

    • Object lower(Object e)

    • Object higher(Object e)

    • SortedSet subSet(fromElement, toElement)

    • SortedSet headSet(toElement)

    • SortedSet tailSet(fromElement)

  • TreeSet 两种排序方法:自然排序定制排序。默认情况下,TreeSet 采用自然排序。



自然排序:TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列。

如果试图把一个对象添加到 TreeSet 时,则该对象的类 必须实现 Comparable 接口

实现 Comparable 的类必须实现 compareTo(Object obj) 方法,两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。

Comparable 的典型实现:

  • BigDecimal、BigInteger 以及所有的数值型对应的包装类:按它们对应的数值大小进行比较

  • Character:按字符的 unicode值来进行比较

  • Boolean:true 对应的包装类实例大于 false 对应的包装类实例

  • String:按字符串中字符的 unicode 值进行比较

  • Date、Time:后边的时间、日期比前面的时间、日期大

注意事项:

  1. 向 TreeSet 中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较。
  2. 因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象。
  3. 对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj) 方法比较返回值,如果相等则返回0。
  4. 当需要把一个对象放入 TreeSet 中,重写该对象对应的 equals() 方法时,应保证该方法与 compareTo(Object obj) 方法有一致的结果:如果两个对象通过equals() 方法比较返回 true,则通过 compareTo(Object obj) 方法比较应返回 0。

定制排序:TreeSet的自然排序要求元素所属的类实现Comparable接口,如果元素所属的类没有实现Comparable接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。定制排序,通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。

  • 利用int compare(T o1,T o2)方法,比较o1和o2的大小:如果方法返回正整数,则表示o1大于o2;如果返回0,表示相等;返回负整数,表示o1小于o2。

  • 要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。

  • 此时,仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。

  • 使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package com.nanzx.collection;

public class Person implements Comparable {

private String name;
private int age;

//按照姓名从大到小排列,年龄从小到大排列
@Override
public int compareTo(Object o) {
if (o instanceof Person) {
Person person = (Person) o;
int compare = -this.name.compareTo(person.name);
if (compare != 0) {
return compare;
} else {
return Integer.compare(this.age, person.age);
}
} else {
throw new RuntimeException("输入的类型不匹配");
}
}
}
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
package com.nanzx.collection;

import org.junit.Test;
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;


public class TreeSetTest {

@Test
public void test1() {//测试自然排序
TreeSet set = new TreeSet();

//失败:不能添加不同类的对象
// set.add(123);
// set.add(456);
// set.add("AA");
// set.add(new Person("Tom",12));

//举例一:
// set.add(34);
// set.add(-34);
// set.add(43);
// set.add(11);
// set.add(8);

//举例二:
set.add(new Person("Tom", 12));
set.add(new Person("Jerry", 32));
set.add(new Person("Jim", 2));
set.add(new Person("Mike", 65));
set.add(new Person("Jack", 33));
set.add(new Person("Jack", 56));


Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}

@Test
public void test2() {//测试定制排序
Comparator com = new Comparator() {
//按照年龄从小到大排列
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof Person && o2 instanceof Person) {
Person u1 = (Person) o1;
Person u2 = (Person) o2;
return Integer.compare(u1.getAge(), u2.getAge());
} else {
throw new RuntimeException("输入的数据类型不匹配");
}
}
};

TreeSet set = new TreeSet(com);
set.add(new Person("Tom", 12));
set.add(new Person("Jerry", 32));
set.add(new Person("Jim", 2));
set.add(new Person("Mike", 65));
set.add(new Person("Mary", 33));
set.add(new Person("Jack", 33));//不会出现
set.add(new Person("Jack", 56));


Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}

经典面试题

在List内去除重复数字值,要求尽量简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static List duplicateList(List list) {
HashSet set = new HashSet();
set.addAll(list);
return new ArrayList(set);
}
public static void main(String[] args) {
List list = new ArrayList();
list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(2));
list.add(new Integer(4));
list.add(new Integer(4));
List list2 = duplicateList(list);
for (Object integer : list2) {
System.out.println(integer);
}
}

注意:如果list的元素是自定义的类,还需重写hashcode()和equals()


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package com.nanzx.collection;

import java.util.HashSet;

public class LastTest {
public static void main(String[] args) {
HashSet set = new HashSet();
Person p1 = new Person("AA", 1001);
Person p2 = new Person("BB", 1002);
set.add(p1);
set.add(p2);
p1.name = "CC";
set.remove(p1);
System.out.println(set);
set.add(new Person("CC", 1001));
System.out.println(set);
set.add(new Person("AA", 1001));
System.out.println(set);
}
}

运行结果:
[Person{name=’CC’, age=1001}, Person{name=’BB’, age=1002}]
[Person{name=’CC’, age=1001}, Person{name=’CC’, age=1001}, Person{name=’BB’, age=1002}]
[Person{name=’CC’, age=1001}, Person{name=’CC’, age=1001}, Person{name=’AA’, age=1001}, Person{name=’BB’, age=1002}]

思路请看HashSet添加元素的过程。

Map接口

概述

  • |—-Map:双列数据,存储key-value对的数据 —类似于高中的函数:y = f(x)
    • |—-HashMap:作为Map的主要实现类;线程不安全的,效率高;可以存储null的key和value。
      • |—-LinkedHashMap:保证在遍历map元素时,可以按照添加的顺序实现遍历。对于频繁的遍历操作,此类执行效率高于HashMap。
    • |—-TreeMap:保证按照添加的key-value对进行排序,实现排序遍历。此时考虑key的自然排序或定制排序,底层使用红黑树
    • |—-Hashtable:作为古老的实现类;线程安全的,效率低;不能存储null的key和value
      • |—-Properties:常用来处理配置文件。key和value都是String类型。

key 和 value 之间存在单向一对一关系,即通过指定的 key 总能找到唯一的、确定的 value。

Map中的key:无序的、不可重复的,使用Set存储所有的key —> key所在的类要重写equals()和hashCode() (以HashMap为例)。

Map中的value:无序的、可重复的,使用Collection存储所有的value —>value所在的类要重写equals()

一个键值对:key-value构成了一个Entry对象。

Map中的entry:无序的、不可重复的,使用Set存储所有的entry。

HashMap 判断两个 key 相等的标准是:两个 key 通过 equals() 方法返回 true,hashCode 值也相等。

HashMap 判断两个 value相等的标准是:两个 value 通过 equals() 方法返回 true。

源码分析

存储结构:

JDK 7及以前版本:HashMap是数组+链表结构(即为链地址法)

JDK 8版本发布以后:HashMap是数组+链表+红黑树实现。



HashMap的底层实现原理

jdk7为例说明:

  • HashMap map = new HashMap();//在实例化以后,底层创建了长度是16的一维数组Entry[] table。
  • map.put(key1,value1);
  • 首先,调用key1所在类的hashCode()计算key1哈希值,此哈希值经过某种算法计算以后,得到在Entry数组中的存放位置。

    • 如果此位置上的数据为空,此时的key1-value1添加成功。 —-情况1

    • 如果此位置上的数据不为空,(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值:

      • 如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功。—-情况2

      • 如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同,继续比较:调用key1所在类的equals(key2)方法比较:

        ①如果equals()返回false:此时key1-value1添加成功。—-情况3

        ②如果equals()返回true:使用value1替换value2。

  • 补充:关于情况2和情况3:此时key1-value1和原来的数据以链表的方式存储。
  • 在不断的添加过程中,会涉及到扩容问题,当超出临界值(且要存放的位置非空)时扩容。默认的扩容方式:扩容为原来容量的2倍,并将原有的数据复制过来。

jdk8相较于jdk7在底层实现方面的不同:

  1. new HashMap();底层没有创建一个长度为16的数组

  2. jdk 8底层的数组是:Node[],而非Entry[]

  3. 首次调用put()方法时,底层创建长度为16的数组

  4. jdk7底层结构只有:数组+链表。jdk8中底层结构:数组+链表+红黑树。

  • 形成链表时,七上八下

    • jdk7:新的元素指向旧的元素,新添加的元素作为链表的head。
    • jdk8:旧的元素指向新的元素,新添加的元素作为链表的last,或树的叶子结点。
  • 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时,此时此索引位置上的所数据改为使用红黑树存储。

    • 当HashMap中的其中一个链的对象个数如果达到了8个,此时如果capacity没有达到64,那么HashMap会先扩容解决,如果已经达到了64,那么这个链会变成树,结点类型由Node变成TreeNode类型。当然,如果当映射关系被移除后,下次resize方法时判断树的结点个数低于6个,也会把树再转为链表。

LinkedHashMap的底层实现原理

HashMap中的内部类:Node

1
2
3
4
5
6
7
8
9
10
11
static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

}

LinkedHashMap中的内部类:Entry

1
2
3
4
5
6
7
8
9
10
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);

}
}

源码中的重要常量

  • DEFAULT_INITIAL_CAPACITY : HashMap的默认容量,16

  • MAXIMUM_CAPACITY:HashMap的最大支持容量,2^30

  • DEFAULT_LOAD_FACTOR:HashMap的默认加载因子:0.75

  • threshold:扩容的临界值=容量*填充因子:16 * 0.75 => 12

  • TREEIFY_THRESHOLD:Bucket(桶)中链表长度大于该默认值,转化为红黑树:8

  • MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量:64

  • table:存储元素的数组,总是2的n次幂

  • entrySet:存储具体元素的集

  • size:HashMap中存储的键值对的数量

  • modCount:HashMap扩容和结构改变的次数

面试题

负载因子值的大小,对HashMap有什么影响

  • 负载因子的大小决定了HashMap的数据密度。
  • 负载因子越大密度越大,发生碰撞的几率越高,数组中的链表越容易长,造成查询或插入时的比较次数增多,性能会下降。

  • 负载因子越小,就越容易触发扩容,数据密度也越小,意味着发生碰撞的几率越小,数组中的链表也就越短,查询和插入时比较的次数也越小,性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能,建议初始化预设大一点的空间。

  • 按照其他语言的参考及研究经验,会考虑将负载因子设置为0.7~0.75,此时平均检索长度接近于常数。

接口方法

添加、删除、修改操作:

  • 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集合

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
package com.nanzx.map;

import org.junit.Test;

import java.util.*;

public class MapTest {
@Test
public void test() {
Map map = new HashMap();
map.put("AA", 123);
map.put(45, 1234);
map.put("BB", 56);

//遍历所有的key集:keySet()
Set set = map.keySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println();

//遍历所有的value集:values()
Collection values = map.values();
for (Object obj : values) {
System.out.println(obj);
}
System.out.println();

//遍历所有的key-value
//方式一:entrySet()
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()) {
Object obj = iterator1.next();
//entrySet集合中的元素都是entry
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
System.out.println();

//方式二:
Set keySet = map.keySet();
Iterator iterator2 = keySet.iterator();
while (iterator2.hasNext()) {
Object key = iterator2.next();
Object value = map.get(key);
System.out.println(key + "=====" + value);
}
}
}

TreeMap

  • TreeMap存储 Key-Value 对时,需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。

  • TreeMap底层使用红黑树结构存储数据

  • TreeMap 的 Key 的排序:

    • 自然排序:TreeMap 的所有的 Key 必须实现 Comparable 接口,而且所有的 Key 应该是同一个类的对象,否则将会抛出 ClasssCastException
    • 定制排序:创建 TreeMap 时,传入一个 Comparator 对象,该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable 接口
  • TreeMap判断两个key相等的标准:两个key通过compareTo()方法或者compare()方法返回0。

Properties

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
package com.nanzx.map;

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Properties;

public class PropertiesTest {

//Properties:常用来处理配置文件。key和value都是String类型
public static void main(String[] args) {
FileInputStream fis = null;
try {
Properties pros = new Properties();

fis = new FileInputStream("jdbc.properties");
pros.load(fis);//加载流对应的文件

String name = pros.getProperty("name");
String password = pros.getProperty("password");

System.out.println("name = " + name + ", password = " + password);
} catch (IOException e) {
e.printStackTrace();
} finally {
if (fis != null) {
try {
fis.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
}
1
2
name=阿楠
password=123456

Collections工具类

  • Collections 是一个操作 Set、List 和 Map等集合的工具类(操作数组的工具类:Arrays)

  • Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作,还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

  • 排序操作:(均为static方法)

    • reverse(List):反转 List 中元素的顺序
    • shuffle(List):对 List 集合元素进行随机排序
    • sort(List):根据元素的自然顺序对指定 List 集合元素按升序排序
    • sort(List,Comparator):根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
    • swap(List,int, int):将指定 list 集合中的 i 处元素和 j 处元素进行交换
  • 查找、替换

    • Object max(Collection):根据元素的自然顺序,返回给定集合中的最大元素
    • Object max(Collection,Comparator):根据 Comparator 指定的顺序,返回给定集合中的最大元素
    • Object min(Collection)
    • Object min(Collection,Comparator)
    • int frequency(Collection,Object):返回指定集合中指定元素的出现次数
    • void copy(List dest,List src):将src中的内容复制到dest中
    • boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换List 对象的所有旧值
  • Collections 类中提供了多个 synchronizedXxx() 方法,该方法可使将指定集合包装成线程同步的集合,从而可以解决多线程并发访问集合时的线程安全问题

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
package com.nanzx.collection;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class CollectionsTest {

@Test
public void test() {
List list = new ArrayList();
list.add(123);
list.add(43);
list.add(765);
list.add(-97);
list.add(0);

//报异常:IndexOutOfBoundsException("Source does not fit in dest")
// List dest = new ArrayList();
// Collections.copy(dest,list);
//正确的:
List dest = Arrays.asList(new Object[list.size()]);//需指定dest.size = list.size
System.out.println(dest.size());//list.size();5
Collections.copy(dest, list);

System.out.println(dest);

//返回的list1即为线程安全的List
List list1 = Collections.synchronizedList(list);
}
}