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》是一种创新的写作手法，市面上还没有，新鲜、有趣的事物总需要一段时间才能被大众接受，否则也就不叫创新了。”
“二哥，为你的勇气点赞！”看到三妹很为我骄傲的样子，我的心里盛开了一朵牡丹花。
