Q:Set Map 的实现
A:Set就是用Map实现的，Map的Value设置为Present的一个占位符实现。
Q：Map有什么实现
A:LinkedHashMap，HashMap，TreeMap
Q：讲讲LinkedHashMap。
A:就是在HashMap的基础上维护一个List，该list的顺序是以put的顺序为准的。使用场景常用来作为简单的缓存，使用LRU算法淘汰entry
Q:TreeMap什么实现？
A:RB树，（然后说自己没看过JDK的RB源码，但2年前看过C++的STL中RBtree的实现，以及算法导论），说了RBtree的性质什么非红即黑，root和leaf皆为black，Red的子节点必须为Black，所有路径Black数目系统，有四种旋转方式。
Q:哪四种？
A:不会，记不得了。。。
Q:RBtree复杂度？
A:log2N
Q:why？
A：所有路径最短为n个black node，最长为2n个node（n个black+n个Red）。
Q:知道还有哪些平衡数吗？
A:B+，AVL。
Q:下一题是。。。
A:大人，我还没说HashMap呢。
Q:问烂了的东西，没必要浪费时间。。。（一脸不屑）
Q:用过多线程，知道几种锁？
A:实现Lock的锁，主要以ReentrantLock为主，synchronized，还可以使用volatile的现行发生语义。
Q:知道ConcurrentHashMap吗？
A:知道，Java1.7和Java1.8实现不一样。你是问？
Q：1.8，如何实现线程安全的？都是加锁吗？
A:不是呢，初始化的时候以及如果bucket为null的情况，那么这个bucket第一个element不会加锁，会使用CAS算法初始化和赋值。如果已有元素，需要解决hash冲突，会使用开链法，这里和ThreadLocalMap不一样，ThreadLocalMap使用的是线性探测法（此处暗示面试官，ThreadLocalMap源码我也看过哦，并引导面试官往这上面问，可惜没中计）。（顿了顿，看面试官没追问，继续往下）。在使用开链法的时候，会使用synchronized锁，此处和1.7不同，1.7使用Lock（暗示面试官1.7我也hold的住）。此时锁的粒度为bucket，并且在ele的数目超过8时会转换为RBtree。
Q:为什么粒度为bucket？
A:因为锁的粒度越小，其他阻塞的几率越小，相应的并发度就越好。但是粒度太小，有时候也有缺点，就是容易出现死锁问题。比如Mysql中InnoDB里默认为行锁就容易死锁，而MyISAM为表锁就基本不会死锁，还是看业务权衡吧。在举个例子，我们都知道Intel CPU处理器中的高速缓存是以缓存行为最小单位分配的（64B），在多处理器并发是，为了解决缓存一致性问题，在锁的时候也是一缓存行为单位。所以在LinkedTransferQueue的实现中，会对Value值进行填充，直到为64B，以此达到每个节点都可以并发访问的结果，而不会因为一个CPU在access一个节点时，导致紧邻的节点不能用。并且1.7的实现也是将整个hash分为16个segment，来减小锁的粒度。
Q:问了下数据库优化，最近一次怎么做的SQL调优。
A:讲了下选择性，聚簇索引，二级索引，回表查询，随机io，InnoDB使用蒙特卡罗算法进行optimization的过程。扯了下MRR，三星索引的概念。以及使用explain，profile，optimizer trace来作为参考。（内容太多就不写了，此处推荐一些Mysql的学习资料，InnoDB技术内幕，高性能Mysql，阿里数据库内核月报,美团点评沙龙，何登成的blog，彭利勋的blog）
Q：解释下RESTful协议？
A: 百度的到就不写了
Q:RPC用过哪些？知道原理吗？
A：用过dsf，隔壁部门自己造的烂轮子，三天两头出问题，目前已弃置不用，dsf原理没兴趣看。不过准备看下thrift。
Q：安利了我一下GO RPC。然后问了下算法题。
A:一个List<Raw> src，结构为
class Raw {
String id;
String parentId;
}
转换为树，
class TreeNode {
String id;
List<TreeNode> children;
}
实现函数TreeNode convert(List<Raw> src) {}
