今日头条Java实习生视频面试(2018.03.31

题1: 如何设计一个HashMap

先自己说了结构，使用拉链法来解决冲突，有一个Node（单链表）的数组table,还有数组长度一般设置为2的幂次,容量、加载因子和阈值。然后面试官一直没说话，我就继续讲了它的put方法，根据对象的hashcode的值，可以先做一下高位与低位的与操作增大随机性得到hash值。通过hash值与（数组长度-1）相与操作，相当于取模操作来确定在table中的位置。然后通过equals方法确定在链表有无存在，没有存在则添加进链表，已存在的话则更新值。

我说完又是沉默了好几秒，然后不知道是不是网络或是其它原因，视频面试挂断了。然后面试官马上重新发起面试邀请。

问1：如何添加值的？

答1：把以上的put方法又说了一遍，然后又补了可以按照jdk1.8实现，可以在链表超过一定值后，转成红黑树

问2：如果对象更多呢？

答2：对HashMap进行扩容,重新进行放置对象

问3：对象必须重排吗？

答3：举了个例子，在数组长只有16的时候，其中一个对象hash值取模为7，但是在扩容后长度为32，这个对象的hash取模可能为7也可能为23，如果它取模为23的话，再继续放在table的第7个位置也不太合适，get方法也许会找不到对象。

问4：讲讲如何扩容？

答4：HashMap里的对象如果达到阈值的话则进行扩容，阈值是容量*加载因子，table长度一般为以前的俩倍。java中数组长度是固定的，扩容是通过创建一个新数组，将旧数组中的数据复制到新数组中去。

问5：假设你的机子只有4G的内存，目前的HashMap占了2G的内存，那你扩容会出现什么问题？

答5：应该会出现OOM错误的
(2018.04.01更新)我错了，其实只要table数组x2就行了，不需要申请所有对象大小的内存，都是链表存的，链表头存进新table数组就行了，然后重新计算下索引的位置就好了。元素hash值第N+1位为0，不需要进行位置调整。元素hash值第N+1位为1时调整至原索引的两倍位置。谢谢#13的@mask_man的回复

问6：那你有什么解决方案，在扩容的时候不报OOM错误？

答6：1. 先把旧HashMap存在文件里（面试官说在硬盘里太慢了）
2.(本来想着再说个虚拟内存，想想也是硬盘，想了30s左右，就说想不出来了

题2：了解数据库索引、事务吗？讲讲事务吧

说了ACID四个特性，还有事务可能产生的脏读、幻读、不可重复读

问1：知道行锁、表锁和库锁吗？

答1：知道一点，说了幻读需要加表锁，不可重复读需要行锁酱

题3：了解TCP吗？

知道一些，说了tcp是可靠的连接，是传输层的，端对端的，有拥塞管理

问1：比如说我们现在视频面试，它是TCP连接的，它是怎么保证，我现在语音说话，前后俩句中间有停顿，你怎么知道我或者他们是怎么确保我说话中间有没有停顿的呢？
答1：（其实这个问题听得有点懵逼，想确认一下问题是不是说语音的数据包是不是按序组装打包酱紫的？，感觉面试官有点不耐烦），感觉答得很不好

这题我也听傻了，不知道咋理解和描述（也许我听错了也理解错了？如果是这样的话，参考的意义好像也不是很大...可以按照tcp，语音视频传输这个点来复习吧？）(2018.04.01更新

题4：手写代码1

一个线程A一个线程B，线程A输出A，线程B输出B，写代码，让这俩个线程按序输出ABABABABABAB...
(花了一些时间，还是有点懵，没写notify...GG

题5：手写代码2

在以上你写的synchronized void printB方法，有"synchronized void printB"这一个字符串，怎么转置字符串，成为"printB void synchronized"
答：1.使用spilt;(不能使用额外的数组，要空间复杂度为O（1）
2.俩个指针，在字符串尾部，一个指针往前走，遇见空格了，直接输出这两个指针之间的字符（也是不行）
面试官：“谢谢参与”
补题：一种做法：直接反转字符串为"Btnirp diov dezinorhcnys",然后，还是俩个指针，从前面开始，遇见空格了，反转这个字符串。