教妹学 Java：大有可为的集合(3)

03、二哥，HashMap 和 TreeMap 有什么区别啊？

三妹，提问题越来越有艺术了啊？继续听哥给你慢慢讲啊。

HashMap 存储的是键值对，其键是一个哈希码（Hash 的直译，也称作散列）。来看源码。

public class HashMap<K,V>
{
    transient Node<K,V>[] table;
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
    public HashMap(int initialCapacity, float loadFactor) {
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
}      

1）table 是一个 Node 数组，而 Node 是一个单向链表（只有 next）。HashMap 的键值对就存储在 table 数组中。

2）loadFactor 就是大名鼎鼎的加载因子，默认的加载因子是 0.75, 据说这是在时间和空间成本上寻求的一种折衷。

3）initialCapacity 就是初始容量，默认为 16。

4）threshold 是 HashMap 的阈值——判断是否需要对 HashMap 进行扩容，threshold 的值 = 容量 * 加载因子，当 HashMap 中存储的数据数量达到 threshold 时，就需要将 HashMap 的容量加倍。

“初始容量” 和 “加载因子”对 HashMap 的性能影响颇大。容量是 HashMap 中桶（见下图）的数量，初始容量只是 HashMap 在创建时的容量。加载因子是 HashMap 在其容量自动增加之前可以达到多满的一种尺度。

TreeMap 存储的是有序的键值对，基于红黑树（Red-Black tree）实现。可以在初始化的时候指定键位的排序方式，如果没有指定的话就根据键位的自然顺序进行排序。来看源码。

public class TreeMap<K,V>
{
    private final Comparator<? super K> comparator;
    private transient Entry<K,V> root;
    private static final boolean RED   = false;
    private static final boolean BLACK = true;
    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
    }
}      

1）root 是红黑树的根节点，是一个 Entry 类型（按照 key 进行排序），包含了 key（键）、value（值）、left（左边的子节点）、right（右边的子节点）、parent（父节点）、color（颜色）。

2）comparator 是红黑树的排序方式，是一个 Comparator 接口类型，该接口里面有一个 compare 方法，有两个参数 T o1 和 T o2，是泛型的表示方式，表示待比较的两个对象，该方法的返回值是一个整形， o1大于o2，返回正整数； o1等于o2，返回0；o1小于o3，返回负整数。

总结一下就是，HashMap 适用于在 Map 中插入、删除和定位元素；TreeMap 适用于按自然顺序或自定义顺序遍历键（key）。

04、二哥，再讲讲二分查找呗！

三妹，没有任何问题，包在我身上。不过，在讲之前，你能先去给哥泡杯咖啡吗？

通常，我们从数组中查找一个元素时，需要对整个数组进行遍历。但如果这个数组是排序过的，就可以进行二分查找了。

二分查找的方式：

第一步，将数组中间位置上的元素与要查找的对象进行比较，如果两者相等，则查找成功；否则进行第二步。

第二步，利用中间位置将数组分割成前、后两个子集。

第三步，比较要查找的对象与中间位置上的元素，如果前者大于后者，则在后面的子集中按照之前的方式进行查找；否则，在前面的子集中按照之前的方式进行查找。

这样做可以将查找范围缩减一半，大大的减少了查询的次数。

Collections 类的 binarySearch() 方法实现了二分查找这个算法，可以直接使用，前提是先要排序，否则将返回 -2。源码如下。

private static <T>
int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
    int low = 0;
    int high = list.size()-1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = list.get(mid);
        int cmp = midVal.compareTo(key);
        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found
}      

我们来测试一下。

List<String> list1 = new ArrayList<>();
list1.add("沉");
list1.add("默");
list1.add("王");
list1.add("二");
Collections.sort(list1); // 先要排序
System.out.println(Collections.binarySearch(list1, "王")); // 2      

05、故事的未完待续

“二哥，终于讲完《集合》了，喝口咖啡吧！”三妹的态度很体贴。

“谢谢。”

“二哥，如果这篇文章继续遭受到批评，你会不会气馁啊？”三妹眨了眨眼睛，继续问我，我看到她长长的睫毛，真的很美。

“嗯，对于作者来说，当然希望文章能够得到正面的反馈，如果是负面的反馈，那也在我的意料之中。”

“为啥？”三妹很好奇。

“《教妹学 Java》是一种创新的写作手法，市面上还没有，新鲜、有趣的事物总需要一段时间才能被大众接受，否则也就不叫创新了。”

“二哥，为你的勇气点赞！”看到三妹很为我骄傲的样子，我的心里盛开了一朵牡丹花。