collection和collections的区别
map遍历过程中删除数据会发生什么如何解决
1，Android为什么使用Dalvik 不用JVM Dalvik和ART的演变
2.双重锁单例 volitile关键字，sync锁
3.binder通信流程，跨进成通信方式，binder的大小
4.代理模式的实现
5.热修复原理 （双亲委托）。

oppo的面试题
1.tcp怎么保证数据传输的可靠性
2.多进程的好处和缺点
3.Service和Thread的区别
4.Socket有什么优化点
5.偏向锁的实现原理
6.CAS的实现原理
7.设计模式的设计原则
8.jvm的多线程机制
9.rsa加密原理
10.hashmap和treemap有什么区别
HashMap：基于哈希表实现 .优化HashMap空间的使用，可以调优初始容量和负载因子。适用于在Map中插入、删除和定位元素。
TreeMap：基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。适用于按自然顺序或自定义顺序遍历键(key)。

1.为什么ThreadLocalMap使用弱引用存储ThreadLocal？

假如使用强引用，当ThreadLocal不再使用需要回收时，发现某个线程中ThreadLocalMap存在该ThreadLocal的强引用，无法回收，造成内存泄漏。

因此，使用弱引用可以防止长期存在的线程（通常使用了线程池）导致ThreadLocal无法回收造成内存泄漏。

2.那通常说的ThreadLocal内存泄漏是如何引起的呢？

我们注意到Entry对象中，虽然Key(ThreadLocal)是通过弱引用引入的，但是value即变量值本身是通过强引用引入。

这就导致，假如不作任何处理，由于ThreadLocalMap和线程的生命周期是一致的，当线程资源长期不释放，即使ThreadLocal本身由于弱引用机制已经回收掉了，但value还是驻留在线程的ThreadLocalMap的Entry中。即存在key为null，但value却有值的无效Entry。导致内存泄漏。

ANR导致原因？

1. cpu过载导致，全量logcat日志里会有相关的打印，各个进程cpu占用情况，这种一般不需要分析trace文件
2. 频繁gc导致，全量日志anr之前会有频繁的gc打印，trace文件头部也会统计gc单次耗时，总次数和总耗时
   主线程也会进入wait状态，之后就是一系列的gc相关的线程 wait
3. 死锁，这种我遇到的很少，就讲了下一般会打印资源is heldby xxx进程会形成互相持有的状态

Q1：什么是 AVL 树？
AVL 树 是平衡二叉查找树，增加和删除节点后通过树形旋转重新达到平衡。右旋是以某个节点为中心，将它沉入当前右子节点的位置，而让当前的左子节点作为新树的根节点，也称为顺时针旋转。同理左旋是以某个节点为中心，将它沉入当前左子节点的位置，而让当前的右子节点作为新树的根节点，也称为逆时针旋转。

Q2：什么是红黑树？
红黑树 是 1972 年发明的，称为对称二叉 B 树，1978 年正式命名红黑树。主要特征是在每个节点上增加一个属性表示节点颜色，可以红色或黑色。红黑树和 AVL 树 类似，都是在进行插入和删除时通过旋转保持自身平衡，从而获得较高的查找性能。与 AVL 树 相比，红黑树不追求所有递归子树的高度差不超过 1，保证从根节点到叶尾的最长路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。

红黑树在本质上还是二叉查找树，它额外引入了 5 个约束条件：① 节点只能是红色或黑色。② 根节点必须是黑色。③ 所有 NIL 节点都是黑色的。④ 一条路径上不能出现相邻的两个红色节点。⑤ 在任何递归子树中，根节点到叶子节点的所有路径上包含相同数目的黑色节点。

这五个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果一个树的左子节点或右子节点不存在，则均认定为黑色。红黑树的任何旋转在 3 次之内均可完成。

Q3：AVL 树和红黑树的区别？
红黑树的平衡性不如 AVL 树，它维持的只是一种大致的平衡，不严格保证左右子树的高度差不超过 1。这导致节点数相同的情况下，红黑树的高度可能更高，也就是说平均查找次数会高于相同情况的 AVL 树。

在插入时，红黑树和 AVL 树都能在至多两次旋转内恢复平衡，在删除时由于红黑树只追求大致平衡，因此红黑树至多三次旋转可以恢复平衡，而 AVL 树最多需要 O(logn) 次。AVL 树在插入和删除时，将向上回溯确定是否需要旋转，这个回溯的时间成本最差为 O(logn)，而红黑树每次向上回溯的步长为 2，回溯成本低。因此面对频繁地插入与删除红黑树更加合适。

Q4：B 树和B+ 树的区别？
B 树中每个节点同时存储 key 和 data，而 B+ 树中只有叶子节点才存储 data，非叶子节点只存储 key。InnoDB 对 B+ 树进行了优化，在每个叶子节点上增加了一个指向相邻叶子节点的链表指针，形成了带有顺序指针的 B+ 树，提高区间访问的性能。

B+ 树的优点在于：

① 由于 B+ 树在非叶子节点上不含数据信息，因此在内存页中能够存放更多的 key，数据存放得更加紧密，具有更好的空间利用率，访问叶子节点上关联的数据也具有更好的缓存命中率。

② B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可。而 B 树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有 B+树好。但是 B 树也有优点，由于每个节点都包含 key 和 value，因此经常访问的元素可能离根节点更近，访问也更迅速。

Q5：排序有哪些分类？
排序可以分为内部排序和外部排序，在内存中进行的称为内部排序，当数据量很大时无法全部拷贝到内存需要使用外存，称为外部排序。

内部排序包括比较排序和非比较排序，比较排序包括插入/选择/交换/归并排序，非比较排序包括计数/基数/桶排序。

插入排序包括直接插入/希尔排序，选择排序包括直接选择/堆排序，交换排序包括冒泡/快速排序。

Q6：直接插入排序的原理？
稳定，平均/最差时间复杂度 O(n²)，元素基本有序时最好时间复杂度 O(n)，空间复杂度 O(1)。

每一趟将一个待排序记录按其关键字的大小插入到已排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

1.从1加到n的和的公式
S=n(n+1)/2。
因为S=1+2+3+…+n，并且，S=n+(n-1)+(n-2)+…+1，把这两个等式左右分别相加可以得到：2S=(n+1)+(n+1)+(n+1)+…+(n+1)，其中等式右边一共是
n个（n+1)相加是很容易数出来的，所以得到 2S=n(n+1)，于是S=n(n+1)/2。

2.等差数列和公式：Sn=n(a1+an)/2=na1+n(n-1)/2 d

3.等比数列求和公式：当q≠1时 ，Sn=a1(1-q^n)/(1-q)=(a1-anq)/(1-q)
当q=1时Sn=na1
(a1为首项，an为第n项，d为公差，q 为等比)

4.等差数列 前n项和公式为：
Sn=na1+n(n-1)d/2或Sn=n(a1+an)/2(2)
从等差数列的定义、通项公式，前n项和公式还可推出：
a1+an=a2+an-1=a3+an-2=…=ak+an-k+1，k∈{1,2,…,n}
若m，n，p，q∈N*，且m+n=p+q，则有
am+an=ap+aq
Sm-1=(2n-1)an，S2n+1=(2n+1)an+1
Sk，S2k-Sk，S3k-S2k，…，Snk-S(n-1)k…或等差数列，等等。

5.Fib
0,1,1,2,3,5,8,13,21,…
F(n) = F(n-1) + F(n-2);

6. 二分查找 时间复杂度O(logn) 公式 T(n) = T(n/2) + O(1)
   二叉树遍历 时间复杂度O(n) 公式 T(n) = 2T(n/2) + O(1)
   排好序的二维矩阵二分查找 时间复杂度O(n) 公式 T(n) = 2T(n/2) + O(logn)
   归并排序 时间复杂度O(nlogn) 公式 T(n) = 2T(n/2) + O(n)

数据结构题目一直是面试官考察的重点。数组和字符串是两种最基本的数据结构。链表应该是面试题中使用频率最高的一种数据结构。如果面试官想加大面试难度，那么
他很有可能会选用与树(尤其是二叉树)想关的面试题。由于栈与递归调用密切相关，队列在图(包括树)的宽度优先遍历中需要用到，需账务这两种数据结构。

算法是面试官喜欢考察的另外一个重点。
查找(特别是二分查找)和排序(特别是快速排序和归并排序)是面试中经常考察的算法，应聘者一定要熟练掌握。
回溯法很适合解决迷宫及其类似的问题。如果面试题是求一哥问题的最优解，那么可以尝试使用动态规划。假如我们在用动态规划分析问题时发现每一步都存在一个能
得到最优解的选择，那么可以尝试使用贪婪算法。另外，应聘者还要掌握分析时间复杂度的方法，理解即使同一思路，基于循环和递归的不同实现，他们的时间复杂度
可能大不相同。很多时候我们会用自上而下的递归思路分析问题，却会基于自下而上的循环实现代码。
位运算是针对二进制数字的运算规则。需掌握二进制的与、或、异或运算及左移、右移操作，就能解决与运算相关的面试题。

不使用新的变量，交换两个变量的值。比如有两个变量a、b，我们希望交换他们的值。有两种不同的方法：
基于加减法：
a = a + b
b = a - b
a = a - b
基于异或运算：
a = a ^ b
b = a ^ b
a = a ^ b

位运算是把数字用二进制表示之后，对每一位上0或者1的运算。
与(&) 0 & 0 = 0 1 & 0 = 0 0 & 1 = 0 1 & 1 = 1
或(|) 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1
异或(^) 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1 ^ 1 = 0

把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的1变为0。
很多二进制问题都可以用这种思路解决。

稳定的
冒泡排序（bubble sort）— O(n2)
鸡尾酒排序（cocktail sort,双向的冒泡排序）—O(n2)
插入排序（insertion sort）—O(n2)
桶排序（bucket sort）—O(n);需要O(k)额外空间
计数排序（counting sort）—O(n+k);需要O(n+k)额外空间
归并排序（merge sort）—O(n log n);需要O(n)额外空间
原地归并排序— O（n2）
二叉排序树排序（binary tree sort）— O(n log n)期望时间; O(n2)最坏时间;需要O(n)额外空间
鸽巢排序（pigeonhole sort）—O(n+k);需要O(k)额外空间
基数排序（radix sort）—O(n·k);需要O(n)额外空间
侏儒排序（gnome sort）— O(n2)
图书馆排序（library sort）— O(n log n) with high probability,需要(1+ε)n额外空间
不稳定
选择排序（selection sort）—O(n2)
希尔排序（shell sort）—O(n log n)如果使用最佳的现在版本
组合排序— O(n log n)
堆排序（heap sort）—O(n log n)
平滑排序（smooth sort）— O(n log n)
快速排序（quick sort）—O(n log n)期望时间, O(n2)最坏情况;对于大的、乱数列表一般相信是最快的已知排序
内省排序（introsort）—O(n log n)
耐心排序（patience sort）—O(n log n + k)最坏情况时间，需要额外的O(n + k)空间，也需要找到最长的递增子串行（longest increasing subsequence）
不实用的排序算法
Bogo排序— O(n × n!)，最坏的情况下期望时间为无穷。
Stupid排序—O(n3);递归版本需要O(n2)额外存储器
珠排序（bead sort）— O(n) or O(√n),但需要特别的硬件
Pancake sorting—O(n),但需要特别的硬件
臭皮匠排序（stooge sort）算法简单，但需要约n^2.7的时间