集合

发表于 分类于 本文字数： 8.3k
单列集合、双列集合

单列集合

  单列集合Collection是所有单列集合实现接口及类的父类，其下有List和Set两个接口，而List下又有ArrayList、LinkedList和Vector（已淘汰）三个实现类，Set下有HashSet和TreeSet两个实现类，HashSet又是LinkedHashSet的父类。。。

  Collection中常用的方法有如下

add(E)，添加一个元素到集合中

1
2
3
4
Collection<String> col1 = new ArrayList<>();
col1.add("A");
col1.add("B");
col1.add("C");

addAll(Collection)，添加另一集合中的所有元素到当前集合中

1
2
3
4
5
6
7
8
9
10
11
12
Collection<String> col1 = new ArrayList<>();
Collection<String> col2 = new ArrayList<>();

col1.add("A");
col1.add("B");
col1.add("C");

col2.add("D");
col2.add("E");

// 把col2中所有元素添加到col1中
col1.addAll(col2);

remove(E)，移除一个元素

1
2
3
4
5
6
7
8
Collection<String> col1 = new ArrayList<>();
col1.add("A");
col1.add("B");
col1.add("C");
col1.add("A");

// 第一个A将会被移除
col1.remove("A");

removeAll(Collection)，移除与另一集合的序列相似的序列

1
2
3
4
5
6
7
8
9
10
11
12
13
Collection<String> col1 = new ArrayList<>();
Collection<String> col2 = new ArrayList<>();
col1.add("A");
col1.add("B");
col1.add("A");
col1.add("B");
col1.add("E");

col2.add("A");
col2.add("B");

// 移除ABAB
col1.removeAll(col2);

retainAll(Collection)，求两集合的并集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Collection<String> col1 = new ArrayList<>();
Collection<String> col2 = new ArrayList<>();

col1.add("A");
col1.add("B");
col1.add("A");
col1.add("B");
col1.add("E");

col2.add("A");
col2.add("B");

// E会被移除
col1.retainAll(col2);

removeIf(Predicate)，条件移除，匿名类Predicate的test方法返回true时元素被移除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Collection<String> col1 = new ArrayList<>();

col1.add("A");
col1.add("B");
col1.add("A");
col1.add("B");
col1.add("E");

col1.removeIf(new Predicate<String>() {
    @Override
    public boolean test(String s) {
        return "A".equals(s);
    }
});

clear()，清空元素

isEmpty()，集合是否为空

size()，集合大小

contains(E)，集合中是否包含某一元素

containsAll(Collection)，集合中是否包含另一集合的序列

iterator()，迭代器

1
2
3
4
5
6
7
// 获取迭代器
Iterator<String> iterator = col1.iterator();

// 通过迭代器遍历
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

List

  List中的元素有序、可重复、有索引

  List集合除包含Collection的所有方法之外，还有如下方法

add(int, E)，在集合的指定位置添加元素

1
2
3
4
5
List<String> list1 = new ArrayList<>();

list1.add(0, "A");
list1.add(0, "B");
list1.add(0, "C");

remove(int)，移除指定位置的元素

1
2
// 移除下标为0的元素
list1.remove(0);

get(int)，获取指定位置的元素

set(int, E)，修改指定位置的元素

Set

  Set中的元素无序、不重复、无索引

HashSet

  HashSet的底层是一个默认长度为16的数组，存储时根据元素的哈希值和数组的长度计算出元素在哈希表中的位置，如果当前位置为空，则直接存入，不为空则采用拉链法储存，通过equals与链表中元素的内容依次对比，确保不重复，若不重复，将新元素挂在老元素的下面（JDK8及以后）；当拉链法链表的长度大于8且数组长度大于等于64时，链表会自动转换成红黑树，以提高查找效率
  HashSet中的元素无序、不重复、无索引，如果集合中存储的对象是自定义对象，则必须重写hashCode()和equals(Object)方法，如下TestBean类中
  如果不重写hashCode()，那么底层将会通过地址值生成对象的哈希值；如果不重写equals(Object)，那么底层将对通过地址值对两个对象进行比较，为了确保Set集合中的不重复性，必须重写这两个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class TeatBean {
    int age;
    String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TeatBean teatBean = (TeatBean) o;
        return age == teatBean.age && Objects.equals(name, teatBean.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name);
    }
}

LinkedHashSet

  LinkedHashSet是HashSet的子类，但是它的元素是有序的，其底层数据结构依然是哈希表，不过元素之间通过双链表记录存储顺序

TreeSet

  TreeSet的底层基于红黑树实现，元素可排序、不重复、无索引
  TreeSet在遍历时似乎是使用二叉树的先序遍历方式
  对于数值类型数据，TreeSet默认会按照从小到大的顺序排列
  对于字符或字符串类型数据，TreeSet默认按照字符在ASCII码表中的数字升序排序；经测试，如果字符串是中文，将按照Unicode编码中的数值部分升序排序，如下代码，将输出[哥, 帅, 我, 是]

1
2
3
4
5
6
7
8
9
10
11
12
char 我 = '\u6211';
char 是 = '\u662f';
char 帅 = '\u5e05';
char 哥 = '\u54e5';

TreeSet<String> treeSet = new TreeSet<>();
treeSet.add(String.valueOf(我));
treeSet.add(String.valueOf(是));
treeSet.add(String.valueOf(帅));
treeSet.add(String.valueOf(哥));

System.out.println(treeSet);

对于自定义对象，必须添加对象比较规则，可采用如下两种方式

  • 第一种：实现Comparable<E>接口，重写compareTos(E e)方法

  TreeSet底层是由红黑树实现，插入结点时也按照红黑树的插入规则；compareTos(E e)方法中的参数表示红黑树中已被插入的结点，当前对象this代表等待插入的结点；插入时通过compareTos(E e)依次比较新结点与已有结点，得出新结点的插入位置

  compareTos(E e)的返回值类型为int，当返回值小于0时，代表插入已有结点的左侧，当返回值大于0时，代表插入已有结点的右侧，当返回值等于0时，代表插入当前位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class TestBean implements Comparable<TestBean> {

    private int number;
    private String key;

    @Override
    public int compareTo(TestBean testBean) {
        // 先根据number进行升序排序，实际开发中不必写这么复杂
        if (this.number < testBean.number)
            return -1;
        if (this.number > testBean.number)
            return 1;

        // number相等时根据key在ASCII码表中的数字升序排序
        return this.key.compareTo(testBean.key);
    }
}
  • 第二种：创建TreeSet集合时，传入Comparator<E>对象，重写compare(E e1, E e2)方法，其中e1代表红黑树中已被插入的结点，e2代表等待插入的结点；插入时通过compare(E e1, E e2)依次比较新结点与已有结点，得出新结点的插入位置

  compare(E e1, E e2)的返回值类型为int，当返回值小于0时，代表插入已有结点的左侧，当返回值大于0时，代表插入已有结点的右侧，当返回值等于0时，代表插入当前位置

1
2
3
4
5
6
7
8
9
10
TreeSet<TestBean> treeSet = new TreeSet<>(new Comparator<TestBean>() {
    @Override
    public int compare(TestBean t1, TestBean t2) {
        if (t1.getNumber() < t2.getNumber())
            return -1;
        if (t1.getNumber() > t2.getNumber())
            return 1;
        return t1.getKey().compareTo(t2.getKey());
    }
});

双列集合

  双列集合Map是所有双列集合实现接口及类的父类，其下有HashMap和TreeMap两个实现类，HashMap下又有LinkedHashMap子类

  Map中常用的方法如下

put(K key, V value)，添加键值和元素到集合中

1
2
3
4
Map<String, TestBean> map = new HashMap<>();

map.put("t1", new TestBean());
map.put("t2", new TestBean());

get(K key)，根据键值获取指定的元素

1
2
3
4
5
6
Map<String, TestBean> map = new HashMap<>();

map.put("t1", new TestBean());
map.put("t2", new TestBean());

TestBean t1 = map.get("t1");

remove(Object obj)，根据键值删除指定的元素

1
2
3
4
5
6
Map<String, TestBean> map = new HashMap<>();

map.put("t1", new TestBean());
map.put("t2", new TestBean());

map.remove("t1");

clear()，清空集合中所有键值对

containsKey(Object obj)，集合中是否包含某个键

containValue(Object obj)，集合中是否包含某个值

isEmpty()，集合是否为空

size()，集合中键值对的个数

keySet()，把Map集合中的所有键放到一个Set集合中

1
2
3
4
5
6
7
8
9
10
11
12
13
Map<String, TestBean> map = new HashMap<>();

map.put("t1", new TestBean(1, "one"));
map.put("t2", new TestBean(2, "two"));

Set<String> keys = map.keySet();

keys.forEach(new Consumer<String>() {
    @Override
    public void accept(String s) {
        System.out.println(map.get(s));
    }
});

entrySet()，把Map集合中的所有键值对放到一个Set集合中

1
2
3
4
5
6
7
8
9
10
11
12
Map<String, TestBean> map = new HashMap<>();

map.put("t1", new TestBean(1, "one"));
map.put("t2", new TestBean(2, "two"));

Set<Map.Entry<String, TestBean>> entries = map.entrySet();
entries.forEach(new Consumer<Map.Entry<String, TestBean>>() {
    @Override
    public void accept(Map.Entry<String, TestBean> entryMap) {
        System.out.println("key=" + entryMap.getKey() + "; value=" + entryMap.getValue());
    }
});

HashMap

  HashMap和HashSet的底层一样，都是一个默认长度为16的数组，区别是在put时如果键相同，新的值会覆盖旧的值

  如果key是自定义对象，则必须重写hashCode()和equals(Object)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class MyKey {
    private int keyValue;
    private String keyContent;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyKey myKey = (MyKey) o;
        return keyValue == myKey.keyValue && Objects.equals(keyContent, myKey.keyContent);
    }

    @Override
    public int hashCode() {
        return Objects.hash(keyValue, keyContent);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Map<MyKey, TestBean> map = new HashMap<>();

MyKey key1 = new MyKey(1, "key1");
MyKey key2 = new MyKey(2, "key2");
MyKey key3  = new MyKey(1, "key1");

TestBean t1 = new TestBean(100, "aaa");
TestBean t2 = new TestBean(200, "bbb");
TestBean t3 = new TestBean(300, "ccc");

map.put(key1, t1);
map.put(key2, t2);
map.put(key3, t3);

map.forEach(new BiConsumer<MyKey, TestBean>() {
    @Override
    public void accept(MyKey myKey, TestBean testBean) {
        System.out.println("key=" + myKey + "; value=" + testBean);
    }
});

LinkedHashMap

  LinkedHashMap是HashMap的子类，但是它的键值对是有序的，其底层数据结构依然是哈希表，不过键值对之间通过双链表记录存储顺序

TreeMap

  对于数值类型数据，TreeMap默认会按照从小到大的顺序排列
  TreeMap的底层基于红黑树实现，对于自定义对象的Key，可以根据Key进行排序，与TreeSet类似，有如下两种排序方式

  • 第一种：实现Comparable<E>接口，重写compareTos(E e)方法

  • 第二种：创建TreeMap集合时，传入Comparator<E>对象，重写compare(E e1, E e2)方法