Map接口、hashMap、平衡二叉树
Map接口
- Map提供了一种映射关系，其中的元素是以键值对（key-value）的形式存储的，能够实现根据key快速查找value
- Map中的键值对以Entry类型的对象实例形式存在
- 建（key值）不可重复，value值可以重复，一个value值可以和很多key值形成对应关系，每个建最多只能映射到一个值。
- Map支持泛型，形式如：Map<K,V>
hashMap
- HashMap是基于数组来实现哈希表的，数组就好比内存储空间，数组的index就好比内存的地址；
- HashMap的每个记录就是一个Entry<K, V>对象，数组中存储的就是这些对象；
- HashMap的哈希函数 = 计算出hashCode + 计算出数组的index；
- HashMap解决冲突：使用链地址法，每个Entry对象都有一个引用next来指向链表的下一个Entry；
- HashMap的装填因子：默认为0.75；
基本上HashMap就像这样：
平衡二叉树
平衡二叉树又名红黑树，是有序二叉树的一种。具有有序二叉树的所有特点，其任意一分支长度不会超过另一支的二倍。
- 每个节点不是红色就是黑色的
- 根节点总是黑色的
- 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）,(也就是从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）
参考链接