集合

Collection接口

  • 集合类的基本接口是Collection接口, 有两个基本方法 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public interface Collection<E> {
    	boolean add(E element);
    	Iterator<E> iterator();
    }

    public interface Iterator<E> {
    	E next();
    	boolean hasNext();
    	void remove();
    	default void forEachRemaining(Consumer<? super E> action);
    }
    // 如果到达末尾依然调用next(), 会抛出NoSuchElementException
    // remove()会删除上一次调用next()返回的元素
    // remove()和next()有依赖性, 如果不先调用next(), 会抛出IllegalStateException
    // 如果需要删除两个元素
    it.next();
    it.remove();
    it.next();
    it.remove();

LinkedList

  • 对于LinkedList, 还存在一个previous(), 支持从后往前遍历
  • 如果调用了previous(), 则remove或set将修改右边的元素
  • 如果有两个迭代器, 一个修改元素, 另一个在遍历元素, 就会产生错误, 抛出ConcurrentModificationException
    • 这里的修改只有增加或删除add(), remove(), set()不会引发错误
  • LinkedList的get()方法不是随机访问, 因为是链表格式, 只是做了一点优化, 如果索引大于n / 2, 则从后往前调用previous()访问

ArrayList

  • 支持动态数组, 并且不是同步的
  • Vector也是动态数组, 但是是同步的, 如果只有一个线程访问Vector, 会在同步操作上花费大量时间, 此时用ArrayList会比较好

散列表

  • Java中散列表使用LinkedList实现, 每个列表称为一个桶
  • 先计算一个对象的散列码, 然后与桶的个数取余, 得到的就是存储桶的索引
  • Java 8中, 桶满了会从链表转换为平衡二叉树
  • 散列表的键要尽可能属于实现了Comparable接口的类, 这样可以避免散列码分布不均的问题
  • 桶的个数一般设计为预计元素个数的75%~150%, 默认桶个数是16个
  • 默认装填因子是0.75, 也就是当哈希表中已经转满了75%就会触发再散列

TreeSet

  • TreeSet是一个有序集合, 使用红黑树实现
  • 插入元素比普通散列表慢, 但是查找一个元素只需要log2(n)log_2(n)
  • 因为是有序的, 所以其中的元素必须实现了Comparable接口

Map

  • 同样分为HashMap, TreeMap

更新

  • counts.put(word, counts.get(word) + 1), 可能word本身不存在, 会抛出NullPointerException
  • counts.put(word, counts.getOrDefault(word, 0) + 1);
  • counts.putIfAbsent(word, 0), 表示如果word不存在, 则赋值为0, 然后调用put即可正常更新, 避免null
  • 也可以使用merge简化操作, counts.merge(word, 1, Integer::sum)
    • 如果word不存在, 就设置为1
    • 如果存在, 就使用Integer::sum设置为word与1的求和

视图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Set<String> keys = map.keySet();
for (String key : keys) {
	...
}

for (Map.Entry<String, E> entry : map.entrySet()) {
	String k = entry.getKey();
	E e = entry.getValue();
}
for (var entry: map.entrySet) {
	..
}
map.forEach((k, v) -> {
	...
});
  • 可以在视图上调用remove()删除散列表的元素, 但是不能添加元素
  • keySet方法返回了一个Set接口的类对象

WeakHashMap

  • 如果一个HashMap中删除了元素, 但是因为HashMap还在使用, 所以GC不会释放这个元素的空间
  • 因此使用WeakHashMap可以释放删除元素的空间, 使用弱引用保存键

LinkedHashSet 与 LinkedHashMap

  • 会记住插入元素的顺序, 在元素加入哈希表后, 会添加到LinkedList双向链表中

EnumSet

  • 使用位序列实现, 如果对应的值出现了, 则在相应的位置设为1
  • 没有公共构造器, 要使用静态工厂方法构造 
    1
    2
    3
    enum Weekday {MONDAY, TUESDAY, ...};
    EnumSet<Weekday> always = EnumSet.allOf(Weekday.class);
    EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class);

标识散列映射

  • IdentityHashMap, 键的散列值不是通过hashCode()计算得到, 而是使用System.indentityHashCode()计算
  • Object.hashCode()计算散列码就使用这个方法, 比较两个对象, IdentityHashMap使用==, 而不是equals

小集合

  • Java 9引入了一些静态方法, 可以生成给定元素的集合或列表, 以及给定的键值对

    • List<String> names = List.of("1", "2", "3");
    • Set<Integer> nums = Set.of(1, 2, 3);
    • Map<String, Integer> m = Map.of("1", 1, "2", 2, "3", 3);

  • List, Set有11个of方法, 还有一个参数可变的of方法, 这样是为了提高效率

  • Map没有这个参数可变的版本, 因为参数类型会交替为键类型和值类型

    • 不过有一个ofEntries, 可以接受任意多个Map.Entry<K, V>对象
      1
      2
      3
      4
      Map<Stirng, Integer> socres = ofEntries(
      	entry("1", 1),
      	entry("2", 2),
      	entry("3", 3));

  • 集合对象是不可修改的, 会导致UnsupportedOperationException

  • 如果需要一个可修改的集合, 可以把这个不可修改的集合传递到构造器中 var names = new ArrayList<>(List.of("1", "2"));

  • Collections.nCopies(n, anObject)会返回一个实现了List接口的不可变对象

    • List<String> settings = Collections.nCopies(100, "DEFAULT");
    • 这样构造包含了100个"DEFAULT"的List, 存储开销很小, 对象只会存储一次

  • Array.asList会返回一个可以更改, 但是大小不可改变的列表, 即可以调用set(), 但是不能使用add(), remove()

不可修改的副本和视图

1
2
3
4
5
ArrayList<String> names = ...
Set<String> nameSet = Set.copyOf(names);
List<String> nameList = List.copyOf(names);
// 每个copyOf()方法会建立集合的一个副本, 修改了原集合这个副本不会受到影响
// 如果原集合正好不可修改, 则copyOf会直接返回原集合

同步视图

  • 如果多个线程访问集合, 一个在修改, 另一个在查看, 结果会发生错误

  • synchronizedMap()可以将任何一个映射转换成有同步访问方法的Map

    • var map = Collections.synchronizedMap(new HashMap<String, Integer>());
    • 这样, get(), put()方法就是同步的, 只有一个执行完了才会调用另一个

  • 对链表排序可以使用归并排序, 但是Java中是先将链表中的数据复制到数组中, 然后在数组中排序完以后再复制回链表

  • Collections.sort()可以对List数据进行排序

  • Collections.binarySearch可以对实现了List的接口的列表去进行二分搜索

    • 如果集合没有采用Comparable接口的compareTo方法进行排序, 则还需要提供一个比较器对象
    • 如果为binarySearch()提供一个链表, 则会退化为线性查找
    • binarySearch()返回值ret如果小于零, 则-ret - 1的位置就是这个元素应该插入的位置

批操作

  • coll1.removeAll(coll2), 在coll1中删除所有coll2包含的元素 (补)

  • coll1.retainAll(coll2), 在coll1中删除所有coll2中没有包含的元素 (交)

  • 数组转集合

    1
    2
    String[] names = ...;
    List<String> staff = List.of(names);

  • 集合转数组

    1
    2
    3
    4
    5
    Object[] names = staff.toArray();
    // 得到一个Object[]数组, 无法进行类型转换
    String[] names = (String[]) staff.toArray(); // Error
    // 需要向toArray传入一个数组构造器表达式
    String[] names = staff.toArray(String[]::new);

遗留

  • Hashtable类和HashMap类作用相同, 但是HashTable是同步的, 不需要兼容性应该使用HashMap, 需要并发应该使用ConcurrentHashMap

  • Enumeration有两个方法hasMoreElements(), nextElements(), 可以使用Collections.list将元素收集到一个ArrayList

  • 属性映射的特性

    • 键值都是字符串
    • 映射可以保存到文件并从文件加载
    • 有一个二级表存放默认值

  • 实现属性映射的Java平台类名为Properties, 对于配置项很有用

    1
    2
    3
    var settings = new Properties();
    settings.setProperty("1", 1);
    settings.setProperty("filename", "/home);

  • 使用store()将属性映射表保存到一个文件中, 比如program.properties

    1
    2
    3
    4
    5
    var out = new FileWriter("program.properties", StandardCharsets.UTF_8);
    settings.store(out, "Program Properties");
    var in  = new FileReader("program.properties", StandardCharsets.UTF_8);
    settings.load(in);
    String userDir = System.getProperty("user.home");

  • Properties因为历史原因实现了Map<>, 因此可以使用get(), put(), 但是get()返回类型是Object, put()允许插入任意对象

    • 所以最好使用处理字符串的getProperty(), setProperty()

  • 栈, Stack, 扩展的Vector, 但是可以使用insert(), remove()添加删除任意的位置

  • 位集, BitSet, 如果需要存储一个位序列, 比如标志, 可以使用位集

    • 因为位集将位包装在字节里, 所以使用位集比使用Boolean, ArrayList高效
    • bitSet.get(i)会返回第i位的结果, true, false
    • bitSet.set(i)将第i位的结果设置为true
    • bitSet.clear(i)将第i位的结果设置为false