【Java基础】HashMap、TreeMap、都用了红黑树

引子

昨天模拟面试，面试官问到了 哈希map 和 treeMap 我说都是使用了 红黑树 问我有什么区别 还有复杂度 稍微一深入讨论 我就废掉了 先亡羊补牢一下

文章目录

• • 引子
  • 1)、使用层次上的区别：
  • • HashMap：
    • TreeMap：
  • 2)、底层数据结构
  • • HashMap：
    • HashTree：
  • 总结：
  • • 红黑树特征：
    • • 红黑树左旋、右旋：
  • 补充
  • • 复杂度总结

1)、使用层次上的区别：

HashMap：

1. 数组 链表存储key-value，1.8加入红黑树(优化链表查找过长的问题)
2. 允许null作为key和value，key不可以重复，value允许重复
3. 不能保证插入顺序是有序的
4. 线程非安全

TreeMap：

1. 基于红黑二叉树的NavigableMap的实现
2. 不允许null，key不可以重复，value允许重复
3. 元素应当实现Comparable接口或者实现Comparator接口，元素进行自动排序
4. 线程非安全

2)、底层数据结构

HashMap：

1.8之前数组 链表，1.8加入红黑树

HashTree：

实现了SotredMap接口，它是有序的集合。 而且是一个红黑树结构，每个key-value都作为一个红黑树的节点。 如果在调用TreeMap的构造函数时没有指定比较器，则根据key执行自然排序

总结：

红黑树特征：

1、每个节点要么是红色，要么是黑色； 2、根节点永远是黑色的； 3、所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）； 4、每个红色节点的两个子节点一定都是黑色； 5、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

红黑树左旋、右旋：

代码语言：javascript复制

右旋——自己变为左孩子的右孩子；
左旋——自己变为右孩子的左孩子。

补充

Java集合关系图

复杂度总结

容器名称			存储形式	复杂度
查询	插入
Map		HashMap	哈希表	O(1)	O(1)
	NavigableMap	TreeMap	红黑树	O(log n)	O(log n)
Collection	List	ArrayList	静态数组	O(1)	O(n)
		LinkedList	双向链表	O(n)	O(n)
	Set	HashSet	HashMap	O(1)	O(1)
		TreeSet	TreeMap	O(log n)	O(log n)

hashmap 编程算法 数据结构

0 人点赞