[数据结构与算法]List、Set 和 Map小总结

List 集合

List 集合常用的有两种，ArrayList 和 LinkedList。

ArrayList

ArrayList 使用的是数组作为底层数据结构。
ArrayList 默认最小容量为10，如果创建对象时传入的容量值大于10，则使用大的容量。数组扩容为原先数组的1.5倍。

int newCapacity = oldCapacity + (oldCapacity >> 1);

数组的最大容量为 Integer.MAX_VALUE - 8。

一些虚拟机在数组中保留一些头字，如果设置最大值会 OOM。

LinkedList

LinkedList 在插入数据时会构建尾插链表（双向链表）。

		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++;

List 总结

List 保证了数据的插入顺序，可以有重复数据。

ArrayList 底层是数组，插入/删除数据慢，通过索引查询数据快。

LinkedList 底层是尾插链表（双向链表），插入/删除数据快，查询数据慢。

List 遍历方式：

1. 通过 for 循环下标。
2. 增强 for 循环，forEach。
3. iterator 迭代器。
4. spliterator 迭代器，forEachRemaining()。

Set 集合

Set 集合常用的有：HashSet、LinkedHashSet 和 TreeSet。

HashSet

底层就是 HashMap，构造器中会创建 HashMap 对象，操作都是调用 HashMap 的方法。

LinkedHashSet

LinkedHashSet 除了重写了 spliterator 方法，其他全部继承于 HashSet 。
因为重写了 spliterator 方法，遍历能够会保证插入顺序。

TreeSet

底层TreeMap，很多的方法都基于 TreeMap的方法实现（调用 TreeMap 的方法）。
TreeSet 初始化创建 TreeMap对象。

注意：如果使用 TreeSet，泛型类中必须实现 Comparable 接口，或定义外部比较器。

Set 总结

Set 保证数据的唯一性，但不会保证顺序性。

HashSet 插入/查询/删除快。

LinkedHashSet 有序（时间顺序）。

TreeSet 保存比较器大小顺序。底层红黑树。

Set 遍历方式

1. 增强 for 循环，forEach。
2. iterator 迭代器。
3. spliterator 迭代器，forEachRemaining()。

Map 集合

Map 常用的有：HashMap、LinkedHashMap 和 TreeMap。

HashMap

HashMap理解。

LinkedHashMap

继承了 HashMap，初始化时会创建 HashMap对象，很多方法直接 super(参数…)。

accessOrder参数来标志记录插入顺序。accessOrder 都被设置为 false。

TreeMap

底层红黑树。

Map 总结

Map 存储一组键值对对象，无需且唯一的数据。

HashMap key 无序且唯一。

LinkedHashMap key 有序（插入次序），唯一。

TreeMap key 有序（比较器顺序）,唯一。

Map 遍历方式：

1. 获取到所有的 key 来遍历所有的 value。
2. 使用Iterator迭代器迭代。
3. 增强for 循环 forEach，get方式，不建议使用。
4. Map接口中默认方法（map.forEach）。
5. 使用 entrySet。

	/**
     * 获取到所有的key和所有的value
     * @param hm
     */
    private static void method1(HashMap<String, Integer> hm) {
        // 获取所有key
        Set<String> keys = hm.keySet();
        for (String key : keys) {
            System.out.println(key);
        }
        Collection<Integer> values = hm.values();
        for (Integer value : values) {
            System.out.println(value);
        }
    }

    /**
     * 使用Iterator迭代器迭代
     * @param hm
     */
    private static void method2(HashMap<String, Integer> hm) {
        Set<Map.Entry<String, Integer>> entries = hm.entrySet();
        Iterator<Map.Entry<String, Integer>> it = entries.iterator();
        while (it.hasNext()) {
            Map.Entry<String, Integer> entry = it.next();
            System.out.println(entry);
        }
    }

    /**
     * 通过get方式 不建议使用
     * @param hm
     */
    private static void method3(HashMap<String, Integer> hm) {
        Set<String> keys = hm.keySet();
        for (String key : keys) {
            Integer value = hm.get(key);
            System.out.println(key + ":" + value);
        }
    }

    /**
     * Map接口中默认方法
     * @param hm
     */
    private static void method4(HashMap<String, Integer> hm) {
        hm.forEach((key, value) -> {
            System.out.println(key + ":" + value);
        });
    }

    /**
     * 使用entrySet
     * @param hm
     */
    private static void method5(HashMap<String, Integer> hm) {
        Set<Map.Entry<String, Integer>> entries = hm.entrySet();
        for (Map.Entry<String, Integer> enter : entries) {
            System.out.println(enter);
        }
    }