网易互娱秋招
https://www.nowcoder.com/discuss/458297?source_id=profile_create&channel=1009
网易互娱内推码(T2qz79)
投递简历网站 https://game.campus.163.com
是否有内推一定要选择是,投递成功后无法修改
网易互娱内推福利:有笔试的岗位,简历免筛选,直通笔试
没有笔试的岗位,简历优先筛选
网易互娱投递时间 :7月13日-9月25日
1、Hash的概念
2、Hash冲突
3、你认为好的Hash算法的点应该有哪些?
(1)效率得高,做到长文本也能高效计算出Hash值
(2)根据Hash值不能逆推出原文
(3)两次输入,如果有一点不同也得保证Hash值是不同的
4、HashMap的存储结构长啥样?
JDK1.8:
(1)数组+链表+红黑树构成,每个数据单元为一个Node结构,Node结构中有key字段、value字段、next字段、hash字段
(2)next字段就是发生Hash冲突的时候,当前桶位中的Node与冲突Node连接成一个链表所需要的字段
JDK1.7:
开放地址法
线性开放地址法 平方开放地址法 双散列开放地址法 拉链法
5、如果创建HashMap的时候没有指定HashMap散列表的长度,初始长度为多少?
在JDK 8中,关于默认容量的定义为:static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16 ,其故意把16写成1<<4,就是提醒开发者,这个地方要是2的幂。
(1)为啥用位运算呢?直接写16不好么?
这样是为了位运算的方便,位与运算比算数计算的效率高了很多,之所以选择16,是为了服务将Key映射到index的算法。
(2)那为啥用16不用别的呢?
因为在使用不是2的幂的数字的时候,Length-1的值是所有二进制位全为1,这种情况下,index的结果等同于HashCode后几位的值。这个值既不能太小,也不能太大。
太小了就有可能频繁发生扩容,影响效率,太大了又浪费空间,不划算。
只要输入的HashCode本身分布均匀,Hash算法的结果就是均匀的。
6、散列表是New HashMap()的时候创建的,还是什么时候创建的?
7、负载因子默认是多少,有啥作用?为什么负载因子为0.75?什么时候进行扩容(resize)?
(1)默认为0.75,用于计算扩容阈值
(2)loadFactor是负载因子,表示HashMap满的程度,默认值为0.75f,设置成0.75有一个好处,那就是0.75正好是3/4,而capacity又是2的幂。所以,两个数的乘积都是整数。
(3)影响扩容主要有两个因素:
Capacity:HashMap当前长度。
LoadFactor:负载因子,默认值0.75f。
8、扩容?它是怎么扩容的呢?
分为两步
(1)扩容:创建一个新的Entry空数组,长度是原数组的2倍。
(2)ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。
为什么要重新Hash呢,直接复制过去不香么?
是因为长度扩大以后,Hash的规则也随之改变。
9、链表转化为红黑树的条件
(1)链表长度达到8
(2)当前散列表长度达到64
10、Node对象里面的hash字段的值是key对象的hashcode的返回值吗?
11、为啥我们重写equals方法的时候需要重写hashCode方法呢?你能用HashMap给我举个例子么?
因为在java中,所有的对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode,这两个方法都是用来比较两个对象是否相等的。
在未重写equals方法我们是继承了object的equals方法,那里的 equals是比较两个对象的内存地址,显然我们new了2个对象内存地址肯定不一样
比如发生Hash冲突的时候,我们去get,他就是根据key去hash然后计算出index,找到了2,那我怎么找到具体的”电脑“还是”脑电“呢?
12、HashMap的put数据的流程
13、为什么java8以后链表数据超过8以后,就改成红黑树存储?
14、Hashmap的结构,1.7和1.8有哪些区别?
(1)JDK1.7用的是头插法,而JDK1.8及之后使用的都是尾插法,那么他们为什么要这样做呢?
因为JDK1.7是用单链表进行的纵向延伸,当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法,能够避免出现逆序且链表死循环的问题。
15、首先HashMap是线程不安全的,其主要体现在哪里?
(1)在jdk1.7中,在多线程环境下,扩容时会造成环形链或数据丢失。
16、红黑树的定义:
- 每个节点要么是红色,要么是黑色;
- 根节点永远是黑色的;
- 所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点);
- 每个红色节点的两个子节点一定都是黑色;
- 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;
性质 3 中指定红黑树的每个叶子节点都是空节点,而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点,因此遍历红黑树时将看不到黑色的叶子节点,反而看到每个叶子节点都是红色的。
性质 4 的意思是:从每个根到节点的路径上不会有两个连续的红色节点,但黑色节点是可以连续的。
因此若给定黑色节点的个数 N,最短路径的情况是连续的 N 个黑色,树的高度为 N - 1(此次树高度的基数从0开始);最长路径的情况为节点红黑相间,树的高度为 2(N - 1) 。
性质 5 是成为红黑树最主要的条件,后序的插入、删除操作都是为了遵守这个规定。红黑树并不是标准平衡二叉树,它以性质 5 作为一种平衡方法,使自己的性能得到了提升。
BST(二分查找数)存在的主要问题是,数在插入的时候会导致树倾斜,不同的插入顺序会导致树的高度不一样,而树的高度直接的影响了树的查找效率。理想的高度是logN,最坏的情况是所有的节点都在一条斜线上,这样的树的高度为N。
红黑树的定义中的这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的(平衡的复杂度为O(lgN),简略可以说红黑树也是O(lgN)),严格的所需要数学证明。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
简单的说,也就是红黑树查找效率比二叉查找树效率高!
全部评论
(1) 回帖