🔥面试高频：跳表，红黑树，b+树，hashmap的区别？

1.为什么mysql使用b+树而不是红黑树、跳表或者hashmap？

• 1.1、不使用红黑树是因为：
  • 1）在增删改查的过程中，时间复杂度为log2n，而b+是logmN，体现在内存和磁盘的IO上，代价比较大。
  • 2）特别是插入的时候，红黑树需要进行节点颜色调整，对于频繁的插入而言，这是一个耗时的过程，而b+树仅仅是页分裂问题。另外从并发交付来说，要么线程不安全，要么加锁虽然线程安全，但是牺牲了效率。
  • 3）区间查找而言，b+树的叶子节点带有双向链表，因此比较方便。对于红黑树而言，虽然可以实现，比如通过中序遍历的方式，但是实现起来比较复杂。
• 1.2、不使用hashmap是因为
  • 1）假设瓶颈不在hash数组上（hashmap由数组加链表构成），一方面，对于庞大数据量的链表来说，查找的时间复杂度为O（n），
  • 2）另一方面从磁盘IO性能考虑，链表足够长，频繁的io会导致极差的性能。
  • 3）对于区间查找，可行性为0。
• 1.3、不使用跳表是因为
  • 1）虽然在区间查找上两者不相上下，如果纯粹基于内存工作，那就是redis。两者的主要区别，那就是一个是关系型，另一个是非关系型，redis是基于某个key进行排序构造的，如果像mysql哪样建立二级索引，那么每一个都是“聚簇索引”，得不偿失，维护也麻烦（就是说跳表无法解决索引问题）。
  • 2）还是数据关系型的问题，虽然说跳表这个结构也可以以Json格式来存储数据库的行数据，但是类似主外键关系、模糊查找等功能，无法提供或者提供起来较为繁琐。
  • 3）如果考虑到足够大的数据，大到需要使用硬盘的话，内存和磁盘进行io的内容会是什么？是跳表的每一层数据，前几层可能还好，越往下，可能不是一次页交换可以容纳下的，那么跳表在查找上的优势尽失，反观mysql，每次交换出来的非叶子节点都是索引，可查找范围大，io次数少，性能高。

2.为什么redis使用跳表而不是红黑树或者hashmap？

• 2.1、由上面分析可知，红黑树在内存工作效率更高，但是同样基于内存的redis为什么不用红黑树，区别在于红黑树范围查询太费劲，插入元素时进行的节点颜色调整太费解，同样的操作，跳表仅仅需要更新前后下三个指针即可，而且，红黑树这样做来保持平衡带来的查找优势对跳表来说并不明显。
• 2.2、不使用hashmap，也是因为链表的操作太费时，远不如跳表这种链表的折半查找来的快。
• 2.3、不使用B+树的原因是：B+树的数据存在叶子结点，而跳表存在于每一个节点，因此不必要查询到叶子结点才拿到数据，维护非叶子结点的分裂和合并也是不小的开销（其实跳表删除结点，也需要继续往下层进行删除，开销也不小）

3.为什么重写equals以后还要重写hashcode

• 1、hashcode和equals都是用于判定两个对象是否相等，hashcode是根据某种hash函数将对象转换成一串数字，equals是根据某些特性，来判定两个对象是否相等。
• 对比两个对象相等，最快的方法是对比hashcode，因为不同的对象，hashcode一定不同，当hashcode相等的时候，再用equals来再次判断一下。
• 不重写hashcode，可能会导致理论上应该相等的值，在map操作时需要进行覆盖的值，实际上因为hashcode不同，而导致重复。因为hashcode未重写前，部分依据是地址，而对于地址不同的，那么hashcode一定不同（相同的值仅仅因为多new了一次，而导致不相等）
• 但是对于不太好的重写，那么存在这样一种可能：两个不同的对象，按照重写的hashcode，巧合性的相等，equals也相等，新值覆盖了旧值。
• 参考博客：帮你搞懂Java中重写equals方法为什么要重写hashcode方法？