Java 集合題目解析

一、簡介

這裏提供了一些有關 Java 集合框架相關的題目，具有一定的代表性，值得記錄下來，以此作爲引導深入學習有關集合框架的相關知識。

二、題目

1. Arrays.asList 和 contains

String[] stringArray = {"one", "two", "three"};
var stringList = Arrays.asList(stringArray);

int[] intArray = {1, 2, 3};
var intList = Arrays.asList(intArray);

System.out.print(stringList.contains("one") + ", ");
System.out.println(intList.contains(1));

輸出：true, false
解析：asList 的汎型參數 T 為引用類型，因此其方法參數為引用類型數組，String 是引用類型，因此 stringList 内部保存的底層數組爲 String[]{"one", "two", "three"}，因此可以遍歷到字符串 "one",返回 true。但是 int 并不是引用類型，而 int[] 是 引用類型，asList 的實參對應的是 int[] 的單個元素，因此 intList 其中包含的底層數組為 int[][]{int[]{1, 2, 3}}，其中只有一個元素，和 1 不相等而返回 false。

2. subList

var ints = new ArrayList<>(List.of(1, 2, 3, 4, 5));
var subList = ints.subList(0, 0);

System.out.print(subList + " ");

subList.addAll(List.of(10, 11, 12));
System.out.print(ints);

輸出：[] [10, 11, 12, 1, 2, 3, 4, 5]
解析：subList 只是底層 List 的視圖，持有原集合的引用，并不重新生成新的數組存放元素，其參數只是限定範文範圍。當修改操作發生是，會對底層數組產生影響。其 addAll 源碼如下： 

public boolean addAll(int index, Collection<? extends E> c) {
    // 部分省略
    root.addAll(offset + index, c);
    updateSizeAndModCount(cSize);
    return true;
}

其中 root 為底層 List 的引用，調用對應的方法實現。

3. null in List

String[] ints = {"a", "b", "c", null};
        
var strings1 = Stream.of(ints).toList();
System.out.print(strings1.size());

var strings2 = List.of(ints);
System.out.print(strings2.size());

輸出： 4Exception in thread "main" java.lang.NullPointerException
解析： Stream.toList() 創建普通的集合，可以接受空值，但是 List.of 創建 Unmodifiable Lists，拒絕空值。

Unmodifiable Lists 特性如下：

4. Arrays.asList().remove

String[] ints = {"a", "b", "c", null};
List<String> strings = Arrays.asList(ints);
strings.removeIf(Objects::isNull);
System.out.print(strings.size());

輸出： UnsupportedOperationException
解析： 使用 Arrays.asList 創建的是不可修改的集合，不支持添加，修改，刪除等操作，對應的方法并沒有實現，繼承的 AbstractList 的方法，其實現為抛出 UnsupportedOperationException。

5. Map.put(key, null)

Map<Integer, String> map = new HashMap<>();
map.put(4, null);
System.out.print(map.getOrDefault(4, "four"));
map.putIfAbsent(4, "four");
System.out.print(map.get(4));

輸出： null four
解析： 

// Map
default V getOrDefault(Object key, V defaultValue) {
    V v;
    return (((v = get(key)) != null) || containsKey(key))
        ? v
        : defaultValue;
}
// HashMap
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(key)) == null ? defaultValue : e.value;
}

從上述兩個 getOrDefault 方法實現來看，返回原值取決於 key 對應的結點 Entry 存在。儘管原值可能為 null，Entry 不存在才返回新值。

// Map
default V putIfAbsent(K key, V value) {
    V v = get(key);
    if (v == null) {
        v = put(key, value);
    }
    return v;
}
// HashMap
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}
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 ((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;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

從上述兩個 putIfAbsent 方法實現來看，節點不存在或者儘管節點存在，但是當原值為 null 時還會把新值替換進去。

6. Map.pustIfAbsent 返回值

var numbers = List.of(-1, 0, 1);
Map<Integer, List<Integer>> map = new HashMap<>();
numbers.forEach(number ->  {
    map.putIfAbsent(number, new ArrayList<>()).add(number);
});
System.out.print(map.get(0));

輸出： java.lang.NullPointerException
解析： putIfAbsent 代碼如上一題所示，該方法返回了舊值，如果 key 不存在則返回 null。對於 put 前綴的方法均遵循上述慣例。如果要返回當前值，應該換用 computedIfAbsent。

7. Map.comouteIfAbsent

var numbers = List.of(-1, 0, 1);
Map<Integer, List<Integer>> map = new HashMap<>();
numbers.forEach(number ->  {
    map.computeIfAbsent(number, ArrayList::new).add(number);
});
System.out.print(map.get(0));

輸出： java.lang.IllegalArgumentException: Illegal Capacity: -1
解析： computeIfAbsent 當 key 不存在時，將 key 傳給 mappingFunction，計算新值。此時 mappingFunction 對應的函數為 ArrayList::new，其不接受容量為負值，因此抛出對應的異常。具體代碼如下。 

public V computeIfAbsent(K key, 
       Function<? super K, ? extends V> mappingFunction) {
    // 省略
    V v = mappingFunction.apply(key);
    // 省略
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    }
}

8. TreeSet 和 HashSet

Set<String> hashSet = new HashSet<>(List.of("a", "b", "c"));
Set<String> treeSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);

treeSet.addAll(List.of("A", "B", "C"));

System.out.print(treeSet.equals(hashSet) + " ");
System.out.print(hashSet.equals(treeSet));

輸出： true false
解析： 由於 TreeSet 傳入了 String.CASE_INSENSITIVE_ORDER，其作用為忽略大小寫，在 TreeSet.contains 比較中使用了該比較器來尋找 key，代碼如下。因此 hashSet 中元素和 treeSet 中相等，但是 hashSet 并沒有此功能，因此 返回 false。 

// TreeMap
final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

9. IdentityHashMap

var map = new IdentityHashMap<Integer, String>();
map.put(1, "one");
map.put(10, "ten");
map.put(100, "hundred");
map.put(1000, "thousand");
map.put(1, "one again");
map.put(10, "ten again");
map.put(100, "hundred again");
map.put(1000, "thousand again");
System.out.println(map.size());

輸出： 5
解析： IdentityHashMap 使用引用相等（==）而不是 equals 方法來比較 key 的相等性。由於在默認情況下系統内部緩存了 -128 ~ 127 的整數值，因此 1，10，100 三個 key 對應的 value 會被替換，但是兩個 1000 并不相等，後一個被添加到 map 中，因此總共有 5 個元素。 

private static class IntegerCache {
    static final int low = -128;
    static final int high;
    static final Integer[] cache;
    static Integer[] archivedCache;

    static {
        // high value may be configured by property
        int h = 127;
        String integerCacheHighPropValue =
            VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
        if (integerCacheHighPropValue != null) {
            try {
                h = Math.max(parseInt(integerCacheHighPropValue), 127);
                // Maximum array size is Integer.MAX_VALUE
                h = Math.min(h, Integer.MAX_VALUE - (-low) -1);
            } catch( NumberFormatException nfe) {
                // If the property cannot be parsed into an int, ignore it.
            }
        }
        high = h;
    }
}

如上代碼所示，Integer 緩存的最小值固定為 -128，最大值可以在程序運行時通過添加執行參數 -XX:AutoBoxCacheMax=2000 調節，但是設置的值不能小於 127，讓結果發生變化。

10. LinkedHashMap

Map<String, Integer> map = LinkedHashMap.newLinkedHashMap(3);
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
map.put("b", 4);
System.out.print(map.get("a"));
System.out.println(map);

輸出： 1{a=1, b=4, c=3}
解析： LinkedHashMap 按照放入的順序來鏈接元素，但是當元素已經存在時并不會調整元素順序，只會替換對應的 value。其 put 使用 HashMap 的 put，沒有任何改變。

11. List 和 Collection

var ints = List.of(1, 2, 3);
var a = Arrays.asList(1, 2, 3);
var c = Collections.unmodifiableCollection(ints);
var l = Collections.unmodifiableList(ints);

System.out.print(a.equals(c) + " ");
System.out.print(a.equals(l) + " ");
System.out.println(c.equals(l));

輸出： false true false
解析： 

// AbstractList
public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

總結