数据库高级 III

数据库高级 III

二叉排序树在极端情况下存在的问题

• 二叉排序树在极端情况下会产生失衡二叉树
  

• 失衡二叉树其实是不希望存在的，因为它失去了二叉排序树的查询优势，现在这种失衡二叉树的查询效率和单向链表一样，此时它就是单向链表

• 数据结构在设计时已经考虑到了这个问题，所以出现了对二叉排序树优化，产生了2种新的数据结构。这2种数据结构是基于二叉排序树的，保留了二叉排序树的优势，且避免了缺陷。

• 分别是

  AVL树 -- 平衡二叉树
  	AVL树通过旋转（左旋/右旋）来保证二叉排序树的平衡状态，AVL树会保证树的左右子树高度差始终是<=1,AVL树达到的平衡状态是绝对平衡（左右子树的高度差<=1）
  1
  2

  

红黑树

• 定义

  红黑树是实现了自平衡的二叉排序树，红黑树达到的是相对平衡状态，而不是绝对平衡状态。相对平衡状态是指左右子树的高度差可以大于1（2，3，。。。），红黑树中所有节点的颜色要么是黑色要么是红色。
  1

• 红黑树是怎么实现平衡状态的

  通过旋转和调整节点的颜色,两种操作来保证树的平衡状态.
  1

• 红黑树中节点的颜色

  有两种节点颜色固定
  1. 根节点必然是黑色的
  2. 新添加的节点颜色必然是红色,不过添加成功后,节点的颜色可能被改变
  1
  2
  3

• 红黑树保证平衡的规则

  红黑树是通过旋转（左旋，右旋）和改变节点的颜色来保持树的平衡的
  红黑树满足以下5大原则，则认为红黑树达到了相对平衡的状态
  1. 节点是红色或黑色
  2. 根节点是黑色的
  3. 所有叶子节点是黑色（叶子节点是NIL节点）
  4. 每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）
  --红色节点不能连续出现
  5. 从任意一个节点到其每个叶子所经历的简单路径上包含的黑色节点的个数相同（简称黑高相同）
  1
  2
  3
  4
  5
  6
  7
  8

• 应用: TreeMap

  TreeMap其实就是红黑树,其实现即为红黑树的实现
  1. 通过debug观察红黑树数据结构
  2. 输出引用,观察toString是如何做的?
      结果是根据key升序排列的结果,即toString中使用了中序遍历.
  1
  2
  3
  4

• 应用2: TreeSet

  TreeSet底层调用了TreeMap,其实质为向map中key的那一列保存元素.所以TreeSet也是红黑树的应用
  1

• 所有的set和map都有这样的关系

  HashSet -- HashMap  数据结构为散列表，输出应用，得到的结果为无序结果
  TreeSet -- TreeMap  数据结构为红黑树  输出引用，得到的结果为中序遍历的结果 -- 升序排列
  LinkedHashSet -- LinkedHashMap  输出应用，得到的结果为有序的结果
  1
  2
  3

• set集合：不可重复集，不要说是无序的，因为实现类不同，set集合可能是有序的，可能是排序的

散列表

• 应用类：HashMap

• hash: 音译后是哈希，翻译 后是散列

• 散列表是一种数据结构，这种数据结构的实现：

  JDK1.8之前，散列表的数据结构为：数组+链表
  从JDK1.8开始，散列表的数据结构为：数组+链表+红黑树
  1
  2

面试题:HashMap,HashTable,ConcurrentHashMap的区别

java.util.concurrent  --JUC包
1. HashMap是非线程安全的散列表;而HashTable和ConcurrentHashMap是线程安全的散列表
2. HashMap的key和value均允许为null,而Hashtable和ConcurrentHashMap的key和value均不允许为null
3. HashTable和ConcurrentHashMap保证线程安全的机制是不同.
    HashTable是通过给整张散列表加锁的方式来保证线程安全,这种方式可以保证线程安全,但是并发执行效率低下.
    ConcurrentHashMap在JDK1.8之前采用分段锁机制来保证线程安全的,这种方式可以在保证线程安全的同时一定程度上提高并发执行效率.当多线程向不同的segment上并发执行添加操作时,此时两个线程就可以完全并发.这种情况下的并发执行效率就会得到提高.此时若多线程向同一个segment上的不同散列桶进行添加元素时,不能实现并发,但是理论上应该可以并发.
    从JDK1.8开始,ConcurrentHashMap数据结构发生了改变,和JDK1.8中的HashMap数据结构一致,均为数组+链表+红黑树.其保证线程安全的机制为:
	 当多线程并发向同一个散列桶添加元素时
		若散列桶为空,此时使用CAS来保证线程安全
		若散列桶不为空,则向该散列桶的头结点/根节点加锁,从而保证线程安全
1
2
3
4
5
6
7
8
9
10

JDK1.8之前,ConcurrentHashMap采用分段锁机制保证线程安全

ConcurrentHashMap在JDK1.8中的数据结构与保证线程安全的方式

从JDK1.8开始,其数据结构发生了改变,数据结构和JDK1.8中的HashMap保持一致,均为数组+链表+红黑树
其保证线程安全的方式为:乐观锁(CAS)+synchronized
1
2

面试题: ==和equals的区别

==:两侧可以是基本数据类型,此时用于比较数值是否相等;也可以是引用类型,此时比较两个引用是否指向同一个对象
equals():是Object类提供的方法,用于比较对象是否相等,在Object类中,其作用等同于==,都是比较对象的地址是否相等;java强烈建议在子类中重写equals方法,让对象之间的比较更具有实际逻辑意义(即可以根据内容判断对象是否相等)
1
2

我是将军；我一直都在，。！