JAVA基础之容器--Map

Map的特点是存放一对"key"-“value”（键值对）。
我们可以通过"key"对象来查找对应的值，因此自然地，为了保证查找结果的唯一性，"key"对象是不可重复的。
Map接口的实现类有HashMap、HashTable、TreeMap、Properties等。

HashMap是Map最常用的实现类。
HashMap底层是一个“位桶数组”，即数组+单向链表的形式，或者说单向链表构成的数组。
数组长度为1的HashMap退化为单个链表。
HashMap通过“哈希算法”获得"key"的哈希值，按照哈希值将"key"-“value"对存储至对应的链表中。
“哈希算法”是为了将存储的"key”-“value"对尽可能散列到“位桶数组”中。
哈希值采用如下算法：hashcode%数组长度。
确保数组长度为2的整数次幂，哈希值采用如下算法提升效率：hashcode&(数组长度-1)。
实际上，JDK对hashcode进行了两次散列处理，具体可查看源码。
存储数据时，先计算"key"对象的hash值，再将包含"key”-"value"对信息的"Entry"对象存储至对应hash值的链表中，如果第一位已经存在元素则存储至第二位，依次类推。
“Entry"对象包含"key”-"value"对、hash值和指向下一个"Entry"对象的引用。

HashTable实际上是实现了同步的HashMap，在需要同步的场景时使用HashTable。
与HashMap较为不同的是，HashTable不允许"key"或"value"为空。

TreeMap是红黑二叉树的典型实现。
一个简单的二叉树模型可以看成是左子树-根节点-右子树的形式，如下图：

其中，左子树的值必须小于根节点的值，右子树的值必须大于根节点的值。
对于一组多个(>3)数据，则会形成排序二叉树，如下图：

可以很明显地看出，其中位于左边的数值总是小于右边的数值。
当然如果仅仅只有上述要求，则二叉树很容易退化成从小到大排列的单向链表。
因此引入平衡二叉树的概念，即左子树高度差与右子树高度差最大为1，否则需要左旋或者右旋重新排序。
平衡二叉树的实现非常麻烦。每次引入节点都需要重新排序，且需要的旋转操作次数不可预知。
JDK提供的TreeMap、TreeSet是红黑二叉树的实现，红黑二叉树有如下特点：
1.每个节点的颜色要么是黑色，要么是红色，且根节点必须是黑色。
2.没有数值的子树必须是黑色且值为null。
3.红色节点的两个子树必须是黑色的。
4.从任一节点出发到最终的子树（包含空子树）的路径中包含的黑色节点数必须相同，这可以很自然地由1-3得出。

TreeMap实际上是排序的Map，效率低于HashMap，用法上基本相同，所以仅在需要排序时采用TreeMap。