面试：为阿里二面准备添加参考答案（数据结构）

c-rainstorm · c-rainstorm · commit 56e0e4e64fab · 2017-04-03T11:32:18.000+08:00
diff --git a/interview/阿里二面准备.md b/interview/阿里二面准备.md
@@ -17,7 +17,8 @@
     - [计算机网络](#计算机网络)
     - [分布式/集群等高级主题](#分布式集群等高级主题)
     - [技术开放题](#技术开放题)
-    - [参考](#参考)
+    - [题目参考](#题目参考)
+    - [解答参考](#解答参考)
 
 <!-- /TOC -->
 
@@ -26,31 +27,69 @@
 ## 数据结构
 
 1. HashMap的原理，内部数据结构？
-    - （hash 表，数据+链表（1.8后红黑树））
+    - 底层使用哈希表（数组 + 链表），当链表过长会将链表转成 红黑树以实现 O(logn) 时间复杂度内查找
 1. 讲一下 HashMap 中 put 方法过程？
-    - 对 key 得 hashcode 取 hash，问，
+    1. 对 Key 求 Hash 值，然后再计算 下标。
+    1. 如果没有碰撞，直接放入桶中，
+    1. 如果碰撞了，以链表的方式链接到后面，
+    1. 如果链表长度超过阀值（TREEIFY_THRESHOLD == 8），就把链表转成红黑树。
+    1. 如果节点已经存在就替换旧值
+    1. 如果桶满了（容量 * 加载因子），就需要 resize。
 1. HashMap 中 hash 函数怎么是是实现的？ 还有哪些 hash 的实现方式？
+    1. 高 16bit 不变，低 16bit 和高 16bit 做了一个异或
+    1. （n - 1） & hash --> 得到下标
+    1. 还有哪些 Hash 实现方式：可以参考之前的博客 [Effective Java 学习笔记 -- hashCode()](../reading-notes/Effective-Java.md)
 1. HashMap 怎样解决冲突，讲一下扩容过程，假如一个值在原数组中，现在移动了新数组，位置肯定改变了，那是什么定位到在这个值新数组中的位置，
-    - 申请一个更大数组，将原数组的中的数据放到新数组中，引用指向新数组，
-    - HashMap 采用的是 rehash，再散列一次。
+    - 将新节点加到链表后，
+    - 容量扩充为原来的两倍，然后对每个节点重新计算哈希值。
+    - 这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为 <原下标+原容量> 的位置。
 1. 抛开 HashMap，hash 冲突有那些解决办法？
-    - 开放定址，rehash，链地址法，HashMap 使用的这种，建立一个公共溢出区
-1. 针对HashMap中某个Entry链太长，查找的时间复杂度可能达到O(n)，怎么优化？
+    - 开放定址，链地址法
+1. 针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？
+    - 将链表转为红黑树， JDK1.8 已经实现了。
 1. 数组和 ArrayList 的区别；
-1. Arraylist如何实现排序
-1. 如果想实现一个线程安全的队列，可以怎么实现？
+    1. 数组可以包含基本类型和对象类型，ArrayList 只能包含对象类型
+    1. 数组大小固定，ArrayList 大小可以动态变化
+    1. ArrayList 提供了更多的特性（`addAll`、`removeAll`）。
+1. Arraylist 如何实现排序
+    - `Collections.sort(List<T> list)`;
+    - `sort(List<T> list, Comparator<? super T> c)`;
 1. HashMap ，HashTable 区别
 1. HashMap、ConcurrentHashMap 区别。
-    - ConcurrentHashMap 两个hash过程，第一次找到所在的桶，并将桶锁定，第二次执行写操作。
-1. ConcurrentHashMap原理，jdk1.8后有哪些改变（引入CAS等）
-1. TreeMap和TreeSet区别和实现原理
+    - ConcurrentHashMap 两个 hash 过程，第一次找到所在的桶，并将桶锁定，第二次执行写操作。
+1. ConcurrentHashMap原理，jdk1.8 后有哪些改变（引入CAS等）
+1. TreeMap 和 TreeSet 区别和实现原理
+    - `TreeSet` 底层是 `TreeMap`，`TreeMap` 是基于红黑树来实现的。
+1. 如果想实现一个线程安全的队列，可以怎么实现？
 1. 知道 LRU 吗，20分钟基于 HashMap 实现一个 LRU 算法，面试官给个地址，进去写代码，面试官远程看
+    - [如何设计实现一个LRU Cache？](http://yikun.github.io/2015/04/03/%E5%A6%82%E4%BD%95%E8%AE%BE%E8%AE%A1%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AALRU-Cache%EF%BC%9F/)
 1. 二叉树的遍历方式，前序、中序、后序和层序
-    - 二叉树本身就是一个递归的产物，那前序举例，访问根节点，然后左节点，再右节点，如果左节点是一棵子树，那么就先访问左子树的根节点，再访问左子树的左节点，依次递归；而层序，使用队列进行辅助，实现广度优先搜索
+    - 可以再写一篇了。。
 1. 常见的排序算法时间复杂度（排序算法实现也要重点掌握）
+    - 可以再写一篇了。。
 1. 红黑树的特点及相比平衡二叉树的优点（先介绍各自特点）？
+    - 红黑树
+        1. 每个节点要么是红色，要么是黑色。
+        1. 根节点永远是黑色的。
+        1. 所有的叶节点都是空节点（即 null），并且是黑色的。
+        1. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
+        1. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
+    - 平衡二叉树
+        1. 任何节点的两个儿子子树的高度最大差别为一
+    - 红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
 1. B+树的了解
+    - 多分支结构有效降低了树的高度
+    - B 树的各种操作能使 B 树保持较低的高度，从而达到有效避免磁盘过于频繁的查找存取操作，从而有效提高查找效率
 1. Trie-Tree 原理及其应用；
+    - 字典树
+    - 特点
+        1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
+        1. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
+        1. 每个节点的所有子节点包含的字符互不相同。
+    - 核心思想是空间换时间
+    - 应用
+        1. 字符串检索
+        1. 词频统计
 
 ## 算法题（剑指 Offer 上原题不少）
 
@@ -233,7 +272,7 @@
 1. 问我简历上学校 oj 平台这个项目怎么实现1000人并发?并发的性能瓶颈在哪?
     - 因为还没完成，现处于开发阶段，只跟面试官说了下自己的构想，nginx+tomcat集群，性能瓶颈可能出现在网络io和java gc上，然后说了下jvm gc的优化，如何实现session共享。最后我问了下面试官这样设计可以吗，他说这样设计不行可能有问题，没有告诉我问题出现在哪里。
 
-## 参考
+## 题目参考
 
 1. [阿里、百度、腾讯、华为面经（均已拿到offer）](https://www.nowcoder.com/discuss/11495)
 1. [【面经】阿里+百度+CVTE面经合集（offer均已收到）](https://www.nowcoder.com/discuss/5941)
@@ -266,3 +305,11 @@
 1. [西安，美团面经 java](https://www.nowcoder.com/discuss/11319?type=0&order=3&pos=1254&page=1)
 1. [美团补招](https://www.nowcoder.com/discuss/19994?type=2&order=3&pos=11&page=1)
 1. [年级倒数TOP20%的求职经验](https://www.nowcoder.com/discuss/18855?type=2&order=3&pos=44&page=1)
+
+## 解答参考
+
+1. [Java HashMap工作原理及实现 ](http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/)
+1. [红黑树和AVL树的比较 ](http://blog.csdn.net/hustyangju/article/details/27214251)
+1. [从B树、B+树、B*树谈到R 树 ](http://blog.csdn.net/v_july_v/article/details/6530142)
+1. [Trie树（Prefix Tree）介绍 ](http://blog.csdn.net/lisonglisonglisong/article/details/45584721)
+1. [如何设计实现一个LRU Cache？](http://yikun.github.io/2015/04/03/%E5%A6%82%E4%BD%95%E8%AE%BE%E8%AE%A1%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AALRU-Cache%EF%BC%9F/)
