知而不行为不知
a = a^b;
b = a^b;
a = a^b;
通过哈希函数后的值首尾相连成一个圆，数据hash之后对应在圆上的一个位置，机器也处在这个圆上（根据机器id计算出哈希值），数据hash之后顺时针找离它的哈希值最近的机器
节点的深度 - 从树的根节点到该节点的边数
节点的高度 - 该节点和叶子之间最长路径上的边数
树的高度 - 其根节点的高度
一个高度平衡的二叉搜索树（平衡二叉搜索树）是在插入和删除任何节点之后，可以自动保持其高度最小。也就是说，有N个节点的平衡二叉搜索树，它的高度是logN。并且，每个节点的两个子树的高度不会相差超过1。
正如我们之前提到的, 一个有N个节点的平衡二搜索叉树的高度总是logN。因此，我们可以计算节点总数和树的高度，以确定这个二叉搜索树是否为高度平衡的。
同样，在定义中， 我们提到了高度平衡的二叉树一个特性: 每个节点的两个子树的深度不会相差超过1。我们也可以根据这个性质，递归地验证树。
我们已经介绍过了二叉树及其相关操作, 包括搜索、插入、删除。
当分析这些操作的时间复杂度时，我们需要注意的是树的高度是十分重要的考量因素。
以搜索操作为例，如果二叉搜索树的高度为h，则时间复杂度为O(h)。二叉搜索树的高度的确很重要。
所以，我们来讨论一下树的节点总数N和高度h之间的关系。 对于一个平衡二叉搜索树, 我们已经在前文中提过, h>= logN 。但对于一个普通的二叉搜索树， 在最坏的情况下, 它可以退化成一个链。
因此，具有N个节点的二叉搜索树的高度在logN到N区间变化。也就是说，搜索操作的时间复杂度可以从logN变化到N。这是一个巨大的性能差异。
所以说，高度平衡的二叉搜索树对提高性能起着重要作用。
有许多不同的方法可以实现。尽管这些实现方法的细节有所不同，但他们有相同的目标:
采用的数据结构应该满足二分查找属性和高度平衡属性。
采用的数据结构应该支持二叉搜索树的基本操作，包括在O(logN)时间内的搜索、插入和删除，即使在最坏的情况下也是如此。
红黑树
AVL树
伸展树
树堆
高度平衡的二叉搜索树在实际中被广泛使用，因为它可以在O(logN)时间复杂度内执行所有搜索、插入和删除操作。
平衡二叉搜索树的概念经常运用在Set和Map中。 Set和Map的原理相似。 我们将在下文中重点讨论Set这个数据结构。
Set(集合)是另一种数据结构，它可以存储大量key(键)而不需要任何特定的顺序或任何重复的元素。 它应该支持的基本操作是将新元素插入到Set中，并检查元素是否存在于其中。
通常，有两种最广泛使用的集合：散列集合(Hash Set)和树集合(Tree Set)。
树集合, Java中的Treeset或者C++中的set，是由高度平衡的二叉搜索树实现的。因此，搜索、插入和删除的时间复杂度都是O(logN)。
散列集合, Java中的HashSet或者C++中的unordered_set，是由哈希实现的, 但是平衡二叉搜索树也起到了至关重要的作用。当存在具有相同哈希键的元素过多时，将花费O(N)时间复杂度来查找特定元素，其中N是具有相同哈希键的元素的数量。 通常情况下，使用高度平衡的二叉搜索树将把时间复杂度从 O(N) 改善到 O(logN)。
哈希集和树集之间的本质区别在于树集中的键是有序的。
高度平衡的二叉搜索树是二叉搜索树的特殊表示形式，旨在提高二叉搜索树的性能。但这个数据结构具体的实现方式，超出了我们这章的内容，也很少会在面试中被考察。但是了解高度平衡二叉搜索树的的基本概念，以及如何运用它帮助你进行算法设计是非常有用的。
比如：反转字符串，数组拆分，两数和（有序数组）
比如： 原地移除元素。最大连续1的个数，长度最小的子数组
你有时可能需要在使用双指针技巧之前对数组进行排序，也可能需要运用贪心想法来决定你的运动策略。
双指针技术
删除倒数第n个节点：19，61，143
判断有没有环lc141，lc142
回文链234
// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
* Change this condition to fit specific problem.
* Attention: remember to avoid null-pointer error
**/
while (slow != null && fast != null && fast.next != null) {
slow = slow.next; // move slow pointer one step each time
fast = fast.next.next; // move fast pointer two steps each time
if (slow == fast) { // change this condition to fit specific problem
return true;
}
}
return false; // change return value to fit specific problem
lc17
递归调用的一个重要特征–要返回
回溯法 是依赖递归的
（要保证回去，递归本身会回去，但有些状态需要手动回去，比如全排列问题中使用辅助空间used）
回溯法是暴力解法的一个主要实现手段
动态规划就是在回溯法基础上实现的；
还可以通过某些剪枝不用遍历完所有情况。
lc93，131
lc77
lc79
本质是深度优先的遍历
回溯法是经典人工智能的基础
lc51
N皇后问题：
可以定义一个Try(x,y)函数判断棋盘(x,y)处是否可以放皇后：
(1)不在同一列
(2)不在对角线上，即有两棋子坐标分别为(X1,Y1),(X2,Y2)，则|X1-X2|!=|Y1-Y2|
回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。
基本思想类同于：
• 图的深度优先搜索
• 二叉树的后序遍历
【
分支限界法：广度优先搜索
思想类同于：图的广度优先遍历
二叉树的层序遍历
】
详细的描述则为：
回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。
问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。
解空间树分为两种：
**子集树和排列树**。两种在算法结构和思路上大体相同。
当问题是要求满足某种性质（约束条件）的所有解或最优解时，往往使用回溯法。
它有“通用解题法”之美誉。
TO BE CONTINUED
单例的7种写法？double check？
多线程中几种锁？
可见性
transient
类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），
为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。
换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。
1）一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。
2）transient关键字只能修饰变量，而不能修饰方法和类。注意，本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量，则该类需要实现Serializable接口。
3）被transient关键字修饰的变量不再能被序列化，一个静态变量不管是否被transient修饰，均不能被序列化。
volatile关键字
当使用volatile修饰某个变量时，它会保证对该变量的修改会立即被更新到内存中，
并且将其它缓存中对该变量的缓存设置成无效，因此其它线程需要读取该值时必须从主内存中读取，从而得到最新的值。
volatile适用于不需要保证原子性，但却需要保证可见性的场景。一种典型的使用场景是用它修饰用于停止线程的状态标记。
volatile在这里可以做到的作用是使得多个线程可以共享变量，但是问题在于使用volatile将使得VM优化失去作用，导致效率较低，所以要在必要的时候使用。
问：既然锁和synchronized即可保证原子性也可保证可见性，为何还需要volatile？
答：synchronized和锁需要通过操作系统来仲裁谁获得锁，开销比较高，而volatile开销小很多。因此在只需要保证可见性的条件下，
使用volatile的性能要比使用锁和synchronized高得多。
6. 类加载顺序
总的来说，初始化顺序依次是：（静态变量、静态初始化块）–>（变量、初始化块）–> 构造器；
如果有父类，则顺序是：父类static方法 –> 子类static方法 –> 父类构造方法- -> 子类构造方法
虚拟机在首次加载Java类时，会对静态代码块、静态成员变量、静态方法进行一次初始化（静态间按声明顺序执行）。
只有在调用new方法时才会创建类的实例。
类实例创建过程：父子继承关系，先父类再子类。父类的静态->子类的静态->父类的初始化块->父类的构造方法->子类的初始化块->子类的构造方法
类实例销毁时候：首先销毁子类部分，再销毁父类部分。
7. 大数相加、大数相乘
static synchronized
timewait次数太多
通信双方建立TCP连接后，主动关闭连接的一方就会进入TIME_WAIT状态。
客户端主动关闭连接时，会发送最后一个ack后，然后会进入TIME_WAIT状态，再停留2个MSL时间(后有MSL的解释)，进入CLOSED状态。
大多数服务器端一般执行被动关闭，服务器不会进入TIME_WAIT状态。
高并发短连接的TCP服务器上，当服务器处理完请求后立刻按照主动正常关闭连接。。。这个场景下，会出现大量socket处于TIMEWAIT状态。
服务端为了解决这个TIME_WAIT问题，可选择的方式有三种：
Ø 保证由客户端主动发起关闭（即做为B端）
Ø 关闭的时候使用RST的方式
Ø 对处于TIME_WAIT状态的TCP允许重用
如发现系统存在大量TIME_WAIT状态的连接，通过调整内核参数解决：
10. hashmap9
atomicInteger
AtomicInteger是一个提供原子操作的Integer类，通过线程安全的方式操作加减。
问：既然锁和synchronized可以保证原子性，为什么还需要AtomicInteger这种的类来保证原子操作？
答：锁和synchronized需要通过操作系统来仲裁谁获得锁，开销比较高，而AtomicInteger是通过CPU级的CAS操作来保证原子性，开销比较小。
所以使用AtomicInteger的目的还是为了提高性能。
Volatile修饰的成员变量在每次被线程访问时，都强迫从共享内存重新读取该成员的值，而且，当成员变量值发生变化时，强迫将变化的值重新写入共享内存，
这样两个不同的线程在访问同一个共享变量的值时，始终看到的是同一个值。
而volatile这个值的作用就是告诉VM：对于这个成员变量不能保存它的副本，要直接与共享成员变量交互。
建议：当多个线程同时访问一个共享变量时，可以使用volatile，而当访问的变量已在synchronized代码块中时，不必使用。
缺点：使用volatile将使得VM优化失去作用，导致效率较低，所以要在必要的时候使用。
找中位数（2个有序数组数组中查找Top K的值（Top K的问题可以转换成求第k个元素的问题））
排序；快速排序思想；
不用随机数生成随机
UDP
可重入锁
如果TCP连接中没收到怎么办
进程间通信：
这种存在共享内存区的进程间的冲突问题，解决方法的思路是统一的：当某个进程正在操作共享内存区时，其他进程不得操作共享内存区。
这个思路实现的关键点就是：令其他进程知道“有一个进程在操作共享内存区”，因此这类问题就被称为进程通信问题，
通信的“内容”就是：有没有其他进程在操作共享内存区。（讲解到信号量机制时进程通信将广义化，但依然不是进程间的“实际通信”，而是某些信号的共享）
IPC的方式通常有管道（包括无名管道和命名管道）、消息队列、信号量、共享存储、Socket、Streams等。其中 Socket和Streams支持不同主机上的两个进程IPC。
1.管道：速度慢，容量有限，只有父子进程能通讯
2.FIFO：任何进程间都能通讯，但速度慢
3.消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题
4.信号量：不能传递复杂消息，只能用来同步
5.共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，
当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存
Mybatis（看）,事务实现
如何找出一列数中的两个重复元素
mysql中索引类型及实现
数据库中的锁
行锁
java锁的底层实现
数据库中mysql的事务
事务的隔离性是通过锁实现，而事务的原子性、一致性和持久性则是通过事务日志实现。说到事务日志，不得不说的就是redo和undo。
事务的实现是基于数据库的存储引擎。不同的存储引擎对事务的支持程度不一样。mysql中支持事务的存储引擎有innoDB和NDB。
innoDB是mysql默认的存储引擎，默认的隔离级别是RR，并且在RR的隔离级别下更进一步，
通过多版本并发控制（MVCC，Multiversion Concurrency Control ）解决不可重复读问题，
加上间隙锁（也就是并发控制）解决幻读问题。因此innoDB的RR隔离级别其实实现了串行化级别的效果，而且保留了比较好的并发性能。
mybatis事务管理机制
mysql中主键和唯一键的区别，唯一索引。
都是不允许重复,mysql中索引的数据结构是B+树
主键只有一个，唯一约束可以有多个；
主键不能为null，唯一约束可以有多个；
主键是不可能（或很难）更新，唯一约束只要唯一就可以更新．
（2）.在创建唯一性约束和主键约束时可以创建聚集索引和非聚集索引，但在 默认情况下主键约束产生聚集索引，而唯一性约束产生非聚集索引
约束和索引， 前者是用来检查数据的正确性，后者用来实现数据查询的优化，目的不同。
唯一性约束与唯一索引有所不同：
（1）.创建唯一约束会在Oracle中创建一个Constraint，同时也会创建一个该约束对应的唯一索引。
（2）.创建唯一索引只会创建一个唯一索引，不会创建Constraint。
也就是说其实唯一约束是通过创建唯一索引来实现的。
在删除时这两者也有一定的区别：
删除唯一约束时可以只删除约束而不删除对应的索引，所以对应的列还是必须唯一的，
而删除了唯一索引的话就可以插入不唯一的值。
tcp连接中间的数据丢失
约瑟夫环
线程间通信
wait，notify，notifyAll
equals与hashcode为什么需要一致
信号量
互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程释放，另一个线程得到。
基于上面的特点，互斥锁一般用于控制一段临界代码，当然信号量也可以做到。但是如果释放和获取不在一个函数中甚至不在一个线程中时就必须使用信号量了
tcp为什么比udp可靠
[1] 确认和重传机制
建立连接时三次握手同步双方的“序列号 + 确认号 + 窗口大小信息”，是确认重传、流控的基础
传输过程中，如果Checksum校验失败、丢包或延时，发送端重传
[2] 数据排序
TCP有专门的序列号SN字段，可提供数据re-order
[3] 流量控制
窗口和计时器的使用。TCP窗口中会指明双方能够发送接收的最大数据量
[4] 拥塞控制
TCP的拥塞控制由4个核心算法组成。
“慢启动”（Slow Start）
“拥塞避免”（Congestion avoidance）
“快速重传 ”（Fast Retransmit）
“快速恢复”（Fast Recovery）
索引
只有在where语句出现，mysql才会去使用索引。
mysql中索引的数据结构是B+树。（通常B+树用于数据库索引，而B树则常用于文件索引。）
mysql中的primary key，unique，联合唯一也都是索引，这些索引除了加速查找以外，还有约束的功能
32.1 为什么用索引
数据库也是一样，但显然要复杂的多，因为不仅面临着等值查询，还有范围查询(>、<、between、in)、模糊查询(like)、并集查询(or)等等。数据库应该选择怎么样的方式来应对所有的问题呢？我们回想字典的例子，能不能把数据分成段，然后分段查询呢？最简单的如果1000条数据，1到100分成第一段，101到200分成第二段，201到300分成第三段……这样查第250条数据，只要找第三段就可以了，一下子去除了90%的无效数据。但如果是1千万的记录呢，分成几段比较好？稍有算法基础的同学会想到搜索树，其平均复杂度是lgN，具有不错的查询性能。但这里我们忽略了一个关键的问题，复杂度模型是基于每次相同的操作成本来考虑的。而数据库实现比较复杂，一方面数据是保存在磁盘上的，另外一方面为了提高性能，每次又可以把部分数据读入内存来计算，因为我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树难以满足复杂的应用场景。
32.1 聚簇索引
索引分为聚簇索引和非聚簇索引两种，聚簇索引是按照数据存放的物理位置为顺序的，而非聚簇索引就不一样了；
聚簇索引能提高多行检索的速度，而非聚簇索引对于单行的检索很快。
聚簇索引是顺序结构与数据存储物理结构一致的一种索引，并且一个表的聚簇索引只能有唯一的一条；
聚簇索引优点：
2.2.1、把相关数据保存在一起，因为mysql数据库读取数据是按照页读取的，当读取某一个用户数据时，相邻的数据也会加载到内存中。
根据用户读取一个id的数据时，相邻数据被读取的可能性会非常高，这种按页加载就减少了IO操作
2.2.2、数据访问更快
2.2.3、使用覆盖索引扫描的查询可以直接使用叶节点中的主键值
object的方法
CAS（compare and swap）
基础类型变量自增（i++）是一种常被新手误以为是原子操作而实际不是的操作。
Java中提供了对应的原子操作类来实现该操作，并保证原子性，其本质是利用了CPU级别的CAS指令。
由于是CPU级别的指令，其开销比需要操作系统参与的锁的开销小。
阻塞队列
阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。
这两个附加的操作是：在队列为空时，获取元素的线程会等待队列变为非空。当
队列满时，存储元素的线程会等待队列可用。
阻塞队列常用于生产者和消费者的场景，生产者是往队列里添加元素的线程，
消费者是从队列里拿元素的线程。阻塞队列就是生产者存放元素的容器，而消费者也只从容器里拿元素。
使用非阻塞队列的时候有一个很大问题就是：它不会对当前线程产生阻塞，那么在面对类似消费者-生产者的模型时，
就必须额外地实现同步策略以及线程间唤醒策略，这个实现起来就非常麻烦。但是有了阻塞队列就不一样了，
它会对当前线程产生阻塞，比如一个线程从一个空的阻塞队列中取元素，此时线程会被阻塞直到阻塞队列中有了元素。
当队列中有元素后，被阻塞的线程会自动被唤醒（不需要我们编写代码去唤醒）。这样提供了极大的方便性。
ThreadLocal
可以通过java.lang.ThreadLocal类来实现线程本地存储的功能。每一个线程的Thread对象中都有一个ThreadLocalMap对象，
这个对象存储了一组以ThreadLocal.threadLocalHashCode为键，以本地线程变量为值的K-V值对，ThreadLocal对象就是当前线程的ThreadLocalMap的访问入口，
每一个ThreadLocal对象都包含了一个独一无二的threadLocalHashCode值，使用这个值就可以在线程K-V值对中找回对应的本地线程变量。
拦截器和过滤器的区别：
①拦截器是基于java的反射机制的，而过滤器是基于函数回调。
②拦截器不依赖与servlet容器，过滤器依赖与servlet容器。
③拦截器只能对action请求起作用，而过滤器则可以对几乎所有的请求起作用。
④拦截器可以访问action上下文、值栈里的对象，而过滤器不能访问。
⑤在action的生命周期中，拦截器可以多次被调用，而过滤器只能在容器初始化时被调用一次。
⑥拦截器可以获取IOC容器中的各个bean，而过滤器就不行，这点很重要，在拦截器里注入一个service，可以调用业务逻辑。