面试题目总结

#1 hashMap底层？

JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

简单说下HashMap的实现原理：

首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中

即HashMap的原理图是：

2 为什么jdk1.8要用红黑树实现？

在Jdk1.8版本后，Java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度

3 为什么HashMap线程不安全，在多线程操作情况下什么时候线程不安全？

HashMap在put的时候，插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。

https://blog.csdn.net/loveliness_peri/article/details/81092360

4 如何实现HashMap的同步？怎么解决线程不安全？

答：

　　第一种方法：

　　直接使用Hashtable，但是当一个线程访问HashTable的同步方法时，其他线程如果也要访问同步方法，会被阻塞住。举个例子，当一个线程使用put方法时，另一个线程不但不可以使用put方法，连get方法都不可以，效率很低，现在基本不会选择它了。

　　第二种方法： HashMap可以通过下面的语句进行同步，

Collections.synchronizeMap(hashMap);

1
　　HashMap可以通过Map m = Collections.synchronizedMap(new HashMap())来达到同步的效果。（从源码中看出 synchronizedMap()方法返回一个SynchronizedMap类的对象，而在SynchronizedMap类中使用了synchronized来保证对Map的操作是线程安全的，故效率其实也不高。）

　　具体而言，该方法返回一个同步的Map，该Map封装了底层的HashMap的所有方法，使得底层的HashMap即使是在多线程的环境中也是安全的。

　　第三种方法：

　　直接使用JDK 5 之后的 ConcurrentHashMap，如果使用Java 5或以上的话，请使用ConcurrentHashMap。

5 认初始容量是16，如果我改成7，容量会变成7么？？为什么？

6数组和链表的区别？

** 数组和链表的区别整理如下： **

数组静态分配内存，链表动态分配内存；
数组在内存中连续，链表不连续；
数组元素在栈区，链表元素在堆区；
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)

7 常见的线程池有哪些?

java中的有哪些线程池？

1.newCachedThreadPool创建一个可缓存线程池程

2.newFixedThreadPool 创建一个定长线程池

3.newScheduledThreadPool 创建一个定长线程池

4.newSingleThreadExecutor 创建一个单线程化的线程池

//缓存线程池，线程池的大小由jvm决定，如果有空闲线程会回收
Executors.newCachedThreadPool();
//单线程线程池，可保证任务执行的顺序就是任务提交的顺序
Executors.newSingleThreadExecutor();
//固定大小线程池（服务端推荐使用）
Executors.newFixedThreadPool(size);
//周期性线程池，可周期性执行任务
Executors.newScheduledThreadPool(size);

8 Java线程池中的7个参数

public class ThreadPoolExecutor extends AbstractExecutorService {
    .....
    public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,
            BlockingQueue<Runnable> workQueue);
 
    public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,
            BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory);
 
    public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,
            BlockingQueue<Runnable> workQueue,RejectedExecutionHandler handler);
 
    public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,
        BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory,RejectedExecutionHandler handler);
    ...
}

参数理解：

corePollSize：核心线程数。在创建了线程池后，线程中没有任何线程，等到有任务到来时才创建线程去执行任务。默认情况下，在创建了线程池后，线程池中的线程数为0，当有任务来之后，就会创建一个线程去执行任务，当线程池中的线程数目达到corePoolSize后，就会把到达的任务放到缓存队列当中。
maximumPoolSize：最大线程数。表明线程中最多能够创建的线程数量。
keepAliveTime：空闲的线程保留的时间。
TimeUnit：空闲线程的保留时间单位。
BlockingQueue：阻塞队列，存储等待执行的任务。参数有ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue可选。
ThreadFactory：线程工厂，用来创建线程
RejectedExecutionHandler：队列已满，而且任务量大于最大线程的异常处理策略。有以下取值:

ThreadPoolExecutor.AbortPolicy:丢弃任务并抛出RejectedExecutionException异常。 
ThreadPoolExecutor.DiscardPolicy：也是丢弃任务，但是不抛出异常。 
ThreadPoolExecutor.DiscardOldestPolicy：丢弃队列最前面的任务，然后重新尝试执行任务（重复此过程）
ThreadPoolExecutor.CallerRunsPolicy：由调用线程处理该任务

9 newCachedThreadPool最大可开启的线程数是多少？

这种类型的线程池特点是：

工作线程的创建数量几乎没有限制(其实也有限制的,数目为Interger. MAX_VALUE), 这样可灵活的往线程池中添加线程。
如果长时间没有往线程池中提交任务，即如果工作线程空闲了指定的时间(默认为1分钟)，则该工作线程将自动终止。终止后，如果你又提交了新的任务，则线程池重新创建一个工作线程。
在使用CachedThreadPool时，一定要注意控制任务的数量，否则，由于大量线程同时运行，很有会造成系统瘫痪。

newCachedThreadPool无上限线程池，动态根据代码添加线程，如果线程空闲60秒没有被使用，会自动关闭

10 如何实现其他线程和主线程的同步？

Synchronized 同步

1、方法同步。给方法增加synchronized修饰符就可以成为同步方法，可以是静态方法、非静态方法，但不能是抽象方法、接口方法。小示例：

public synchronized void aMethod() { 
    // do something 
} 
 
public static synchronized void anotherMethod() { 
    // do something 
}

使用块同步，示例：

public class ThreadTest implements Runnable{
   public void run(){
      synchronized(this){  //与上面示例不同于关键字使用
           for(int i=0;i<10;i++){
               System.out.print(" " + i);
           }
      } 
   }
   public static void main(String[] args){
       Runnable r = new ThreadTest();
       Thread t1 = new Thread(r);
       Thread t2 = new Thread(r);
       t1.start();
       t2.start();
   }
}

Volatile 同步

1	a.volatile关键字为域变量的访问提供了一种免锁机制

b.使用volatile修饰域相当于告诉虚拟机该域可能会被其他线程更新

c.因此每次使用该域就要重新计算，而不是使用寄存器中的值 

d.volatile不会提供任何原子操作，它也不能用来修饰final类型的变量

重入锁同步

ReentrantLock类是可重入、互斥、实现了Lock接口的锁，它与使用synchronized方法和快具有相同的基本行为和语义，并且扩展了其能力。 ReenreantLock类的常用方法有：

1
2
3

ReentrantLock() : 创建一个ReentrantLock实例 
lock() : 获得锁 
unlock() : 释放锁

阻塞队列同步

BlockingQueue定义了阻塞队列的常用方法，尤其是三种添加元素的方法，我们要多加注意，当队列满时：

　　add()方法会抛出异常

　　offer()方法返回false

　　put()方法会阻塞

原子变量同步

AtomicInteger类常用方法：

AtomicInteger(int initialValue) : 创建具有给定初始值的新的

AtomicIntegeraddAddGet(int dalta) : 以原子方式将给定值与当前值相加

get() : 获取当前值

11 volatile关键字的特性有哪些？

1 . 保证了不同线程对该变量操作的内存可见性;

2 . 禁止指令重排序

12 Java使用阻塞队列BlockingQueue实现线程同步

详细阐述了多个任务之间的协同合作，需要使用wait、notify、notifyAll或者lock、condition、await、signal、signalAll方法来进行同步。实现起来比较复杂。因此java提供了同步队列（阻塞队列BlockingQueue）。
同步队列要求只能有一个任务对其进行操作（因此无需再对其使用同步操作，同步队列内部是同步的。）。当队列是空时，会导致取该队列的线程阻塞；当队列满（设置固定大小的队列）时，会导致写该队列的线程阻塞。
java的JUC（java.util.concurrent）包提供了BlockingQueue接口，并为其提供了三个实现：LinkedBlockingQueue（无界队列）、ArrayBlockingQueue（有固定大小的队列）、 SynchronousQueue（大小为1的队列

从上表可以很明显看出每个方法的作用，这个不用多说。我想说的是：

add(e) remove() element() 方法不会阻塞线程。当不满足约束条件时，会抛出IllegalStateException 异常。例如：当队列被元素填满后，再调用add(e)，则会抛出异常。
offer(e) poll() peek() 方法即不会阻塞线程，也不会抛出异常。例如：当队列被元素填满后，再调用offer(e)，则不会插入元素，函数返回false。
要想要实现阻塞功能，需要调用put(e) take() 方法。当不满足约束条件时，会阻塞线程。
BlockingQueue 阻塞算法

13 建mysql表的时候会考虑一些什么

char与varchar

char ：长度固定，比较适合存储很短（比如门牌号码101，201）、固定长度（比如使用uuid作为主键）、十分频繁改变的column的字段；char(M)类型的数据列里，每个值都占用M个字节，如果某个长度小于M，MySQL就会在它的右边用空格字符补足。（在检索操作中那些填补出来的空格字符将被去掉）

varchar：可变长度，占用长度为字符数+1(用来存储位置)
总结：char 因固定长度，所以在处理速度上要比varchar快速很多，但是相对较费存储空间；所以对存储空间要求不大，但在速度上有要求的可以使用char类型，反之可以用varchar类型来实例

索引

对于那些在查询中很少使用或者参考的列不应该创建索引。费空间

对于那些只有很少数据值的列也不应该增加索引。映射太少

对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为，这些列的数据量要么相当大，要么取值很少。

当修改性能远远大于检索性能时，不应该创建索引。这是因为，修改性能和检索性能是互相矛盾的。

14 mysql索引

1	CREATE INDEX indexName ON mytable(username(length));

主键索引: 数据列不允许重复，不允许为NULL.一个表只能有一个主键。

唯一索引: 数据列不允许重复，允许为NULL值，一个表允许多个列创建唯一索引。

可以通过 ALTER TABLE table_name ADD UNIQUE (column); 创建唯一索引

可以通过 ALTER TABLE table_name ADD UNIQUE (column1,column2); 创建唯一组合索引

普通索引: 基本的索引类型，没有唯一性的限制，允许为NULL值。

可以通过ALTER TABLE table_name ADD INDEX index_name (column);创建普通索引

可以通过ALTER TABLE table_name ADD INDEX index_name(column1, column2, column3);创建组合索引

全文索引： 是目前搜索引擎使用的一种关键技术。

可以通过ALTER TABLE table_name ADD FULLTEXT (column);创建全文索引

最左前缀

顾名思义，就是最左优先，在创建多列索引时，要根据业务需求，where子句中使用最频繁的一列放在最左边。
还有一个就是生效原则比如

1
2

索引算法有 BTree Hash

BTree是最常用的mysql数据库索引算法，也是mysql默认的算法。因为它不仅可以被用在=,>,>=,<,<=和between这些比较操作符上，而且还可以用于like操作符，只要它的查询条件是一个不以通配符开头的常量，例如：

select * from user where name like 'jack%'; 
如果一通配符开头，或者没有使用常量，则不会使用索引，例如： 
select * from user where name like '%jack'; 
复制代码

Hash Hash索引只能用于对等比较，例如=,<=>（相当于=）操作符。由于是一次定位数据，不像BTree索引需要从根节点到枝节点，最后才能访问到页节点这样多次IO访问，所以检索效率远高于BTree索引。

BTree索引是最常用的mysql数据库索引算法，也是mysql默认的算法。因为它不仅可以被用在=,>,>=,<,<=和between这些比较操作符上，而且还可以用于like操作符例如：

只要它的查询条件是一个不以通配符开头的常量
select * from user where name like 'jack%'; 
如果一通配符开头，或者没有使用常量，则不会使用索引，例如： 
select * from user where name like '%jack'; 
复制代码

15 写sql语句的时候where会考虑什么？

不要在Where 字句中对列使用函数，那样会导致索引失效，

16 hashtable和concurrenthashmap有什么区别?

ConcurrentHashMap采用了更细粒度的锁来提高在并发情况下的效率。ConcurrentHashMap将Hash表默认分为16个桶（每一个桶可以被看作是一个Hashtable），大部分操作都没有用到锁，而对应的put、remove等操作也只需要锁住当前线程需要用到的桶，而不需要锁住整个数据。采用这种设计方式以后，在大并发的情况下，同时可以有16个线程来访问数据。显然，大大提高了并发性。
————————————————

Hashtable通过使用synchronized修饰方法的方式来实现多线程同步，因此，Hashtable的同步会锁住整个数组。在高并发的情况下，性能会非常差，Java5中引入了java.util.concurrent.ConcurrentHashMap作为高吞吐量的线程安全HashMap实现，它采用了锁分离的技术允许多个修改操作并发进行。它们在多线程锁的使用方式如图4所示。
————————————————

底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段数组+链表 实现，而 JDK1.8 的 ConcurrentHashMap 实现跟 HashMap1.8 的数据结构一样，都是 数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似，都是采用 数组+链表 的形式。数组是 HashMap 的主体，链表则是为了解决哈希冲突而存在的；
实现线程安全的方式： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段( Segment )，每一把锁只锁容器其中的一部分数据，这样多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高了并发访问率。到了 JDK1.8，摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作，（JDK1.6 以后对 synchronized 锁做了很多的优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable (同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。一个线程访问同步方法时，当其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程就不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈，效率就越低

————————————————

17 lock和synchronized的区别

　1）Lock是一个接口，而synchronized是Java中的关键字，synchronized是内置的语言实现，synchronized是在JVM层面上实现的，不但可以通过一些监控工具监控synchronized的锁定，而且在代码执行时出现异常，JVM会自动释放锁定，但是使用Lock则不行，lock是通过代码实现的，要保证锁定一定会被释放，就必须将 unLock()放到finally{} 中；

　　2）synchronized在发生异常时，会自动释放线程占有的锁，因此不会导致死锁现象发生；而Lock在发生异常时，如果没有主动通过unLock()去释放锁，则很可能造成死锁现象，因此使用Lock时需要在finally块中释放锁；

　　3）Lock可以让等待锁的线程响应中断，线程可以中断去干别的事务，而synchronized却不行，使用synchronized时，等待的线程会一直等待下去，不能够响应中断；

　　4）通过Lock可以知道有没有成功获取锁，而synchronized却无法办到。

　　5）Lock可以提高多个线程进行读操作的效率。

　　在性能上来说，如果竞争资源不激烈，两者的性能是差不多的，而当竞争资源非常激烈时（即有大量线程同时竞争），此时Lock的性能要远远优于synchronized。所以说，在具体使用时要根据适当情况选择。

*二、ReentrantLock获取锁定与三种方式：　　*

*a) lock(), 如果获取了锁立即返回，如果别的线程持有锁，当前线程则一直处于休眠状态，直到获取锁　　*

*b) tryLock(), 如果获取了锁立即返回true，如果别的线程正持有锁，立即返回false；　　*

*c)tryLock(long timeout,TimeUnit unit)，如果获取了锁定立即返回true，如果别的线程正持有锁，会等待参数给定的时间，在等待的过程中，如果获取了锁定，就返回true，如果等待超时，返回false；　　*

d) lockInterruptibly:如果获取了锁定立即返回，如果没有获取锁定，当前线程处于休眠状态，直到或者锁定，或者当前线程被别的线程中断

2.ReentrantLock

　　ReentrantLock，意思是“可重入锁”，关于可重入锁的概念在下一节讲述。ReentrantLock是唯一实现了Lock接口的类，并且ReentrantLock提供了更多的方法。下面通过一些实例看具体看一下如何使用ReentrantLock。

18 TCP和UDP区别

区别：

1） TCP是面向连接的，可靠性高；UDP是基于非连接的，可靠性低
2）由于TCP是连接的通信，需要有三次握手、重新确认等连接过程，会有延时，实时性差，同时过程复杂，也使其易于攻击；UDP没有建立连接的过程，因而实时性较强，也稍安全
3）在传输相同大小的数据时，TCP首部开销20字节；UDP首部开销8字节，TCP报头比UDP复杂，故实际包含的用户数据较少。TCP在IP协议的基础上添加了序号机制、确认机制、超时重传机制等，保证了传输的可靠性，不会出现丢包或乱序，而UDP有丢包，故TCP开销大，UDP开销较小
4）每条TCP连接只能时点到点的；UDP支持一对一、一对多、多对一、多对多的交互通信

TCP是一种面向连接的、可靠的、基于字节流的传输层通信协议，是专门为了在不可靠的网络中提供一个可靠的端对端字节流而设计的，面向字节流。
UDP（用户数据报协议）是iso参考模型中一种无连接的传输层协议，提供简单不可靠的非连接传输层服务，面向报文

19 TCP UDP 应用场景选择

对实时性要求高和高速传输的场合下使用UDP;在可靠性要求低，追求效率的情况下使用UDP;
需要传输大量数据且对可靠性要求高的情况下使用TCP

20 TCP协议如何保证可靠传输

1、应用数据被分割成TCP认为最适合发送的数据块。
2、超时重传：当TCP发出一个段后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段。
3、TCP给发送的每一个包进行编号，接收方对数据包进行排序，把有序数据传送给应用层。
4、校验和：TCP将保持它首部和数据的检验和。这是一个端到端的检验和，目的是检测数据在传输过程中的任何变化。如果收到段的检验和有差错，TCP将丢弃这个报文段和不确认收到此报文段。
5、TCP的接收端会丢弃重复的数据。
6、流量控制：TCP连接的每一方都有固定大小的缓冲空间，TCP的接收端只允许发送端发送接收端缓冲区能接纳的我数据。当接收方来不及处理发送方的数据，能提示发送方降低发送的速率，防止包丢失。TCP使用的流量控制协议是可变大小的滑动窗口协议。
7、拥塞控制：当网络拥塞时，减少数据的发送。
————————————————

21 javaGC

一、什么是GC：

每个程序员都遇到过内存溢出的情况，程序运行时，内存空间是有限的，那么如何及时的把不再使用的对象清除将内存释放出来，这就是GC要做的事。

1、GC的对象

需要进行回收的对象就是已经没有存活的对象，判断一个对象是否存活常用的有两种办法：引用计数和可达分析。

在Java语言中，GC Roots包括：

虚拟机栈中引用的对象。

方法区中类静态属性实体引用的对象。

方法区中常量引用的对象。

本地方法栈中JNI引用的对象。

2、什么时候触发GC

(1)程序调用System.gc时可以触发

(2)系统自身来决定GC触发的时机（根据Eden区和From Space区的内存大小来决定。当内存大小不足时，则会启动GC线程并停止应用线程）

GC又分为 minor GC 和 Full GC (也称为 Major GC )

Minor GC触发条件：当Eden区满时，触发Minor GC。

Full GC触发条件：

a.调用System.gc时，系统建议执行Full GC，但是不必然执行

b.老年代空间不足

c.方法去空间不足

d.通过Minor GC后进入老年代的平均大小大于老年代的可用内存

e.由Eden区、From Space区向To Space区复制时，对象大小大于To Space可用内存，则把该对象转存到老年代，且老年代的可用内存小于该对象大小

二 GC常用算法

GC常用算法有：标记-清除算法，标记-压缩算法，复制算法，分代收集算法。

目前主流的JVM（HotSpot）采用的是分代收集算法。

三、垃圾收集器

如果说收集算法是内存回收的方法论，垃圾收集器就是内存回收的具体实现

1.Serial收集器

串行收集器是最古老，最稳定以及效率高的收集器
可能会产生较长的停顿，只使用一个线程去回收
-XX:+UseSerialGC

新生代、老年代使用串行回收
新生代复制算法
老年代标记-压缩

*& 并行收集器

2.1 ParNew

-XX:+UseParNewGC（new代表新生代，所以适用于新生代）

新生代并行
老年代串行
Serial收集器新生代的并行版本
在新生代回收时使用复制算法
多线程，需要多核支持
-XX:ParallelGCThreads 限制线程数量
————————————————

2.2 Parallel收集器

类似ParNew
新生代复制算法
老年代标记-压缩
更加关注吞吐量
-XX:+UseParallelGC

使用Parallel收集器+ 老年代串行
-XX:+UseParallelOldGC

使用Parallel收集器+ 老年代并行

CMS收集器

Concurrent Mark Sweep 并发标记清除（应用程序线程和GC线程交替执行）
使用标记-清除算法
并发阶段会降低吞吐量（停顿时间减少，吞吐量降低）
老年代收集器（新生代使用ParNew）
-XX:+UseConcMarkSweepGC
CMS运行过程比较复杂，着重实现了标记的过程，可分为

初始标记（会产生全局停顿）

根可以直接关联到的对象
速度快

并发标记（和用户线程一起）

主要标记过程，标记全部对象

重新标记（会产生全局停顿）
. G1收集器

G1是目前技术发展的最前沿成果之一，HotSpot开发团队赋予它的使命是未来可以替换掉JDK1.5中发布的CMS收集器。

与CMS收集器相比G1收集器有以下特点：

(1) 空间整合，G1收集器采用标记整理算法，不会产生内存空间碎片。分配大对象时不会因为无法找到连续空间而提前触发下一次GC。

————————————————

22 重载和重写的区别

重载 Overload

表示同一个类中可以有多个名称相同的方法，但这些方法的参数列表各不相同（即参数个数或类型不同）。

重写 Override

表示子类中的方法可以与父类中的某个方法的名称和参数完全相同，通过子类创建的实例对象调用这个方法时，将调用子类中的定义方法，这相当于把父类中定义的那个完全相同的方法给覆盖了，这也是面向对象编程的多态性的一种表现。子类覆盖父类的方法时，只能比父类抛出更少的异常，或者是抛出父类抛出的异常的子异常，因为子类可以解决父类的一些问题，不能比父类有更多的问题。子类方法的访问权限只能比父类的更大，不能更小。如果父类的方法是private类型，那么，子类则不存在覆盖的限制，相当于子类中增加了一个全新的方法。

23 排序O(N2)，什么排序O(NlogN)，什么排序稳定，什么排序不稳定

24 数据结构中散列表说一下？Hash冲突有什么解决方法？

开放定址法:  当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。

再哈希法：   当发生哈希冲突时使用另一个哈希函数计算地址值，直到冲突不再发生。这种方法不易产生聚
            集，但是增加计算时间，同时需要准备许多哈希函数。

链地址法：   将所有哈希值相同的Key通过链表存储。key按顺序插入到链表中

建立公共溢出区：采用一个溢出表存储产生冲突的关键字。如果公共溢出区还产生冲突，再采用处理冲突方法处理。

散列表（Hash table，也叫哈希表）是一种查找算法，与链表、树等算法不同的是，散列表算法在查找时不需要进行一系列和关键字（关键字是数据元素中某个数据项的值，用以标识一个数据元素）的比较操作。

散列表（也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

23 你说get是幂等的，幂等是你怎么理解？

幂等:
对于同一种行为，如果执行不论多少次，最终的结果都是一致相同的，就称这种行为是幂等的。

(个人理解：不管是一次,还是多次操作，我们返回同样的结果,且不修改状态信息,接口可重复调用)

非幂等:
对于同一种行为，如果最终的结果与执行的次数有关，每次执行后结果都不相同，就称这种行为为非幂等。譬如：累加

#25HashMap的扩容机制—resize()

虽然在hashmap的原理里面有这段，但是这个单独拿出来讲rehash或者resize()也是极好的。

什么时候扩容：当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值(知道这个阈字怎么念吗？不念fa值，念yu值四声)—即当前数组的长度乘以加载因子的值的时候，就要自动扩容啦。

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。

26 http协议状态码301和302的区别

301 redirect: 301 代表永久性转移(Permanently Moved)
302 redirect: 302 代表暂时性转移(Temporarily Moved )

301：请求的网页已被永久移动到新位置。服务器返回此响应（作为对 GET 或 HEAD 请求的响应）时，会自动将请求者转到新位置。

302：服务器目前正从不同位置的网页响应请求，但请求者应继续使用原有位置来进行以后的请求。此代码与响应 GET 和 HEAD 请求的 301 代码类似，会自动将请求者转到不同的位置。

27 TIME_WAIT

什么时候会TIME_WAIT

TCP在关闭的时候有个四次挥手的过程，主动关闭方在四次挥手的最后一个ACK发送之后会变成TIME_WAIT状态。

在JDK1.7中ConcurrentHashMap采用了数组+Segment+分段锁的方式实现。

DK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，内部大量采用CAS操作，这里我简要介绍下CAS。

28 抽象类和接口的含义以及区别

抽象类是什么：

抽象类不能创建实例，它只能作为父类被继承。抽象类是从多个具体类中抽象出来的父类，它具有更高层次的抽象。从多个具有相同特征的类中抽象出一个抽象类，以这个抽象类作为其子类的模板，从而避免了子类的随意性。

(1) 抽象方法只作声明，而不包含实现，可以看成是没有实现体的虚方法

(2) 抽象类不能被实例化

(3) 抽象类可以但不是必须有抽象属性和抽象方法，但是一旦有了抽象方法，就一定要把这个类声明为抽象类

(4) 具体派生类必须覆盖基类的抽象方法

(5) 抽象派生类可以覆盖基类的抽象方法，也可以不覆盖。如果不覆盖，则其具体派生类必须覆盖它们

接口是什么：

(1) 接口不能被实例化

(2) 接口只能包含方法声明

(3) 接口的成员包括方法、属性、索引器、事件

(4) 接口中不能包含常量、字段(域)、构造函数、析构函数、静态成员

接口和抽象类的区别：

（1）抽象类可以有构造方法，接口中不能有构造方法。

（2）抽象类中可以有普通成员变量，接口中没有普通成员变量

（3）抽象类中可以包含静态方法，接口中不能包含静态方法

（4）一个类可以实现多个接口，但只能继承一个抽象类。

（5）接口可以被多重实现，抽象类只能被单一继承

（6）如果抽象类实现接口，则可以把接口中方法映射到抽象类中作为抽象方法而不必实现，而在抽象类的子类中实现接口中方法

29 怎么优化sql

1.1 查看SQL执行频率

1.2 定位执行效率比较低的SQL语句

1.3 通过EXPLAIN分析慢SQL

1.4 通过show profile分析SQL

1.对查询进行优化，应尽量避免全表扫描，首先应考虑在 where 及 order by 涉及的列上建立索引。    
    
2.应尽量避免在 where 子句中对字段进行 null 值判断，否则将导致引擎放弃使用索引而进行全表扫描，如：    
select id from t where num is null    
可以在num上设置默认值0，确保表中num列没有null值，然后这样查询：    
select id from t where num=0    
    
3.应尽量避免在 where 子句中使用!=或<>操作符，否则将引擎放弃使用索引而进行全表扫描。    
    
4.应尽量避免在 where 子句中使用 or 来连接条件，否则将导致引擎放弃使用索引而进行全表扫描，如：    
select id from t where num=10 or num=20    
可以这样查询：    
select id from t where num=10    
union all    
select id from t where num=20    
    
5.in 和 not in 也要慎用，否则会导致全表扫描，如：    
select id from t where num in(1,2,3)    
对于连续的数值，能用 between 就不要用 in 了：    
select id from t where num between 1 and 3    
    
6.下面的查询也将导致全表扫描：    
select id from t where name like '%abc%'    
    
7.应尽量避免在 where 子句中对字段进行表达式操作，这将导致引擎放弃使用索引而进行全表扫描。如：    
select id from t where num/2=100    
应改为:    
select id from t where num=100*2    
    
8.应尽量避免在where子句中对字段进行函数操作，这将导致引擎放弃使用索引而进行全表扫描。如：    
select id from t where substring(name,1,3)='abc'--name以abc开头的id    
应改为:    
select id from t where name like 'abc%'    
    
9.不要在 where 子句中的“=”左边进行函数、算术运算或其他表达式运算，否则系统将可能无法正确使用索引。    
    
10.在使用索引字段作为条件时，如果该索引是复合索引，那么必须使用到该索引中的第一个字段作为条件时才能保证系统使用该索引，    
否则该索引将不会被使用，并且应尽可能的让字段顺序与索引顺序相一致。    
    
11.不要写一些没有意义的查询，如需要生成一个空表结构：    
select col1,col2 into #t from t where 1=0    
这类代码不会返回任何结果集，但是会消耗系统资源的，应改成这样：    
create table #t(...)    
    
12.很多时候用 exists 代替 in 是一个好的选择：    
select num from a where num in(select num from b)    
用下面的语句替换：    
select num from a where exists(select 1 from b where num=a.num)    
    
13.并不是所有索引对查询都有效，SQL是根据表中数据来进行查询优化的，当索引列有大量数据重复时，SQL查询可能不会去利用索引，    
如一表中有字段sex，male、female几乎各一半，那么即使在sex上建了索引也对查询效率起不了作用。    
    
14.索引并不是越多越好，索引固然可以提高相应的 select 的效率，但同时也降低了 insert 及 update 的效率，    
因为 insert 或 update 时有可能会重建索引，所以怎样建索引需要慎重考虑，视具体情况而定。    
一个表的索引数最好不要超过6个，若太多则应考虑一些不常使用到的列上建的索引是否有必要。    
    
15.尽量使用数字型字段，若只含数值信息的字段尽量不要设计为字符型，这会降低查询和连接的性能，并会增加存储开销。    
这是因为引擎在处理查询和连接时会逐个比较字符串中每一个字符，而对于数字型而言只需要比较一次就够了。    
    
16.尽可能的使用 varchar 代替 char ，因为首先变长字段存储空间小，可以节省存储空间，    
其次对于查询来说，在一个相对较小的字段内搜索效率显然要高些。    
    
17.任何地方都不要使用 select * from t ，用具体的字段列表代替“*”，不要返回用不到的任何字段。    
    
18.避免频繁创建和删除临时表，以减少系统表资源的消耗。

19.临时表并不是不可使用，适当地使用它们可以使某些例程更有效，例如，当需要重复引用大型表或常用表中的某个数据集时。但是，对于一次性事件，最好使用导出表。    
    
20.在新建临时表时，如果一次性插入数据量很大，那么可以使用 select into 代替 create table，避免造成大量 log ，    
以提高速度；如果数据量不大，为了缓和系统表的资源，应先create table，然后insert。

30 为什么重写equals还要重写hashcode

用equals比较说明对象相同，但是在HashMap中却以不同的对象存储（没有重写hascode值，两个hascode值，在他看来就是两个对象）。到底这两个对象相等不相等？？？？说明必须重写hashCode()的重要性，

往HashMap添加元素的时候，需要先定位到在数组的位置（hashCode方法）。

如果只重写了 equals 方法，两个对象 equals 返回了true，集合是不允许出现重复元素的，只能插入一个。

此时如果没有重写 hashCode 方法，那么就无法定位到同一个位置，集合还是会插入元素。这样集合中就出现了重复元素了。那么重写的equals方法就没有意义了。
如下图：

如果重写了hashcode方法，确保两个对象都能够定位到相同的位置，那么就可以遍历这条单向链表，使用equals方法判断两个对象是否相同，如果相同，那么就不插入了（HashMap的实现仍然插入，但是覆盖掉旧的value）。如果不相同，就插入到链表的头节点处。

：默认情况下也就是从超类Object继承而来的equals方法与‘==’是完全等价的，比较的都是对象的内存地址，但我们可以重写equals方法，使其按照我们的需求的方式进行比较，如String类重写了equals方法，使其比较的是字符的序列，而不再是内存地址。

31 Redis数据类型

一、Redis的五大数据类型

1.String（字符串）

string是redis最基本的类型，你可以理解成与Memcached一模一样的类型，一个key对应一个value。
string类型是二进制安全的。意思是redis的string可以包含任何数据。比如jpg图片或者序列化的对象。
string类型是Redis最基本的数据类型，一个redis中字符串value最多可以是512M

2.Hash（哈希，类似java里的Map）

Redis hash 是一个键值对集合。
Redis hash是一个string类型的field和value的映射表，hash特别适合用于存储对象。
类似Java里面的Map<String,Object>

3.List（列表）

Redis 列表是简单的字符串列表，按照插入顺序排序。你可以添加一个元素导列表的头部（左边）或者尾部（右边）。
它的底层实际是个链表

4.Set（集合）

Redis的Set是string类型的无序集合。它是通过HashTable实现实现的，

5.Zset(sorted set：有序集合)

zset(sorted set：有序集合)
Redis zset 和 set 一样也是string类型元素的集合,且不允许重复的成员。
不同的是每个元素都会关联一个double类型的分数。
redis正是通过分数来为集合中的成员进行从小到大的排序。zset的成员是唯一的,但分数(score)却可以重复。

32 怎么保证Redis缓存和数据库的数据一致性？缓存雪崩？击穿？穿透？

解决方法：

1、缓存层缓存空值。 –缓存太多空值，占用更多空间。（优化：给个空值过期时间） –存储层更新代码了，缓存层还是空值。（优化：后台设置时主动删除空值，并缓存把值进去）

2、将数据库中所有的查询条件，放到布隆过滤器中。当一个查询请求来临的时候，先经过布隆过滤器进行检查，如果请求存在这个条件中，那么继续执行，如果不在，直接丢弃。

过滤器，将所有可能存在的数据哈希到一个足够大的bitmap中，一个一定不存在的数据会被这个bitmap拦截掉，从而避免了对底层存储系统的查询压力。另外也有一个更为简单粗暴的方法（我们采用的就是这种），如果一个查询返回的数据为空（不管是数据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。

.**缓存穿透**

缓存穿透是指查询一个一定不存在的数据，由于缓存是不命中时被动写的，并且出于容错考虑，如果从存储层查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到存储层去查询，失去了缓存的意义。在流量大时，可能DB就挂掉了，要是有人利用不存在的key频繁攻击我们的应用，这就是漏洞。

1.1**解决方案**

有很多种方法可以有效地解决缓存穿透问题，最常见的则是采用布隆过滤器，将所有可能存在的数据哈希到一个足够大的bitmap中，一个一定不存在的数据会被这个bitmap拦截掉，从而避免了对底层存储系统的查询压力。另外也有一个更为简单粗暴的方法（我们采用的就是这种），如果一个查询返回的数据为空（不管是数据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。

2.**缓存雪崩**

缓存雪崩是指在我们设置缓存时采用了相同的过期时间，导致缓存在某一时刻同时失效，请求全部转发到DB，DB瞬时压力过重雪崩。

2.1**解决方案**

缓存失效时的雪崩效应对底层系统的冲击非常可怕。大多数系统设计者考虑用加锁或者队列的方式保证缓存的单线程（进程）写，从而避免失效时大量的并发请求落到底层存储系统上。这里分享一个简单方案就时讲缓存失效时间分散开，比如我们可以在原有的失效时间基础上增加一个随机值，比如1-5分钟随机，这样每一个缓存的过期时间的重复率就会降低，就很难引发集体失效的事件。

3.**缓存击穿**

对于一些设置了过期时间的key，如果这些key可能会在某些时间点被超高并发地访问，是一种非常“热点”的数据。这个时候，需要考虑一个问题：缓存被“击穿”的问题，这个和缓存雪崩的区别在于这里针对某一key缓存，前者则是很多key。

缓存在某个时间点过期的时候，恰好在这个时间点对这个Key有大量的并发请求过来，这些请求发现缓存过期一般都会从后端DB加载数据并回设到缓存，这个时候大并发的请求可能会瞬间把后端DB压垮。

解决方案

3.**1使用互斥锁(mutex key)**

业界比较常用的做法，是使用mutex。简单地来说，就是在缓存失效的时候（判断拿出来的值为空），不是立即去load db，而是先使用缓存工具的某些带成功操作返回值的操作（比如Redis的SETNX或者Memcache的ADD）去set一个mutex key，当操作返回成功时，再进行load db的操作并回设缓存；否则，就重试整个get缓存的方法。

3.**2 “提前”使用互斥锁(mutex key)：**

在value内部设置1个超时值(timeout1), timeout1比实际的memcache timeout(timeout2)小。当从cache读取到timeout1发现它已经过期时候，马上延长timeout1并重新设置到cache。然后再从数据库加载数据并设置到cache中。

3**.3** “永远不过期”：

这里的“永远不过期”包含两层意思：

(1) 从redis上看，确实没有设置过期时间，这就保证了，不会出现热点key过期问题，也就是“物理”不过期。

(2) 从功能上看，如果不过期，那不就成静态的了吗？所以我们把过期时间存在key对应的value里，如果发现要过期了，通过一个后台的异步线程进行缓存的构建，也就是“逻辑”过期

3.**4资源保护：**

采用netflix的hystrix，可以做资源的隔离保护主线程池，如果把这个应用到缓存的构建也未尝不可

各种方案的优缺点

<dependencies> 
 <dependency> 
 <groupId>com.google.guava</groupId> 
 <artifactId>guava</artifactId> 
 <version>23.0</version> 
 </dependency> 
</dependencies> 
public class BloomFilterTest {
 
 private static final int capacity = 1000000;
 private static final int key = 999998;
 
 private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), capacity);
 
 static {
 for (int i = 0; i < capacity; i++) {
 bloomFilter.put(i);
 }
 }
 
 public static void main(String[] args) {
 /*返回计算机最精确的时间，单位微妙*/
 long start = System.nanoTime();
 
 if (bloomFilter.mightContain(key)) {
 System.out.println("成功过滤到" + key);
 }
 long end = System.nanoTime();
 System.out.println("布隆过滤器消耗时间:" + (end - start));
 int sum = 0;
 for (int i = capacity + 20000; i < capacity + 30000; i++) {
 if (bloomFilter.mightContain(i)) {
 sum = sum + 1;
 }
 }
 System.out.println("错判率为:" + sum);
 }
}
成功过滤到999998
布隆过滤器消耗时间:215518
错判率为:318

33 算法的时间复杂度和空间复杂度的含义，分析一下快排的？

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

34 MySQL外键删除策略？

35 如何做的MySQL优化？

作者：互联网编程

方案概述

方案一：优化现有mysql数据库。优点：不影响现有业务，源程序不需要修改代码，成本最低。缺点：有优化瓶颈，数据量过亿就玩完了。
方案二：升级数据库类型，换一种100%兼容mysql的数据库。优点：不影响现有业务，源程序不需要修改代码，你几乎不需要做任何操作就能提升数据库性能，缺点：多花钱
方案三：一步到位，大数据解决方案，更换newsql/nosql数据库。优点：没有数据容量瓶颈，缺点：需要修改源程序代码，影响业务，总成本最高。

以上三种方案，按顺序使用即可，数据量在亿级别一下的没必要换nosql，开发成本太高。三种方案我都试了一遍，而且都形成了落地解决方案。该过程心中慰问跑路的那几个开发者一万遍 :)

方案一详细说明：优化现有mysql数据库

跟阿里云数据库大佬电话沟通 and Google解决方案 and 问群里大佬，总结如下（都是精华）：

1.数据库设计和表创建时就要考虑性能
2.sql的编写需要注意优化
3.分区
4.分表
5.分库

1.数据库设计和表创建时就要考虑性能

mysql数据库本身高度灵活，造成性能不足，严重依赖开发人员能力。也就是说开发人员能力高，则mysql性能高。这也是很多关系型数据库的通病，所以公司的dba通常工资巨高。

设计表时要注意：

表字段避免null值出现，null值很难查询优化且占用额外的索引空间，推荐默认数字0代替null。
尽量使用INT而非BIGINT，如果非负则加上UNSIGNED（这样数值容量会扩大一倍），当然能使用TINYINT、SMALLINT、MEDIUM_INT更好。
使用枚举或整数代替字符串类型
尽量使用TIMESTAMP而非DATETIME
单表不要有太多字段，建议在20以内
用整型来存IP

索引

索引并不是越多越好，要根据查询有针对性的创建，考虑在WHERE和ORDER BY命令上涉及的列建立索引，可根据EXPLAIN来查看是否用了索引还是全表扫描
应尽量避免在WHERE子句中对字段进行NULL值判断，否则将导致引擎放弃使用索引而进行全表扫描
值分布很稀少的字段不适合建索引，例如”性别”这种只有两三个值的字段
字符字段只建前缀索引
字符字段最好不要做主键
不用外键，由程序保证约束
尽量不用UNIQUE，由程序保证约束
使用多列索引时主意顺序和查询条件保持一致，同时删除不必要的单列索引

简言之就是使用合适的数据类型，选择合适的索引

1.选择合适的数据类型

（1）使用可存下数据的最小的数据类型，整型 < date,time < char,varchar < blob
（2）使用简单的数据类型，整型比字符处理开销更小，因为字符串的比较更复杂。如，int类型存储时间类型，bigint类型转ip函数
（3）使用合理的字段属性长度，固定长度的表会更快。使用enum、char而不是varchar
（4）尽可能使用not null定义字段
（5）尽量少用text，非用不可最好分表

2.选择合适的索引列

（1）查询频繁的列，在where，group by，order by，on从句中出现的列
（2）where条件中<，<=，=，>，>=，between，in，以及like 字符串+通配符（%）出现的列
（3）长度小的列，索引字段越小越好，因为数据库的存储单位是页，一页中能存下的数据越多越好
（4）离散度大（不同的值多）的列，放在联合索引前面。查看离散度，通过统计不同的列值来实现，count越大，离散程度越高：

原开发人员已经跑路，该表早已建立，我无法修改，故：该措辞无法执行，放弃！

2.sql的编写需要注意优化

使用limit对查询结果的记录进行限定
避免select *，将需要查找的字段列出来
使用连接（join）来代替子查询
拆分大的delete或insert语句
可通过开启慢查询日志来找出较慢的SQL
不做列运算：SELECT id WHERE age + 1 = 10，任何对列的操作都将导致表扫描，它包括数据库教程函数、计算表达式等等，查询时要尽可能将操作移至等号右边
sql语句尽可能简单：一条sql只能在一个cpu运算；大语句拆小语句，减少锁时间；一条大sql可以堵死整个库
OR改写成IN：OR的效率是n级别，IN的效率是log(n)级别，in的个数建议控制在200以内
不用函数和触发器，在应用程序实现
避免%xxx式查询
少用JOIN
使用同类型进行比较，比如用’123’和’123’比，123和123比
尽量避免在WHERE子句中使用!=或<>操作符，否则将引擎放弃使用索引而进行全表扫描
对于连续数值，使用BETWEEN不用IN：SELECT id FROM t WHERE num BETWEEN 1 AND 5
列表数据不要拿全表，要使用LIMIT来分页，每页数量也不要太大

原开发人员已经跑路，程序已经完成上线，我无法修改sql，故：该措辞无法执行，放弃！

引擎

目前广泛使用的是MyISAM和InnoDB两种引擎：

\1. MyISAM

MyISAM引擎是MySQL 5.1及之前版本的默认引擎，它的特点是：

不支持行锁，读取时对需要读到的所有表加锁，写入时则对表加排它锁
不支持事务
不支持外键
不支持崩溃后的安全恢复
在表有读取查询的同时，支持往表中插入新纪录
支持BLOB和TEXT的前500个字符索引，支持全文索引
支持延迟更新索引，极大提升写入性能
对于不会进行修改的表，支持压缩表，极大减少磁盘空间占用

\2. InnoDB

InnoDB在MySQL 5.5后成为默认索引，它的特点是：

支持行锁，采用MVCC来支持高并发
支持事务
支持外键
支持崩溃后的安全恢复
不支持全文索引

总体来讲，MyISAM适合SELECT密集型的表，而InnoDB适合INSERT和UPDATE密集型的表

MyISAM速度可能超快，占用存储空间也小，但是程序要求事务支持，故InnoDB是必须的，故该方案无法执行，放弃！

3.分区

MySQL在5.1版引入的分区是一种简单的水平拆分，用户需要在建表的时候加上分区参数，对应用是透明的无需修改代码

对用户来说，分区表是一个独立的逻辑表，但是底层由多个物理子表组成，实现分区的代码实际上是通过对一组底层表的对象封装，但对SQL层来说是一个完全封装底层的黑盒子。MySQL实现分区的方式也意味着索引也是按照分区的子表定义，没有全局索引

用户的SQL语句是需要针对分区表做优化，SQL条件中要带上分区条件的列，从而使查询定位到少量的分区上，否则就会扫描全部分区，可以通过EXPLAIN PARTITIONS来查看某条SQL语句会落在那些分区上，从而进行SQL优化，我测试，查询时不带分区条件的列，也会提高速度，故该措施值得一试。

分区的好处是：

可以让单表存储更多的数据
分区表的数据更容易维护，可以通过清楚整个分区批量删除大量数据，也可以增加新的分区来支持新插入的数据。另外，还可以对一个独立分区进行优化、检查、修复等操作
部分查询能够从查询条件确定只落在少数分区上，速度会很快
分区表的数据还可以分布在不同的物理设备上，从而搞笑利用多个硬件设备
可以使用分区表赖避免某些特殊瓶颈，例如InnoDB单个索引的互斥访问、ext3文件系统的inode锁竞争
可以备份和恢复单个分区

分区的限制和缺点：

一个表最多只能有1024个分区
如果分区字段中有主键或者唯一索引的列，那么所有主键列和唯一索引列都必须包含进来
分区表无法使用外键约束
NULL值会使分区过滤无效
所有分区必须使用相同的存储引擎

分区的类型：

RANGE分区：基于属于一个给定连续区间的列值，把多行分配给分区
LIST分区：类似于按RANGE分区，区别在于LIST分区是基于列值匹配一个离散值集合中的某个值来进行选择
HASH分区：基于用户定义的表达式的返回值来进行选择的分区，该表达式使用将要插入到表中的这些行的列值进行计算。这个函数可以包含MySQL中有效的、产生非负整数值的任何表达式
KEY分区：类似于按HASH分区，区别在于KEY分区只支持计算一列或多列，且MySQL服务器提供其自身的哈希函数。必须有一列或多列包含整数值

具体关于mysql分区的概念请自行google或查询官方文档，我这里只是抛砖引玉了。

我首先根据月份把上网记录表RANGE分区了12份，查询效率提高6倍左右，效果不明显，故：换id为HASH分区，分了64个分区，查询速度提升显著。问题解决！
结果如下：PARTITION BY HASH (id)PARTITIONS 64

select count(*) from readroom_website; –11901336行记录

/* 受影响行数: 0 已找到记录: 1 警告: 0 持续时间 1 查询: 5.734 sec. */

select * from readroom_website where month(accesstime) =11 limit 10;

/* 受影响行数: 0 已找到记录: 10 警告: 0 持续时间 1 查询: 0.719 sec. */

4.分表

分表就是把一张大表，按照如上过程都优化了，还是查询卡死，那就把这个表分成多张表，把一次查询分成多次查询，然后把结果组合返回给用户。

分表分为垂直拆分和水平拆分，通常以某个字段做拆分项。比如以id字段拆分为100张表：表名为 tableName_id%100

但：分表需要修改源程序代码，会给开发带来大量工作，极大的增加了开发成本，故：只适合在开发初期就考虑到了大量数据存在，做好了分表处理，不适合应用上线了再做修改，成本太高！！！而且选择这个方案，都不如选择我提供的第二第三个方案的成本低！故不建议采用。

5.分库

把一个数据库分成多个，建议做个读写分离就行了，真正的做分库也会带来大量的开发成本，得不偿失！不推荐使用。

方案二详细说明：升级数据库，换一个100%兼容mysql的数据库

mysql性能不行，那就换个。为保证源程序代码不修改，保证现有业务平稳迁移，故需要换一个100%兼容mysql的数据库。

今天，数据库的操作越来越成为整个应用的性能瓶颈了，这点对于Web应用尤其明显。关于数据库的性能，这并不只是DBA才需要担心的事，而这更是我们程序员需要去关注的事情。当我们去设计数据库表结构，对操作数据库时（尤其是查表时的SQL语句），我们都需要注意数据操作的性能。这里，我们不会讲过多的SQL语句的优化，而只是针对MySQL这一Web应用最多的数据库。希望下面的这些优化技巧对你有用。

1. 为查询缓存优化你的查询

大多数的MySQL服务器都开启了查询缓存。这是提高性最有效的方法之一，而且这是被MySQL的数据库引擎处理的。当有很多相同的查询被执行了多次的时候，这些查询结果会被放到一个缓存中，这样，后续的相同的查询就不用操作表而直接访问缓存结果了。

这里最主要的问题是，对于程序员来说，这个事情是很容易被忽略的。因为，我们某些查询语句会让MySQL不使用缓存。请看下面的示例：

`// 查询缓存不开启``$r` `= mysql_query(``"SELECT username FROM user WHERE signup_date >= CURDATE()"``);` `// 开启查询缓存``$today` `= ``date``(``"Y-m-d"``);``$r` `= mysql_query(``"SELECT username FROM user WHERE signup_date >= '$today'"``);`

上面两条SQL语句的差别就是 CURDATE() ，MySQL的查询缓存对这个函数不起作用。所以，像 NOW() 和 RAND() 或是其它的诸如此类的SQL函数都不会开启查询缓存，因为这些函数的返回是会不定的易变的。所以，你所需要的就是用一个变量来代替MySQL的函数，从而开启缓存。

2. EXPLAIN 你的 SELECT 查询

使用 EXPLAIN 关键字可以让你知道MySQL是如何处理你的SQL语句的。这可以帮你分析你的查询语句或是表结构的性能瓶颈。

EXPLAIN 的查询结果还会告诉你你的索引主键被如何利用的，你的数据表是如何被搜索和排序的……等等，等等。

挑一个你的SELECT语句（推荐挑选那个最复杂的，有多表联接的），把关键字EXPLAIN加到前面。你可以使用phpmyadmin来做这个事。然后，你会看到一张表格。下面的这个示例中，我们忘记加上了group_id索引，并且有表联接：

当我们为 group_id 字段加上索引后：

我们可以看到，前一个结果显示搜索了 7883 行，而后一个只是搜索了两个表的 9 和 16 行。查看rows列可以让我们找到潜在的性能问题。

3. 当只要一行数据时使用 LIMIT 1

当你查询表的有些时候，你已经知道结果只会有一条结果，但因为你可能需要去fetch游标，或是你也许会去检查返回的记录数。

在这种情况下，加上 LIMIT 1 可以增加性能。这样一样，MySQL数据库引擎会在找到一条数据后停止搜索，而不是继续往后查少下一条符合记录的数据。

下面的示例，只是为了找一下是否有“中国”的用户，很明显，后面的会比前面的更有效率。（请注意，第一条中是Select *，第二条是Select 1）

`// 没有效率的：``$r` `= mysql_query(``"SELECT * FROM user WHERE country = 'China'"``);``if` `(mysql_num_rows(``$r``) > 0) {``    ``// ...``}` `// 有效率的：``$r` `= mysql_query(``"SELECT 1 FROM user WHERE country = 'China' LIMIT 1"``);``if` `(mysql_num_rows(``$r``) > 0) {``    ``// ...``}`

4. 为搜索字段建索引

索引并不一定就是给主键或是唯一的字段。如果在你的表中，有某个字段你总要会经常用来做搜索，那么，请为其建立索引吧。

从上图你可以看到那个搜索字串 “last_name LIKE ‘a%’”，一个是建了索引，一个是没有索引，性能差了4倍左右。

另外，你应该也需要知道什么样的搜索是不能使用正常的索引的。例如，当你需要在一篇大的文章中搜索一个词时，如： “WHERE post_content LIKE ‘%apple%’”，索引可能是没有意义的。你可能需要使用MySQL全文索引或是自己做一个索引（比如说：搜索关键词或是Tag什么的）

5. 在Join表的时候使用相当类型的例，并将其索引

如果你的应用程序有很多 JOIN 查询，你应该确认两个表中Join的字段是被建过索引的。这样，MySQL内部会启动为你优化Join的SQL语句的机制。

而且，这些被用来Join的字段，应该是相同的类型的。例如：如果你要把 DECIMAL 字段和一个 INT 字段Join在一起，MySQL就无法使用它们的索引。对于那些STRING类型，还需要有相同的字符集才行。（两个表的字符集有可能不一样）

`// 在state中查找company``$r` `= mysql_query("SELECT company_name FROM users``    ``LEFT JOIN companies ON (users.state = companies.state)``    ``WHERE users.id = ``$user_id``");` `// 两个 state 字段应该是被建过索引的，而且应该是相当的类型，相同的字符集。`

6. 千万不要 ORDER BY RAND()

想打乱返回的数据行？随机挑一个数据？真不知道谁发明了这种用法，但很多新手很喜欢这样用。但你确不了解这样做有多么可怕的性能问题。

如果你真的想把返回的数据行打乱了，你有N种方法可以达到这个目的。这样使用只让你的数据库的性能呈指数级的下降。这里的问题是：MySQL会不得不去执行RAND()函数（很耗CPU时间），而且这是为了每一行记录去记行，然后再对其排序。就算是你用了Limit 1也无济于事（因为要排序）

下面的示例是随机挑一条记录

`// 千万不要这样做：``$r` `= mysql_query(``"SELECT username FROM user ORDER BY RAND() LIMIT 1"``);` `// 这要会更好：``$r` `= mysql_query(``"SELECT count(*) FROM user"``);``$d` `= mysql_fetch_row(``$r``);``$rand` `= mt_rand(0,``$d``[0] - 1);` `$r` `= mysql_query(``"SELECT username FROM user LIMIT $rand, 1"``);`

7. 避免 SELECT *

从数据库里读出越多的数据，那么查询就会变得越慢。并且，如果你的数据库服务器和WEB服务器是两台独立的服务器的话，这还会增加网络传输的负载。

所以，你应该养成一个需要什么就取什么的好的习惯。

`// 不推荐``$r` `= mysql_query(``"SELECT * FROM user WHERE user_id = 1"``);``$d` `= mysql_fetch_assoc(``$r``);``echo` `"Welcome {$d['username']}"``;` `// 推荐``$r` `= mysql_query(``"SELECT username FROM user WHERE user_id = 1"``);``$d` `= mysql_fetch_assoc(``$r``);``echo` `"Welcome {$d['username']}"``;`

8. 永远为每张表设置一个ID

我们应该为数据库里的每张表都设置一个ID做为其主键，而且最好的是一个INT型的（推荐使用UNSIGNED），并设置上自动增加的AUTO_INCREMENT标志。

就算是你 users 表有一个主键叫 “email”的字段，你也别让它成为主键。使用 VARCHAR 类型来当主键会使用得性能下降。另外，在你的程序中，你应该使用表的ID来构造你的数据结构。

而且，在MySQL数据引擎下，还有一些操作需要使用主键，在这些情况下，主键的性能和设置变得非常重要，比如，集群，分区……

在这里，只有一个情况是例外，那就是“关联表”的“外键”，也就是说，这个表的主键，通过若干个别的表的主键构成。我们把这个情况叫做“外键”。比如：有一个“学生表”有学生的ID，有一个“课程表”有课程ID，那么，“成绩表”就是“关联表”了，其关联了学生表和课程表，在成绩表中，学生ID和课程ID叫“外键”其共同组成主键。

9. 使用 ENUM 而不是 VARCHAR

ENUM 类型是非常快和紧凑的。在实际上，其保存的是 TINYINT，但其外表上显示为字符串。这样一来，用这个字段来做一些选项列表变得相当的完美。

如果你有一个字段，比如“性别”，“国家”，“民族”，“状态”或“部门”，你知道这些字段的取值是有限而且固定的，那么，你应该使用 ENUM 而不是 VARCHAR。

MySQL也有一个“建议”（见第十条）告诉你怎么去重新组织你的表结构。当你有一个 VARCHAR 字段时，这个建议会告诉你把其改成 ENUM 类型。使用 PROCEDURE ANALYSE() 你可以得到相关的建议。

10. 从 PROCEDURE ANALYSE() 取得建议

PROCEDURE ANALYSE() 会让 MySQL 帮你去分析你的字段和其实际的数据，并会给你一些有用的建议。只有表中有实际的数据，这些建议才会变得有用，因为要做一些大的决定是需要有数据作为基础的。

例如，如果你创建了一个 INT 字段作为你的主键，然而并没有太多的数据，那么，PROCEDURE ANALYSE()会建议你把这个字段的类型改成 MEDIUMINT 。或是你使用了一个 VARCHAR 字段，因为数据不多，你可能会得到一个让你把它改成 ENUM 的建议。这些建议，都是可能因为数据不够多，所以决策做得就不够准。

在phpmyadmin里，你可以在查看表时，点击 “Propose table structure” 来查看这些建议

一定要注意，这些只是建议，只有当你的表里的数据越来越多时，这些建议才会变得准确。一定要记住，你才是最终做决定的人。

11. 尽可能的使用 NOT NULL

除非你有一个很特别的原因去使用 NULL 值，你应该总是让你的字段保持 NOT NULL。这看起来好像有点争议，请往下看。

首先，问问你自己“Empty”和“NULL”有多大的区别（如果是INT，那就是0和NULL）？如果你觉得它们之间没有什么区别，那么你就不要使用NULL。（你知道吗？在 Oracle 里，NULL 和 Empty 的字符串是一样的！)

不要以为 NULL 不需要空间，其需要额外的空间，并且，在你进行比较的时候，你的程序会更复杂。当然，这里并不是说你就不能使用NULL了，现实情况是很复杂的，依然会有些情况下，你需要使用NULL值。

下面摘自MySQL自己的文档：

“NULL columns require additional space in the row to record whether their values are NULL. For MyISAM tables, each NULL column takes one bit extra, rounded up to the nearest byte.”

12. Prepared Statements

Prepared Statements很像存储过程，是一种运行在后台的SQL语句集合，我们可以从使用 prepared statements 获得很多好处，无论是性能问题还是安全问题。

Prepared Statements 可以检查一些你绑定好的变量，这样可以保护你的程序不会受到“SQL注入式”攻击。当然，你也可以手动地检查你的这些变量，然而，手动的检查容易出问题，而且很经常会被程序员忘了。当我们使用一些framework或是ORM的时候，这样的问题会好一些。

在性能方面，当一个相同的查询被使用多次的时候，这会为你带来可观的性能优势。你可以给这些Prepared Statements定义一些参数，而MySQL只会解析一次。

虽然最新版本的MySQL在传输Prepared Statements是使用二进制形势，所以这会使得网络传输非常有效率。

当然，也有一些情况下，我们需要避免使用Prepared Statements，因为其不支持查询缓存。但据说版本5.1后支持了。

在PHP中要使用prepared statements，你可以查看其使用手册：mysqli 扩展或是使用数据库抽象层，如： PDO.

`// 创建 prepared statement``if` `(``$stmt` `= ``$mysqli``->prepare(``"SELECT username FROM user WHERE state=?"``)) {` `    ``// 绑定参数``    ``$stmt``->bind_param(``"s"``, ``$state``);` `    ``// 执行``    ``$stmt``->execute();` `    ``// 绑定结果``    ``$stmt``->bind_result(``$username``);` `    ``// 移动游标``    ``$stmt``->fetch();` `    ``printf(``"%s is from %s\n"``, ``$username``, ``$state``);` `    ``$stmt``->close();``}`

13. 无缓冲的查询

正常的情况下，当你在当你在你的脚本中执行一个SQL语句的时候，你的程序会停在那里直到没这个SQL语句返回，然后你的程序再往下继续执行。你可以使用无缓冲查询来改变这个行为。

关于这个事情，在PHP的文档中有一个非常不错的说明： mysql_unbuffered_query() 函数：

“mysql_unbuffered_query() sends the SQL query query to MySQL without automatically fetching and buffering the result rows as mysql_query() does. This saves a considerable amount of memory with SQL queries that produce large result sets, and you can start working on the result set immediately after the first row has been retrieved as you don’t have to wait until the complete SQL query has been performed.”

上面那句话翻译过来是说，mysql_unbuffered_query() 发送一个SQL语句到MySQL而并不像mysql_query()一样去自动fethch和缓存结果。这会相当节约很多可观的内存，尤其是那些会产生大量结果的查询语句，并且，你不需要等到所有的结果都返回，只需要第一行数据返回的时候，你就可以开始马上开始工作于查询结果了。

然而，这会有一些限制。因为你要么把所有行都读走，或是你要在进行下一次的查询前调用 mysql_free_result() 清除结果。而且， mysql_num_rows() 或 mysql_data_seek() 将无法使用。所以，是否使用无缓冲的查询你需要仔细考虑。

14. 把IP地址存成 UNSIGNED INT

很多程序员都会创建一个 VARCHAR(15) 字段来存放字符串形式的IP而不是整形的IP。如果你用整形来存放，只需要4个字节，并且你可以有定长的字段。而且，这会为你带来查询上的优势，尤其是当你需要使用这样的WHERE条件：IP between ip1 and ip2。

我们必需要使用UNSIGNED INT，因为 IP地址会使用整个32位的无符号整形。

而你的查询，你可以使用 INET_ATON() 来把一个字符串IP转成一个整形，并使用 INET_NTOA() 把一个整形转成一个字符串IP。在PHP中，也有这样的函数 ip2long() 和 long2ip()。

1	`$r` `= ``"UPDATE users SET ip = INET_ATON('{$_SERVER['REMOTE_ADDR']}') WHERE user_id = $user_id"``;`

15. 固定长度的表会更快

如果表中的所有字段都是“固定长度”的，整个表会被认为是 “static” 或 “fixed-length”。例如，表中没有如下类型的字段： VARCHAR，TEXT，BLOB。只要你包括了其中一个这些字段，那么这个表就不是“固定长度静态表”了，这样，MySQL 引擎会用另一种方法来处理。

固定长度的表会提高性能，因为MySQL搜寻得会更快一些，因为这些固定的长度是很容易计算下一个数据的偏移量的，所以读取的自然也会很快。而如果字段不是定长的，那么，每一次要找下一条的话，需要程序找到主键。

并且，固定长度的表也更容易被缓存和重建。不过，唯一的副作用是，固定长度的字段会浪费一些空间，因为定长的字段无论你用不用，他都是要分配那么多的空间。

使用“垂直分割”技术（见下一条），你可以分割你的表成为两个一个是定长的，一个则是不定长的。

16. 垂直分割

“垂直分割”是一种把数据库中的表按列变成几张表的方法，这样可以降低表的复杂度和字段的数目，从而达到优化的目的。（以前，在银行做过项目，见过一张表有100多个字段，很恐怖）

示例一：在Users表中有一个字段是家庭地址，这个字段是可选字段，相比起，而且你在数据库操作的时候除了个人信息外，你并不需要经常读取或是改写这个字段。那么，为什么不把他放到另外一张表中呢？这样会让你的表有更好的性能，大家想想是不是，大量的时候，我对于用户表来说，只有用户ID，用户名，口令，用户角色等会被经常使用。小一点的表总是会有好的性能。

示例二：你有一个叫 “last_login” 的字段，它会在每次用户登录时被更新。但是，每次更新时会导致该表的查询缓存被清空。所以，你可以把这个字段放到另一个表中，这样就不会影响你对用户ID，用户名，用户角色的不停地读取了，因为查询缓存会帮你增加很多性能。

另外，你需要注意的是，这些被分出去的字段所形成的表，你不会经常性地去Join他们，不然的话，这样的性能会比不分割时还要差，而且，会是极数级的下降。

17. 拆分大的 DELETE 或 INSERT 语句

如果你需要在一个在线的网站上去执行一个大的 DELETE 或 INSERT 查询，你需要非常小心，要避免你的操作让你的整个网站停止相应。因为这两个操作是会锁表的，表一锁住了，别的操作都进不来了。

Apache 会有很多的子进程或线程。所以，其工作起来相当有效率，而我们的服务器也不希望有太多的子进程，线程和数据库链接，这是极大的占服务器资源的事情，尤其是内存。

如果你把你的表锁上一段时间，比如30秒钟，那么对于一个有很高访问量的站点来说，这30秒所积累的访问进程/线程，数据库链接，打开的文件数，可能不仅仅会让你泊WEB服务Crash，还可能会让你的整台服务器马上掛了。

所以，如果你有一个大的处理，你定你一定把其拆分，使用 LIMIT 条件是一个好的方法。下面是一个示例：

`while` `(1) {``    ``//每次只做1000条``    ``mysql_query(``"DELETE FROM logs WHERE log_date <= '2009-11-01' LIMIT 1000"``);``    ``if` `(mysql_affected_rows() == 0) {``        ``// 没得可删了，退出！``        ``break``;``    ``}``    ``// 每次都要休息一会儿``    ``usleep(50000);``}`

18. 越小的列会越快

对于大多数的数据库引擎来说，硬盘操作可能是最重大的瓶颈。所以，把你的数据变得紧凑会对这种情况非常有帮助，因为这减少了对硬盘的访问。

参看 MySQL 的文档 Storage Requirements 查看所有的数据类型。

如果一个表只会有几列罢了（比如说字典表，配置表），那么，我们就没有理由使用 INT 来做主键，使用 MEDIUMINT, SMALLINT 或是更小的 TINYINT 会更经济一些。如果你不需要记录时间，使用 DATE 要比 DATETIME 好得多。

当然，你也需要留够足够的扩展空间，不然，你日后来干这个事，你会死的很难看，参看Slashdot的例子（2009年11月06日），一个简单的ALTER TABLE语句花了3个多小时，因为里面有一千六百万条数据。

19. 选择正确的存储引擎

在 MySQL 中有两个存储引擎 MyISAM 和 InnoDB，每个引擎都有利有弊。酷壳以前文章《MySQL: InnoDB 还是 MyISAM?》讨论和这个事情。

MyISAM 适合于一些需要大量查询的应用，但其对于有大量写操作并不是很好。甚至你只是需要update一个字段，整个表都会被锁起来，而别的进程，就算是读进程都无法操作直到读操作完成。另外，MyISAM 对于 SELECT COUNT(*) 这类的计算是超快无比的。

InnoDB 的趋势会是一个非常复杂的存储引擎，对于一些小的应用，它会比 MyISAM 还慢。他是它支持“行锁” ，于是在写操作比较多的时候，会更优秀。并且，他还支持更多的高级应用，比如：事务。

下面是MySQL的手册

20. 使用一个对象关系映射器（Object Relational Mapper）

使用 ORM (Object Relational Mapper)，你能够获得可靠的性能增涨。一个ORM可以做的所有事情，也能被手动的编写出来。但是，这需要一个高级专家。

ORM 的最重要的是“Lazy Loading”，也就是说，只有在需要的去取值的时候才会去真正的去做。但你也需要小心这种机制的副作用，因为这很有可能会因为要去创建很多很多小的查询反而会降低性能。

ORM 还可以把你的SQL语句打包成一个事务，这会比单独执行他们快得多得多。

36 MySQL索引结构？介绍一下B树和B+树？MyISAM和InnoDB索引的区别？

MyISAM和InnoDB两个存储引擎的索引虽然都是使用的B+Tree数据结构，但是在具体实现上还是存在不小差别的。InnoDB支持聚簇索引，聚簇索引就是表，所以InnoDB不用像MyISAM那样需要独立的行存储。也就是说，InnoDB的数据文件本身就是索引文件。而MyISAM的数据文件和索引文件是分开存储的。可以通过MyISAM和InnoDB如何存放表的抽象图帮助快速理解。

B-树

B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树
它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图.

图片描述

B-树有如下特点:

所有键值分布在整颗树中；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束；
在关键字全集内做一次查找,性能逼近二分查找；

B+ 树

B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于:

所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
为所有叶子结点增加了一个链指针

简化 B+树如下图

图片描述

为什么使用B-/B+ Tree

红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。MySQL 是基于磁盘的数据库系统,索引往往以索引文件的形式存储的磁盘上,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取，I/O存取的消耗要高几个数量级,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。为什么使用B-/+Tree，还跟磁盘存取原理有关。

局部性原理与磁盘预读

由于磁盘的存取速度与内存之间鸿沟,为了提高效率,要尽量减少磁盘I/O.磁盘往往不是严格按需读取，而是每次都会预读,磁盘读取完需要的数据,会顺序向后读一定长度的数据放入内存。而这样做的理论依据是计算机科学中著名的局部性原理：

1 2	当一个数据被用到时，其附近的数据也通常会马上被使用程序运行期间所需要的数据通常比较集中

由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间)，因此对于具有局部性的程序来说，预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。

1	MySQL(默认使用InnoDB引擎),将记录按照页的方式进行管理,每页大小默认为16K(这个值可以修改).linux 默认页大小为4K

B-/+Tree索引的性能分析

来自张洋的博客:

实际实现B-Tree还需要使用如下技巧：
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个结点只需一次I/O。
假设 B-Tree 的高度为 h,B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。
而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

为什么使用 B+树

B+树更适合外部存储,由于内节点无 data 域,一个结点可以存储更多的内结点,每个节点能索引的范围更大更精确,也意味着 B+树单次磁盘IO的信息量大于B-树,I/O效率更高。
Mysql是一种关系型数据库，区间访问是常见的一种情况，B+树叶节点增加的链指针,加强了区间访问性，可使用在范围区间查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。

36 最短路径算法

1、最短路径问题介绍

问题解释：
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径

解决问题的算法：

迪杰斯特拉算法（Dijkstra算法）
弗洛伊德算法（Floyd算法）
SPFA算法

37 thread的join方法

hread.Join把指定的线程加入到当前线程，可以将两个交替执行的线程合并为顺序执行的线程。比如在线程B中调用了线程A的Join()方法，直到线程A执行完毕后，才会继续执行线程B。

线程的合并的含义就是 将几个并行线程的线程合并为一个单线程执行，应用场景是 当一个线程必须等待另一个线程执行完毕才能执行时，Thread类提供了join方法来完成这个功能，注意，它不是静态方法。

join有3个重载的方法：

1
2
3

void join():当前线程等该加入该线程后面，等待该线程终止。`
`void join(long millis):当前线程等待该线程终止的时间最长为 millis 毫秒。 如果在millis时间内，该线程没有执行完，那么当前线程进入就绪状态，重新等待cpu调度。`
`void join(long millis,int nanos):等待该线程终止的时间最长为 millis 毫秒 + nanos纳秒。如果在millis时间内，该线程没有执行完，那么当前线程进入就绪状态，重新等待cpu调度。

j oin()方法，使调用此方法的线程wait()（在例子中是main线程）,直到调用此方法的线程对象（在例子中是MyThread对象）所在的线程（在例子中是子线程）执行完毕后被唤醒。

38 final

1.final修饰变量，则等同于常量

2.final修饰方法中的参数，称为最终参数。

3.final修饰类，则类不能被继承

4.final修饰方法，则方法不能被重写。



 final 不能修饰抽象类

final修饰的方法可以被重载 但不能被重写

在构造函数内对一个 final 域的写入，与随后把这个被构造对象的引用赋值给一个引用变量，这两个操作之间不能重排序。
初次读一个包含 final 域的对象的引用，与随后初次读这个 final 域，这两个操作之间不能重排序。

39Redis线程安全吗，事务支持一致性吗

Redis是线程安全的吗？

Redis是个单线程程序，所以它是线程安全的。

Redis单线程为什么还能这么快？

Redis是基于内存的，内存的读写速度非常快；
Redis是单线程的，避免了不必要的上下文切换和竞争条件；
Redis使用多路复用技术，可以处理并发的连接。非阻塞I/O内部实现采用epoll，采用了epoll+自己实现的简单的事件框架。epoll中的读、写、关闭、连接都转化成了事件，然后利用epoll的多路复用特性，绝不在io上浪费一点时间。

Redis的事务并不具有一致性（Consistency）。一致性指事务结束后系统的数据依然保证一致。就是说读能马上读到事务操作更新之后的数据（强一致性）。

Redis部分支持事务，不支持的是：强一致性

能干嘛： 一个队列中，一次性、顺序性、排他性的执行一系列命令

常用命令：

MULTI：开启一个事务，MULTI 执行之后，客户端可以继续向服务器发送任意多条命令，这些命令不会立即被执行，而是被放到一个队列中。
EXEC：执行队列中所有的命令
DISCARD：清空事务队列,并放弃执行事务
UNWATCH：取消 WATCH 命令对所有 key 的监视
WATCH key1 key2 ... ：监视一个(或多个) key ，如果在事务执行之前这个(或这些) key 被其他命令所改动，那么事务将被打断。

40 数组与链表的区别？
数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。
链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

41 MySQL分库分表的方案？

42 AtomicInteger怎么实现的？

AtomicInteger内部有一个变量UnSafe：

1	private static final Unsafe unsafe = Unsafe.getUnsafe();

Unsafe类是一个可以执行不安全、容易犯错的操作的一个特殊类。虽然Unsafe类中所有方法都是public的，但是这个类只能在一些被信任的代码中使用。Unsafe的源码可以在这里看 -> UnSafe源码。

Unsafe类可以执行以下几种操作：

分配内存，释放内存：在方法allocateMemory，reallocateMemory，freeMemory中，有点类似c中的malloc，free方法
可以定位对象的属性在内存中的位置，可以修改对象的属性值。使用objectFieldOffset方法
挂起和恢复线程，被封装在LockSupport类中供使用
CAS操作(CompareAndSwap，比较并交换，是一个原子操作)

AtomicInteger中用的就是Unsafe的CAS操作。

Unsafe中的int类型的CAS操作方法：

1
2
3

public final native boolean compareAndSwapInt(Object o, long offset,
                                                int expected,
                                                int x);

参数o就是要进行cas操作的对象，offset参数是内存位置，expected参数就是期望的值，x参数是需要更新到的值。

也就是说，如果我把1这个数字属性更新到2的话，需要这样调用：

1	compareAndSwapInt(this, valueOffset, 1, 2)

valueOffset字段表示内存位置，可以在AtomicInteger对象中使用unsafe得到：

static {
  try {
    valueOffset = unsafe.objectFieldOffset
        (AtomicInteger.class.getDeclaredField("value"));
  } catch (Exception ex) { throw new Error(ex); }
}

AtomicInteger内部使用变量value表示当前的整型值，这个整型变量还是volatile的，表示内存可见性，一个线程修改value之后保证对其他线程的可见性：

1	private volatile int value;

AtomicInteger内部还封装了一下CAS，定义了一个compareAndSet方法，只需要2个参数：

1
2
3

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

addAndGet方法，addAndGet方法内部使用一个死循环，先得到当前的值value，然后再把当前的值加一，加完之后使用cas原子操作让当前值加一处理正确。当然cas原子操作不一定是成功的，所以做了一个死循环，当cas操作成功的时候返回数据。这里由于使用了cas原子操作，所以不会出现多线程处理错误的问题。比如线程A得到current为1，线程B也得到current为1；线程A的next值为2，进行cas操作并且成功的时候，将value修改成了2；这个时候线程B也得到next值为2，当进行cas操作的时候由于expected值已经是2，而不是1了；所以cas操作会失败，下一次循环的时候得到的current就变成了2；也就不会出现多线程处理问题了：

public final int addAndGet(int delta) {
    for (;;) {
        int current = get();
        int next = current + delta;
        if (compareAndSet(current, next))
            return next;
    }
}

incrementAndGet方法，跟addAndGet方法类似，只不过next值变成了current+1：

public final int incrementAndGet() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return next;
    }
}

getAndAdd方法，跟addAndGet方法一样，返回值变成了current：

public final int getAndAdd(int delta) {
    for (;;) {
        int current = get();
        int next = current + delta;
        if (compareAndSet(current, next))
            return current;
    }
}

缺点：

虽然AtomicInteger中的cas操作可以实现非阻塞的原子操作，但是会产生ABA问题，

43 CAS三大问题及解决方式

1、ABA问题
1.1、什么是ABA问题
1.2、ABA问题解决方法
2、循环时间长开销大
3、只能保证一个共享变量的原子操作

1.2、ABA问题解决方法

1、使用版本号

ABA问题的解决思路是使用版本号，每次变量更新的时候版本号加1，那么A->B->A就会变成1A->2B->3A

2、jdk自带原子变量

从jdk1.5开始，jdk的Atomic包里就提供了一个类AtomicStampedReference来解决ABA问题，这个类中的compareAndSet方法的作用就是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值更新为指定的新值

/**
* 如果当前引用等于预期引用并且当前标志等于预期标志
* 则以原子方式将该引用和该标志的值设置为给定新值
*
* @param expectedReference 预期引用值
* @param newReference 新的引用值
* @param expectedStamp 预期标记值
* @param newStamp 新标记值
* @return {@code true} if successful
*/
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair current = pair;
return
#预期引用==当前引用
expectedReference == current.reference &&
#预期标志==当前标志
expectedStamp == current.stamp &&
#新引用==当前引用并且新标志==当前标志
((newReference == current.reference &&
newStamp == current.stamp) ||
#原子更新值
casPair(current, Pair.of(newReference, newStamp)));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2、循环时间长开销大

自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。如果jvm能支持处理器提供的pause指令，那么效率会有一定的提升。pause指令有两个作用：

第一，它可以延迟流水线执行指令（de-pipeline），使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。

第二，它可以避免在退出循环的时候因内存顺序冲突（Memory Order Violation）而引起CPU流水线被清空（CPU Pipeline Flush），从而提高CPU的执行效率。

3、只能保证一个共享变量的原子操作

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁。还有一个方法，就是把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量i=2,j=a合并一下ij=2a，然后用CAS来操作ij。从java1.5开始，JDK提供了AtomicReference类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行CAS操作。
————————————————

44 事务隔离级别，MySQL默认级别，（可重复读），为啥使用可重复读？（可重复读+MVCC达到了序列化要求）

首先创建一个表account。创建表的过程略过（由于InnoDB存储引擎支持事务，所以将表的存储引擎设置为InnoDB）。表的结构如下：

表结构

然后往表中插入两条数据，插入后结果如下：

数据

为了说明问题，我们打开两个控制台分别进行登录来模拟两个用户（暂且成为用户A和用户B吧），并设置当前MySQL会话的事务隔离级别。

一. read uncommitted（读取未提交数据）

具体用户A的操作如下：

1
2
3

set session transaction isolation level read uncommitted；
start transaction;
select * from account;

结果如下：

数据

用户B的操作如下：

1
2
3

set session transaction isolation level read uncommitted；
start transaction;
update account set account=account+200 where id = 1;

随后我们在A用户中查询数据，结果如下：

uncommittedA数据

结论一：

我们将事务隔离级别设置为read uncommitted，即便是事务没有commit，但是我们仍然能读到未提交的数据，这是所有隔离级别中最低的一种。

那么这么做有什么问题吗？

那就是我们在一个事务中可以随随便便读取到其他事务未提交的数据，这还是比较麻烦的，我们叫脏读。我不知道这个名字是怎么起的，为了增强大家的印象，可以这么想，这个事务好轻浮啊，饥渴到连别人没提交的东西都等不及，真脏，呸！

实际上我们的数据改变了吗？

答案是否定的，因为只有事务commit后才会更新到数据库。

二. read committed（可以读取其他事务提交的数据）—大多数数据库默认的隔离级别

同样的办法，我们将用户B所在的会话当前事务隔离级别设置为read commited。

在用户A所在的会话中我们执行下面操作：

1	update account set account=account-200 where id=1;

read committed

我们将id=1的用户account减200。然后查询，发现id=1的用户account变为800。

在B用户所在的会话中查询：

1	select * from account；

结果如下：

read committedB

我们会发现数据并没有变，还是1000。

接着在会话A中我们将事务提交：

commit;

在会话B中查询结果如下：

read committedB1

结论二：

当我们将当前会话的隔离级别设置为read committed的时候，当前会话只能读取到其他事务提交的数据，未提交的数据读不到。

那么这么做有什么问题吗？

那就是我们在会话B同一个事务中，读取到两次不同的结果。这就造成了不可重复读，就是两次读取的结果不同。这种现象叫不可重复读。

三. repeatable read（可重读）—MySQL默认的隔离级别

现在有个需求，就是老板说在同一个事务中查询结果必须保持一致，如果你是数据库，你会怎么做？数据库是这么做的。

在会话B中我们当前事务隔离级别为repeatable read。具体操作如下：

1 2	set session transaction isolation level repeatable read; start transaction;

接着在会话B中查询数据：

repeatablereadB1

我们在A用户所在会话中为表account添加一条数据：

1 2	insert into account(id,account) value(3,1000); commit;

然后我们查询看数据插入是否成功：

repeatable readA

回到B用户所在的会话，我们查询结果：

repeatablereadB2

用户B在他所在的会话中想插入一条新数据id=3，value=1000。来我们操作下：

readpeatablereadB3

什么？竟然插不进去，说我数据重复？

用户B当然不服啊，因为查询到数据只有两条啊，为什么插入id=3说我数据重复了呢？

我再看一遍，莫非我眼花了？

repeatablereadB2

试想一下，在实际中用户A和用户B肯定是相互隔离的，彼此不知道操作什么。用户B碰到这种现象，肯定会炸毛的啊，明明不存在的数据，插入却说主键id=3数据重复了。

结论三：

当我们将当前会话的隔离级别设置为repeatable read的时候，当前会话可以重复读，就是每次读取的结果集都相同，而不管其他事务有没有提交。

有什么问题吗？

管他呢，老板的要求满足了。要一个事务中读取的数据一致（可重复读）。我只能这么做啊，打肿脸装胖子。数据已经发生改变，但是我还是要保持一致。但是，出现了用户B面对的问题，这种现象叫幻读（记得当时就在这个地方纠结好久，到底什么是幻读啊）。

四. serializable（串行化）

同样，我们将用户B所在的会话的事务隔离级别设置为serializable并开启事务。

1 2	set session transaction isolation level serializable; start transaction;

在用户B所在的会话中我们执行下面操作：

1	select * from account;

结果如下：

serializableA

那我们这个时候在用户A所在的会话中写数据呢？

readcommittedA1

我们发现用户A所在的会话陷入等待，如果超时（这个时间可以进行配置），会出现Lock wait time out提示：

readcommittedA2

如果在等待期间我们用户B所在的会话事务提交，那么用户A所在的事务的写操作将提示操作成功。

结论四：

当我们将当前会话的隔离级别设置为serializable的时候，其他会话对该表的写操作将被挂起。可以看到，这是隔离级别中最严格的，但是这样做势必对性能造成影响。所以在实际的选用上，我们要根据当前具体的情况选用合适的。

46 介绍一下Java中的锁？可重入锁如何实现的可重入？

广义上的可重入锁指的是可重复可递归调用的锁，在外层使用锁之后，在内层仍然可以使用，并且不发生死锁（前提得是同一个对象或者class），这样的锁就叫做可重入锁。ReentrantLock和synchronized都是可重入锁，下面是一个用synchronized实现的例子：

在JAVA中，内置锁都是可重入的，也就是说，如果某个线程试图获取一个已经由它自己持有的锁时，那么这个请求会立刻成功，并且会将这个锁的计数值加1，而当线程退出同步代码块时，计数器将会递减，当计数值等于0时，锁释放。

47 浏览器从输入URL到返回结果中间经历了什么？

总体来说分为以下几个过程:

DNS解析
TCP连接
发送HTTP请求
服务器处理请求并返回HTTP报文
浏览器解析渲染页面
连接结束

过程概述

浏览器查找域名对应的 IP 地址；
浏览器根据 IP 地址与服务器建立 socket 连接；
浏览器与服务器通信：浏览器请求，服务器处理请求；
浏览器与服务器断开连接。

48 简单介绍一下关系数据库三范式?

第一范式（1NF)

所谓第一范式（1NF）是指数据库表的每一列都是不可分割的基本数据项，同一列中不能有多个值，即实体中的某个属性不能有多个值或者不能有重复的属性。如果出现重复的属性，就可能需要定义一个新的实体，新的实体由重复的属性构成，新实体与原实体之间为一对多关系。在第一范式（1NF）中表的每一行只包含一个实例的信息。

在任何一个关系数据库中，第一范式（1NF）是对关系模式的基本要求，不满足第一范式（1NF）的数据库就不是关系数据库。

我的理解：列不可分。

第二范式（2NF)

第二范式（2NF）是在第一范式（1NF）的基础上建立起来的，即满足第二范式（2NF）必须先满足第一范式（1NF）。第二范式（2NF）要求数据库表中的每个实例或行必须可以被惟一的区分。为实现区分通常需要为表加上一个列，以存储各个实例的惟一标识。要求实体的属性完全依赖于主关键字。

我的理解：不能部分依赖。即：一张表存在组合主键时，其他非主键字段不能部分依赖。

第三范式（3NF)

满足第三范式（3NF）必须先满足第二范式（2NF）。简而言之，第三范式（3NF）要求一个数据库表中不包含已在其它表中已包含的非主关键字信息。

在第二范式的基础上，数据表中如果不存在非关键字段对任一候选关键字段的传递函数依赖则符合第三范式。

我的理解：不能存在传递依赖。即：除主键外，其他字段必须直接依赖主键,不能间接依赖主键。

49 大家都知道快排的时间复杂度是O(n*ln[n])，那么这个复杂度是如何计算出来的呢？

排序的平均时间复杂度为O（n×log（n）），最糟糕时复杂度为O（n^2）

5 0腾讯面试题04.进程和线程的区别？

但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

1) 简而言之,一个程序至少有一个进程,一个进程至少有一个线程.

2) 线程的划分尺度小于进程，使得多线程程序的并发性高。

3) 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。

51 TCP 三次握手和四次挥手

所谓三次握手(Three-way Handshake)，是指建立一个 TCP 连接时，需要客户端和服务器总共发送3个包。

三次握手的目的是连接服务器指定端口，建立 TCP 连接，并同步连接双方的序列号和确认号，交换 TCP 窗口大小信息。在 socket 编程中，客户端执行 connect() 时。将触发三次握手。

第一次握手(SYN=1, seq=x):

客户端发送一个 TCP 的 SYN 标志位置1的包，指明客户端打算连接的服务器的端口，以及初始序号 X,保存在包头的序列号(Sequence Number)字段里。

发送完毕后，客户端进入 SYN_SEND 状态。
第二次握手(SYN=1, ACK=1, seq=y, ACKnum=x+1):

服务器发回确认包(ACK)应答。即 SYN 标志位和 ACK 标志位均为1。服务器端选择自己 ISN 序列号，放到 Seq 域里，同时将确认序号(Acknowledgement Number)设置为客户的 ISN 加1，即X+1。发送完毕后，服务器端进入 SYN_RCVD 状态。
第三次握手(ACK=1，ACKnum=y+1)

客户端再次发送确认包(ACK)，SYN 标志位为0，ACK 标志位为1，并且把服务器发来 ACK 的序号字段+1，放在确定字段中发送给对方，并且在数据段放写ISN的+1

发送完毕后，客户端进入 ESTABLISHED 状态，当服务器端接收到这个包时，也进入 ESTABLISHED 状态，TCP 握手结束。

三次握手的过程的示意图如下：

three-way-handshake

TCP 的连接的拆除需要发送四个包，因此称为四次挥手(Four-way handshake)，也叫做改进的三次握手。客户端或服务器均可主动发起挥手动作，在 socket 编程中，任何一方执行 close() 操作即可产生挥手操作。

第一次挥手(FIN=1，seq=x)

假设客户端想要关闭连接，客户端发送一个 FIN 标志位置为1的包，表示自己已经没有数据可以发送了，但是仍然可以接受数据。

发送完毕后，客户端进入 FIN_WAIT_1 状态。
第二次挥手(ACK=1，ACKnum=x+1)

服务器端确认客户端的 FIN 包，发送一个确认包，表明自己接受到了客户端关闭连接的请求，但还没有准备好关闭连接。

发送完毕后，服务器端进入 CLOSE_WAIT 状态，客户端接收到这个确认包之后，进入 FIN_WAIT_2 状态，等待服务器端关闭连接。
第三次挥手(FIN=1，seq=y)

服务器端准备好关闭连接时，向客户端发送结束连接请求，FIN 置为1。

发送完毕后，服务器端进入 LAST_ACK 状态，等待来自客户端的最后一个ACK。
第四次挥手(ACK=1，ACKnum=y+1)

客户端接收到来自服务器端的关闭请求，发送一个确认包，并进入 TIME_WAIT状态，等待可能出现的要求重传的 ACK 包。

服务器端接收到这个确认包之后，关闭连接，进入 CLOSED 状态。

客户端等待了某个固定时间（两个最大段生命周期，2MSL，2 Maximum Segment Lifetime）之后，没有收到服务器端的 ACK ，认为服务器端已经正常关闭连接，于是自己也关闭连接，进入 CLOSED状态。

四次挥手的示意图如下：

four-way-handshake 所谓三次握手(Three-way Handshake)，是指建立一个 TCP 连接时，需要客户端和服务器总共发送3个包。

第一次握手(SYN=1, seq=x):

客户端发送一个 TCP 的 SYN 标志位置1的包，指明客户端打算连接的服务器的端口，以及初始序号 X,保存在包头的序列号(Sequence Number)字段里。

发送完毕后，客户端进入 SYN_SEND 状态。
第二次握手(SYN=1, ACK=1, seq=y, ACKnum=x+1):

服务器发回确认包(ACK)应答。即 SYN 标志位和 ACK 标志位均为1。服务器端选择自己 ISN 序列号，放到 Seq 域里，同时将确认序号(Acknowledgement Number)设置为客户的 ISN 加1，即X+1。发送完毕后，服务器端进入 SYN_RCVD 状态。
第三次握手(ACK=1，ACKnum=y+1)

客户端再次发送确认包(ACK)，SYN 标志位为0，ACK 标志位为1，并且把服务器发来 ACK 的序号字段+1，放在确定字段中发送给对方，并且在数据段放写ISN的+1

发送完毕后，客户端进入 ESTABLISHED 状态，当服务器端接收到这个包时，也进入 ESTABLISHED 状态，TCP 握手结束。

三次握手的过程的示意图如下：

three-way-handshake

第一次挥手(FIN=1，seq=x)

假设客户端想要关闭连接，客户端发送一个 FIN 标志位置为1的包，表示自己已经没有数据可以发送了，但是仍然可以接受数据。

发送完毕后，客户端进入 FIN_WAIT_1 状态。
第二次挥手(ACK=1，ACKnum=x+1)

服务器端确认客户端的 FIN 包，发送一个确认包，表明自己接受到了客户端关闭连接的请求，但还没有准备好关闭连接。

发送完毕后，服务器端进入 CLOSE_WAIT 状态，客户端接收到这个确认包之后，进入 FIN_WAIT_2 状态，等待服务器端关闭连接。
第三次挥手(FIN=1，seq=y)

服务器端准备好关闭连接时，向客户端发送结束连接请求，FIN 置为1。

发送完毕后，服务器端进入 LAST_ACK 状态，等待来自客户端的最后一个ACK。
第四次挥手(ACK=1，ACKnum=y+1)

客户端接收到来自服务器端的关闭请求，发送一个确认包，并进入 TIME_WAIT状态，等待可能出现的要求重传的 ACK 包。

服务器端接收到这个确认包之后，关闭连接，进入 CLOSED 状态。

客户端等待了某个固定时间（两个最大段生命周期，2MSL，2 Maximum Segment Lifetime）之后，没有收到服务器端的 ACK ，认为服务器端已经正常关闭连接，于是自己也关闭连接，进入 CLOSED状态。

四次挥手的示意图如下：

four-way-handshake