集合

概念：对象的容器，定义了对多个对象进行操作的常用方法，可实现数组的功能

所有集合类都位于java.util包下，Java的集合类主要由两个接口派生而出，Collection和Map，Collection和Map是Java集合框架的根接口，这两个接口又包含了一些子接口或实现类。

集合与数组区别:

  1. 数组长度固定，集合长度不固定
  2. 数组可以存储基本类型和引用类型，集合只能存储引用类型

Collection体系集合

Collection父接口

特点：代表一组任意类型的对象，无序、无下标、不能重复

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
public static void main(String[] args) {
    // 创建集合
    Collection collection = new ArrayList();

    // 添加元素
    collection.add("苹果");        
    collection.add("香蕉");        
    collection.add("梨子");

    // 删除元素
    collection.remove("苹果");

    // 清空集合
    collection.clear();

    // 遍历(无下标，所以循环遍历时只能使用增强for循环)
    for(Object obj : collection) {
        System.out.println(obj);
    }

    // 使用迭代器遍历   
    // 删除当前元素
    Iterator it = collection.iterator();
    // 判断有没有下一个元素
    while(it.hasNext()){
        // 获取元素
        Object obj = it.next();
        // 移除当前元素
        // 使用collection.remove()会报并发修改异常
        it.remove();
    }

    // 判断集合是否存在指定元素
    boolean result1 = collection.contains("梨子");
    // 判断集合是否为空
    boolean result2 = collection.inEmpty();

    // 获取集合元素个数
    int num = collection.size();
}

Set和List的区别

  1. Set接口存储的是无序、无下标、不重复的数据。List接口存储的是有序的、有下标、可以重复的元素
  2. Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变，实现类有HashSet,TreeSet
  3. List和数组类似，可以动态增长，根据实际存储的数据的长度自动增长List的长度。查找元素效率高，插入删除效率低，因为会引起其他元素位置改变，实现类有ArrayList,LinkedList,Vector

List子接口

特点：有序、有下标、元素可重复

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
public static void main(String[] args) {
    // 创建集合
    List list = new ArrayList<>();

    // 添加元素
    list.add("苹果");
    list.add("梨子");
    list.add("香蕉");

    // 删除元素
    list.remove("梨子");
    // 使用索引删除
    list.remove(0);

    // 遍历
    // 使用for循环
    for (int i= 0; i<list.size(); i++) {
        System.out.println(list.get(i));
    }

    // 使用增强for循环
    for(Object obj : list) {
        System.out.println(obj);
    }
    
    // 使用迭代器遍历
    Iterator it = list.iterator();
    // 判断有没有下一个元素
    while(it.hasNext()){
        // 获取元素
        Object obj = it.next();

        // 移除当前元素
        // 如果使用list.remove()会报并发修改异常
        it.remove();
    }

    // 使用列表迭代器，列表迭代器可以从前向后遍历，也可以从后向前遍历
    // 创建迭代器
    ListIterator it1 = list.listIterator();
    // 从前向后遍历
    while(it1.hasNext()){
        System.out.println();
    }
    // 从后向前遍历(因为是同一个迭代器，在上一次遍历之后，迭代器已经指向了集合末尾，所以这里可以直接开始向前遍历)
    while(it1.hasNext()){
        System.out.println();
    }

    // 获取元素出现位置
    System.out.println(list.indexOf("香蕉"));

    // List集合添加整数元素(自动装箱)
    list.add(10);
    list.add(20);

    // 删除List中的整数元素，直接传入整数，会被当做下标，所以这里通过获取下标，用下标来进行删除
    list.remove(list.indexOf(10));

    // 返回子集合，取头不取尾
    List subList = list.subList(0,2);

    // 集合转换为数组
    String[] array =new String[list.size()];
    list.toArray(array);
}

List实现类

  1. ArrayList：数组结构实现，必须要连续空间，查询快，增删慢，运行效率快，线程不安全
  2. Vector：数组结构实现，查询快，增删慢，运行效率慢，线程安全
  3. LinkedList：双向链表结构实现，增删快，查询慢

ArrayList

源码分析：

  • 如果没有向集合中添加任何元素时，容量0，添加一个后，容量为10
  • 首次添加元素时，ArrayList会进行第一次扩容，之后每当判断到容量不够时，就会扩容，每次扩容是原来的1.5倍
1
2
3
4
5
6
7
8
9
10
11
// 一个空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 

// 默认容量
private static final int DEFAULT_CAPACITY = 10; 

// 实际元素个数
private int size; 

// 存放元素的数组
transient Object[] elementData; 
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
// 构造方法，将空数组赋值给存放元素的数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 添加方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制出一个新的数组，覆盖原数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Vector

添加、删除、判断都与List子接口相同，遍历使用枚举器

1
2
3
4
5
6
Vector vector = new Vector();
Enumeration en = vector.elements();
while(en.hasMoreElements()){
  String o = (String)en.nextElement();
  System.out.println(o);
}

LinkedList

常用方法都与List子接口相同
源码分析：

  • 首次添加元素之后，first以及last都会指向第一个节点
  • 之后每次添加元素，first始终指向第一个节点，last会指向当前节点
  • 每个节点中的next属性存储下一个节点，prev属性存储上一个节点
1
2
3
4
5
6
7
8
// 集合大小，初始为0
transient int size = 0;

// 指向集合第一个元素，初始为null
transient Node<E> first;

// 指向集合最后一个元素，初始为null
transient Node<E> last;
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
// 添加方法
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

// 集合中的一个节点
private static class Node<E> {
    // 数据
    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;
    }
}

Set子接口

特点：无序、无下标、元素不可重复
方法：全部继承自Collection父接口中的方法，添加、删除、遍历、判断与collection父接口中一致

Set实现类

  1. HashSet：基于HashCode计算元素存放位置，当在同一个位置存入的两个元素哈希码相同时，会调用equals再次进行确认，对比两个元素的内存地址，如果也为true，则判定为同一个元素，拒绝后者存入，如果为false，说明不是同一个元素，则在此位置形成链表
  2. TreeSet：基于排列顺序实现元素不重复，实现了SortedSet接口，对集合元素自动排序，元素对象的类型必须实现Comparable接口，指定排序规则，通过CompareTo方法确定是否为重复元素

HashSet

存储结构：哈希表(数组+链表+红黑树)

重写hashCode()和equals()方法，可以自定义hash的计算规则，从而改变结果

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

    User user = (User) o;

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

@Override
public int hashCode() {
    int result = name != null ? name.hashCode() : 0;
    // 使用31这个质数，减少散列冲突
    result = 31 * result + age;
    return result;
}
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
public static void main(String[] args) {
    // 创建集合
    HashSet<String> hashSet = new HashSet<String>();

    // 添加元素
    hashSet.add("苹果");
    hashSet.add("梨子");
    hashSet.add("香蕉");

    // 删除元素
    hashSet.remove("梨子");

    // 遍历
    // 使用增强for循环
    for(Object obj : hashSet) {
        System.out.println(obj);
    }

    // 使用迭代器遍历
    Iterator it = hashSet.iterator();
    // 判断有没有下一个元素
    while(it.hasNext()){
        // 获取元素
        System.out.println(it.next());
        // 删除当前元素
        // 使用hashSet.remove()会报并发修改异常
        it.remove();
    }
    System.out.println(hashSet.toString());
}

TreeSet

存储结构：红黑树
要求：使用TreeSet存储引用类型数据时，元素需要要实现Comparable接口，重写compareTo()方法，方法返回值为0，认为是重复元素

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
public class Student implements Comparable<Student>{
    private String name;
    private int age;

    public Student() {
    }

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    
    //重写compareTo方法，这里我们的逻辑是先按照姓名比较，然后再按照年龄比较
    @Override
    public int compareTo(Student o) {
        int n1 = this.getName().compareTo(o.getName());
        int n2 = this.age - o.getAge();
        return n1==0? n2: n1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Test {
    public static void main(String[] args) {
        TreeSet<Student> treeSet = new TreeSet<>();

        Student stu1 = new Student("张三",20);
        Student stu2 = new Student("李四",21);
        Student stu3 = new Student("张三",22);

        treeSet.add(stu1);
        treeSet.add(stu2);
        treeSet.add(stu3);
        
        System.out.println(treeSet.size());
        System.out.println(treeSet.toString());
    }
}

也可以不继承Comparable接口，使用比较器，在创建集合的同时，指定比较规则

1
2
3
4
5
6
7
8
TreeSet<Student> students = new TreeSet<>(new Comparator<Student>() {
    @Override
    public int compare(Student stu1, Student stu2) {
        int n1 = stu1.getName().compareTo(stu2.getName());
        int n2 = stu1.getAge() - stu2.getAge();
        return n1 == 0? n2: n1;
    }
});

Map体系集合

Map父接口

特点：

  • 用于存储任意键值对(key - value)
  • 键：无序、无下标、不允许重复(唯一)
  • 值：无序、无下标、允许重复
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
public static void main(String[] args) {
    //创建Map集合
    Map<String, String> map = new HashMap<>();

    // 1. 添加元素
    map.put("cn", "中国");
    map.put("uk", "英国");
    // 添加重复键，值会覆盖
    map.put("cn", "zhongguo"); 

    // 2. 删除元素
    map.remove("uk");

    // 3. 遍历
    //第一种：
    //遍历所有的key，用key查找对应value
    for (String key : map.keySet()) {
        System.out.println("key= "+ key + " and value= " + map.get(key));
    }

    //第二种：
    //通过Map.entrySet(键值对映射)使用iterator遍历key和value
    Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry<String, String> entry = it.next();
        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
    }

    //第三种：推荐，尤其是容量大时
    //通过Map.entrySet遍历key和value
    for (Map.Entry<String, String> entry : map.entrySet()) {
        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
    }

    //第四种：
    //通过Map.values()遍历所有的value，但不能遍历key
    for (String v : map.values()) {
        System.out.println("value= " + v);
    }
    
    // 4.判断
    System.out.println(map.containsKey("cn"));
    System.out.println(map.containsValue("中国"));
}

Map实现类

  1. HashMap：线程不安全，运行效率快，允许使用null作为key或是value
  2. Hashtable：线程安全，运行效率慢；不允许null作为key或是value
  3. Properties：hashtable的子类，要求key和value都是string，通常用于配置文件的读取
  4. TreeMap：实现了SortedMap接口（是map的子接口），可以对key自动排序

HashMap

存储结构：哈希表(数组+链表+红黑树)
增、删、遍历、判断与Map父接口一致

源码分析：

  • HashMap刚创建时，table是null，节省空间，当添加第一个元素时，table容量调整为16
  • 当元素个数大于阈值（16*0.75 = 12）时，会进行扩容，扩容后的大小为原来的两倍，目的是减少调整元素的个数
  • jdk1.8 当每个链表长度 >8 ，并且数组元素个数 ≥64时，会调整成红黑树，目的是提高效率
  • jdk1.8 当链表长度 <6 时 调整成链表
  • jdk1.8 以前，链表时头插入，之后为尾插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子，容量超过75%则自动扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 键值对映射数组，用于存放传入的键值对，初始为null
transient Node<K,V>[] table;

// 数组大小，初始为0
transient int size;
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
// 添加方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 这一个if判断了table赋给tab的值是否为空，实际上进行了初始化，table的容量变为16
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 当元素个数超过阈值，进行扩容，阈值16*0.75=12，每一次扩容为原来的2倍
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Hashtable

线程安全，运行效率慢；不允许null作为key或是value

Properties

Hashtable的子类，要求key和value都是string，通常用于配置文件的读取

TreeMap

实现了SortedMap接口（是map的子接口），可以对key自动排序
TreeMap存储引用类型数据的时候，也和TreeSet一样，需要实现Comparable接口，或者是在创建集合的同时，指定比较规则，具体使用，参照TreeSet

Collections工具类

集合工具类，定义了除了存取以外的集合常用方法

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
public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(20);
    list.add(5);
    list.add(12);
    list.add(30);
    list.add(6);

    // sort排序(由小到大)
    System.out.println("排序前：" + list.toString());
    Collections.sort(list);
    System.out.println("排序后：" + list.toString());

    // binarySearch二分查找
    int i = Collections.binarySearch(list,12);
    System.out.println(i);

    // copy复制
    List<Integer> dest = new ArrayList<>();
    for (int k = 0;k < list.size();i++) {
        dest.add(0);
    }
    Collections.copy(dest,list);
    System.out.println(dest.toString());

    // reverse反转
    Collections.reverse(list);
    System.out.println("反转后：" + list);

    // shuffle 打乱
    Collections.shuffle(list);
    System.out.println("打乱后：" + list);

    // list转数组,如果数组大小小于集合大小，则会直接存入，如果数组大小大于集合大小，多余部分会用默认值填充
    Integer[] arr = list.toArray(new Integer[10]);
    System.out.println(arr.length);
    System.out.println(Arrays.toString(arr));

    // 数组转集合
    String[] names = {"张三","李四","王五"};
    // 得到的是一个受限集合，不能增删
    List<String> list2 = Arrays.asList(names);
    System.out.println(list2);
}