每日面试题推送及讲解-20190410

今日面试题

• HashMap解决hash值冲突的方法
• JDK1.8中HashMap链表长度大于8时将转换为红黑树，这样好处是什么
• 说一说红黑树的性质
• 红黑树跟平衡二叉树有什么区别

上期面试题：

每日面试题推送及讲解-20190409

面试题分析

第一题是对Hash表的考察，哈希表的特点：关键字和它在表中存储位置之间存在一种函数关系。这个函数我们称为为哈希函数。而键(key)经过hash函数得到的结果作为地址去存放当前的键值对(key-value)，可能会发现该地址已经被占用了，于是就会产生冲突。这个冲突就是hash冲突了。一般来说解决Hash冲突有两种方法：链表法和开放地址法。

第二题是对于HashMap的考察，我实习面试那会，面试官对于Map好像是问到最多的，在JDK8之前，HashMap是数组加链表的结构(链表散列)，在一些糟糕的场景下(Hash分布很集中)，链表长度就会比较长，链表过长,就容易导致栈溢出且在随机取数的时候会比较耗时(指针需要一个一个的移动)，所以在JDK8中，当链表的长度大于8的时候，链表会转换为红黑树。

第三题是数据结构的问题，红黑树有如下性质：

• 节点必须是红色或者黑色。
• 根节点必须是黑色。
• 叶节点(NIL)是黑色的。（NIL节点无数据，是空节点）
• 红色节点必须有两个黑色儿子节点。
• 从任一节点出发到其每个叶子节点的路径，黑色节点的数量是相等的。

第四题同样是数据结构的问题，我们知道红黑树属于平衡二叉树，但是它并没有像平衡二叉树(AVL树)一样要求左、右子树高度或节点数之差小于等于1。红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。

面试题答案

面试题详细答案都在题库里面，如果不是最新的题目，大家可以使用题库的搜索功能，来看看吧......