常见 Java 容器对比

线索：

1. 对比 HashMap、HashTable、TreeMap、LinkedHashMap

2. 对比 HashSet、TreeSet、LinkedHashSet

3. Map 的四种遍历方式

4. 散列表的应用：word 拼错错误功能

1. 对比 HashMap、HashTable、TreeMap、LinkedHashMap

都是 Map 的实现，以“键值对”形式存取。

HashTable 是线程安全的，但里边都是类似 public synchronized V get(Object key) 的实现，不支持高并发，如果有线程安全的需求，可以使用 ConcurrentHashMap

HashMap 是线程不安全，是大多数场景的首选。散列表的 put、get 的时间复杂度是 O(1)

TreeMap 底层基于红黑树，因此 get、put、remove 之类的操作的时间复杂度是 O(logN)。TreeMap 是一种有序集合，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来判断// Comparable。

LinkedHashMap 是 HashMap 的子类，它也保证某种顺序，即遍历顺序按 插入顺序 或 访问顺序。其中，put、get、compute 等，都算“访问”。此外，使用 LinkedHashMap 可以轻松实现 LRU 缓存淘汰算法。比如，我们构建一个空间占用敏感的资源池，希望可以自动将最近不常被访问（LRU）的对象释放掉，这就可以利用 LinkedHashMap 提供的机制来实现。

2. 对比 HashSet、TreeSet、LinkedHashSet

Set 不允许重复元素。所谓的不重复、唯一性，指的是不存在两个对象 equals 返回 true，不重复也是 Set 和 List 最明显的差别。在需要保证元素唯一性的场景下，可以使用 Set 集合。

HashSet 是 HashMap 的马甲；TreeSet 是 TreeMap 的马甲；LinkedHashSet 是 LinkedHashMap 的马甲。因此讨论 Set 类的性能，实际上是谈论 Map 类的性能。

以 HashSet 为例：

// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();
/** * Adds the specified element to this set if it is not already present. * More formally, adds the specified element {@code e} to this set if * the set contains no element {@code e2} such that * {@code Objects.equals(e, e2)}. * If this set already contains the element, the call leaves the set * unchanged and returns {@code false}.public boolean add(E e) {    return m.put(e, PRESENT)==null; // 这里的m其实就是HashMap或TreeMap}

3. Map 的四种遍历方式：entrySet()、iterator、keySet()、values()

values 返回的是 v 的集合： Collection<V> values(); 主要用以单遍历 value，而不要 key

Iterator<Map.Entry<String, String>> iterator = hashMap.entrySet().iterator();while (iterator.hasNext()) {  Map.Entry<String, String> entry = iterator.next();  System.out.println(entry.getKey() + ":" + entry.getValue());}

4. word 拼错错误功能，散列表的应用。

使用 word 时，假设你有一个单词拼错了，比如 appla，word 会以红色波浪线的形式提醒你“拼写错误”。这个功能的实现就用到了散列表。

常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就 20MB。完全可以放到内存里。

我们用散列表来存储整个英文单词词典，当用户输入某个英文单词时，我们拿着用户输入的单词到散列表中查找，如果找到则拼写正确；反之，则可能拼写有误。