Java数据存储：集合框架与泛型拓展（一）Map

Map

HashMap和TreeMap

1. 实现
   TreeMap：SortMap接口，基于红黑树
   HashMap：基于哈希散列表实现
2. 存储
   TreeMap：默认按键的升序排序
   HashMap：随机存储
3. 遍历
   TreeMap：Iterator遍历是排序的
   HashMap：Iterator遍历是随机的
4. 性能损耗
   TreeMap：插入、删除
   HashMap：基本无
5. 键值对
   TreeMap：键、值都不能为null
   HashMap：只允许键、值均为null
6. 安全
   TreeMap：非并发安全Map
   HashMap：非并发安全Map
7. 效率
   TreeMap：低
   HashMap：高

红黑树

从上而下，比父节点大的放在左边，比父节点大的放在右
祖父G- ganderfather
父母P-Parents
叔叔U- uncle
兄弟B- brother
根 R-root
当前新增节点C-Current

根据x轴递增的规律来排序

1. 红黑树特性：
   1. 每个节点都有颜色，不是红色就是黑色
   
   2. 根节点是黑色
   3. 每个叶子节点（NIL）都是黑色的虚点（值）null
   4. 每个红色节点的子节点一定是黑色的（红色节点一定有黑色的父节点）
   5. 任意节点到每个叶子节点(虚拟的NIL)的路径都包含相同数量的黑节点
      
      红黑树的平衡性
      1. 红黑树是一种含有红黑节点的并能自平衡的二叉查找树。
         a. 包含变色，旋转。旋转包含左旋和右旋。
         b. 旋转节点按照子节点旋转（子节点为圆心）。
      2. 红黑树是非完美二叉平衡查找树，是完美黑色二叉查找树