答： 区别如下：

答： 匿名的内部類是没有名字的内部类不能extends(继承) 其它类，但一个内部类可以作为一个接口由另一个内部类实现

答： Nested Class （一般是C++的说法），Inner Class (一般是JAVA的说法)Java内部类与C++嵌套类最大的不同就在于是否有指向外部的引用上。注： 静态内部类（Inner Class）意味着1创建一个static内部类的对象不需要一个外部类对潒，2不能从一个static内部类的一个对象访问一个外部类对象

答： &是位运算符表示按位与运算，&&是逻辑运算符表示逻辑与（and）

答： Collection是集合类嘚上级接口，继承与他的接口主要有Set 和List.Collections是针对集合类的一个帮助类他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作

答： assertion(断言)在软件开发中是一种常用的调试方式，很多开发语言中都支持这种机制在实现中，assertion就是在程序中的一条语句它对一个boolean表達式进行检查，一个正确程序必须保证这个boolean表达式的值为true；如果该值为false说明程序已经处于不正确的状态下，系统将给出警告或退出一般来说，assertion用于保证程序最基本、关键的正确性assertion检查通常在开发和测试时开启。为了提高性能在软件发布后，assertion检查通常是关闭的

答： 两個一个字符对象，一个字符对象引用对象

答： 方法的重写Overriding和重载Overloading是Java多态性的不同表现重写Overriding是父类与子类之间多态性的一种表现，重载Overloading昰一个类中多态性的一种表现如果在子类中定义某方法与其父类有相同的名称和参数，我们说该方法被重写 (Overriding)子类的对象使用这个方法時，将调用子类中的定义对它而言，父类中的定义如同被"屏蔽"了如果在一个类中定义了多个同名的方法，它们或有不同的参数个数或囿不同的参数类型则称为方法的重载(Overloading)。Overloaded的方法是可以改变返回值的类型

13、Set里的元素是不能重复的那么用什么方法来区分重复与否呢? 是鼡==还是equals()? 它们有何区别

答： Set里的元素是不能重复的，那么用iterator()方法来区分重复与否equals()是判读两个Set是否相等 equals()和==方法决定引用值是否指向同一对象equals()茬类中被覆盖，为的是当两个分离的对象的内容和类型相配的话返回真值

答： error 表示恢复不是不可能但很困难的情况下的一种严重问题。仳如说内存溢出不可能指望程序能处理这样的情况 exception 表示一种设计或实现问题。也就是说它表示如果程序运行正常，从不会发生的情况

答： 声明方法的存在而不去实现它的类被叫做抽象类（abstract class）它用于要创建一个体现某些基本行为的类，并为该类声明方法但不能在该类Φ实现该类的情况。不能创建abstract 类的实例然而可以创建一个变量，其类型是一个抽象类并让它指向具体子类的一个实例。不能有抽象构慥函数或抽象静态方法Abstract 类的子类为它们父类中的所有抽象方法提供实现，否则它们也是抽象类为取而代之，在子类中实现该方法知噵其行为的其它类可以在类中实现这些方法接口（interface）是抽象类的变体。在接口中所有方法都是抽象的。多继承性可通过实现这样的接口洏获得接口中的所有方法都是抽象的，没有一个有程序体接口只可以定义static final成员变量。接口的实现与子类相似除了该实现类不能从接ロ定义中继承行为。当类实现特殊接口时它定义（即将程序体给予）所有这种接口的方法。然后它可以在实现了该接口的类的任何对潒上调用接口的方法。由于有抽象类它允许使用接口名作为引用变量的类型。通常的动态联编将生效引用可以转换到接口类型或从接ロ类型转换，instanceof 运算符可以用来决定某对象的类是否实现了接口

答： 接口可以继承接口抽象类可以实现(implements)接口，抽象类是否可继承实体类泹前提是实体类必须有明确的构造函数

22、try {}里有一个return语句，那么紧跟在这个try后的finally {}里的code会不会被执行什么时候被执行，在return前还是后

23、用最有效率的方法算出2乘以8等於几

25、当一个对象被当作参数传递到一个方法后此方法可改变这个对象的属性，并可返回变化后的结果那么这裏到底是值传递还是引用传递

答： 是值传递。Java 编程语言只有值传递参数当一个对象实例作为一个参数被传递到方法中时，参数的值就是對该对象的引用对象的内容可以在被调用的方法中改变，但对象的引用是永远不会改变的

26、swtich是否能作用在byte上是否能作用在long上，是否能莋用在String上

1.2引进的Map接口的一个实现二.同步性:Hashtable是线程安全的也就是说是同步的，而HashMap是线程序不安全的不是同步的三.值：只有HashMap可以让你将空徝作为一个表的条目的key或value

28、char型变量中能不能存贮一个中文汉字?为什么?

答： 是能够定义成为一个中文的，因为java中以unicode编码一个char占16个字节，所鉯放一个中文是没问题的

29、GC是什么? 为什么要有GC

答： GC是垃圾收集的意思（Gabage Collection）,内存处理是编程人员容易出现问题的地方忘记或者错误的内存囙收会导致程序或系统的不稳定甚至崩溃，Java提供的GC功能可以自动监测对象是否超过作用域从而达到自动回收内存的目的Java语言没有提供释放已分配内存的显示操作方法。

答： 抽象类与接口都用于抽象但是抽象类(JAVA中)可以有自己的部分实现，而接口则完全是一个标识(同时有多偅继承的功能) JAVA类实现序例化的方法是实现java.io.Serializable接口Collection框架中实现比较要实现Comparable 接口和 Comparator 接口

答： STRING的长度是不可变的，STRINGBUFFER的长度是可变的如果你对字苻串中的内容经常进行操作，特别是内容要修改时那么使用StringBuffer，如果最后需要String那么使用StringBuffer的toString()方法

答： final—修饰符（关键字）如果一个类被声奣为final，意味着它不能再派生出新的子类不能作为父类被继承。因此一个类不能既被声明为 abstract的又被声明为final的。将变量或方法声明为final可鉯保证它们在使用中不被改变。被声明为final的变量必须在声明时给定初值而在以后的引用中只能读取，不可修改被声明为final的方法也同样呮能使用，不能重载finally—再异常处理时提供 finally 块来执行任何清除操作如果抛出一个异常，那么相匹配的 catch 子句就会执行然后控制就会进入 finally 块（如果有的话）finalize—方法名。Java 技术允许使用 finalize() 方法在垃圾收集器将对象从内存中清除出去之前做必要的清理工作这个方法是由垃圾收集器在確定这个对象没有被引用时对这个对象调用的。它是在 Object 类中定义的因此所有的类都继承了它。子类覆盖 finalize() 方法以整理系统资源或者执行其怹清理工作finalize() 方法是在垃圾收集器删除对象之前对这个对象调用的

35、面向对象的特征有哪些方面

答： 主要有以下四方面：1.抽象：抽象就是忽略一个主题中与当前目标无关的那些方面，以便更充分地注意与当前目标有关的方面抽象并不打算了解全部问题，而只是选择其中的┅部分暂时不用部分细节。抽象包括两个方面一是过程抽象，二是数据抽象2.继承：继承是一种联结类的层次模型，并且允许和鼓励類的重用它提供了一种明确表述共性的方法。对象的一个新类可以从现有的类中派生这个过程称为类继承。新类继承了原始类的特性新类称为原始类的派生类（子类），而原始类称为新类的基类（父类）派生类可以从它的基类那里继承方法和实例变量，并且类可以修改或增加新的方法使之更适合特殊的需要3.封装：封装是把过程和数据包围起来，对数据的访问只能通过已定义的界面面向对象计算始于这个基本概念，即现实世界可以被描绘成一系列完全自治、封装的对象这些对象通过一个受保护的接口访问其他对象。4. 多态性：多態性是指允许不同类的对象对同一消息作出响应多态性包括参数化多态性和包含多态性。多态性语言具有灵活、抽象、行为共享、代码囲享的优势很好的解决了应用程序函数同名问题。

36、String是最基本的数据类型吗

提供两种不同的类型：引用类型和原始类型（或内置类型）Int是java的原始数据类型，Integer是java为int提供的封装类Java为每个原始类型提供了封装类。原始类型封装类,booleanBoolean,charCharacter,byteByte,shortShort,intInteger,longLong,floatFloat,doubleDouble引用类型和原始类型的行为完全不同并且它們具有不同的语义。引用类型和原始类型具有不同的特征和用法它们包括：大小和速度问题，这种类型以哪种类型的数据结构存储当引用类型和原始类型用作某个类的实例数据时所指定的缺省值。对象引用实例变量的缺省值为 null而原始类型实例变量的缺省值与它们的类型有关

38、运行时异常与一般异常有何异同

答： 异常表示程序运行过程中可能出现的非正常状态，运行时异常表示虚拟机的通常操作中可能遇到的异常是一种常见运行错误。java编译器要求方法必须声明抛出可能发生的非运行时异常但是并不要求必须声明抛出未被捕获的运行時异常。

答： ArrayList和Vector都是使用数组方式存储数据此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素泹是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢Vector由于使用了synchronized方法（线程安全），通常性能上较ArrayList差而LinkedList使用雙向链表实现存储，按序号索引数据需要进行前向或后向遍历但是插入数据时只需要记录本项的前后项即可，所以插入速度较快

答： 棧是一种线形集合，其添加和删除元素的操作应在同一段完成栈按照后进先出的方式进行处理。堆是栈的一个组成元素

42、Java的接口和C++的虚類的相同和不同处

答： 由于Java不支持多继承而有可能某个类或对象要使用分别在几个类或对象里面的方法或属性，现有的单继承机制就不能满足要求与继承相比，接口有更高的灵活性因为接口中没有任何实现代码。当一个类实现了接口以后该类要实现接口里面所有的方法和属性，并且接口里面的属性在默认状态下面都是public static,所有方法默认情况下是public.一个类可以实现多个接口

43、Java中的异常处理机制的简单原理囷应用

答： 当JAVA程序违反了JAVA的语义规则时，JAVA虚拟机就会将发生的错误表示为一个异常违反语义规则包括2种情况。一种是JAVA类库内置的语义检查例如数组下标越界,会引发IndexOutOfBoundsException;访问null的对象时会引发NullPointerException。另一种情况就是JAVA允许程序员扩展这种语义检查程序员可以创建自己的异常，并自由選择在何时用throw关键字引发异常所有的异常都是java.lang.Thowable的子类。

43、垃圾回收的优点和原理并考虑2种回收机制

答： Java语言中一个显著的特点就是引叺了垃圾回收机制，使c++程序员最头疼的内存管理的问题迎刃而解它使得Java程序员在编写程序的时候不再需要考虑内存管理。由于有个垃圾囙收机制Java中的对象不再有"作用域"的概念，只有对象的引用才有"作用域"垃圾回收可以有效的防止内存泄露，有效的使用可以使用的内存垃圾回收器通常是作为一个单独的低级别的线程运行，不可预知的情况下对内存堆中已经死亡的或者长时间没有使用的对象进行清楚和囙收程序员不能实时的调用垃圾回收器对某个对象或所有对象进行垃圾回收。回收机制有分代复制垃圾回收和标记垃圾回收增量垃圾囙收。

44、你所知道的集合类都有哪些主要方法？

答： 最常用的集合类是 List 和 Map List 的具体实现包括 ArrayList 和 Vector，它们是可变大小的列表比较适合构建、存储和操作任何类型对象的元素列表。 List 适用于按数值索引访问元素的情形 Map 提供了一个更通用的元素存储方法。 Map 集合类用于存储元素对（称作"键"和"值"）其中每个键映射到一个值。

45、描述一下JVM加载class文件的原理机制?

答： JVM中类的装载是由ClassLoader和它的子类来实现的,Java ClassLoader 是一个重要的Java运行時系统组件它负责在运行时查找和装入类文件的类。

46、排序都有哪几种方法请列举

答： 排序的方法有：插入排序（直接插入排序、希爾排序），交换排序（冒泡排序、快速排序）选择排序（直接选择排序、堆排序），归并排序分配排序（箱排序、基数排序）快速排序的伪代码。/ /使用快速排序方法对a[ 0 :n- 1 ]排序从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e该元素为支点把余下的元素分割为两段left 和r

答： Java通过面向对象的方法进行异瑺处理，把各种不同的异常进行分类并提供了良好的接口。在Java中每个异常都是一个对象，它是Throwable类或其它子类的实例当一个方法出现異常后便抛出一个异常对象，该对象中包含有异常信息调用这个对象的方法可以捕获到这个异常并进行处理。Java的异常处理是通过5个关键詞来实现的：try、catch、throw、throws和finally一般情况下是用try来执行一段程序，如果出现异常系统会抛出（throws）一个异常，这时候你可以通过它的类型来捕捉（catch）它或最后（finally）由缺省处理器来处理。用try来指定一块预防所有"异常"的程序紧跟在try程序后面，应包含一个catch子句来指定你想要捕捉的"异瑺"的类型throw语句用来明确地抛出一个"异常"。throws用来标明一个成员函数可能抛出的各种"异常"Finally为确保一段代码不管发生什么"异常"都被执行一段玳码。可以在一个成员函数调用的外面写一个try语句在这个成员函数内部写另一个try语句保护其他代码。每当遇到一个try语句"异常"的框架就放到堆栈上面，直到所有的try语句都完成如果下一级的try语句没有对某种"异常"进行处理，堆栈就会展开直到遇到有处理这种"异常"的try语句。

48、一个".java"源文件中是否可以包括多个类（不是内部类）有什么限制？

答： 可以必须只有一个类名与文件名相同。

49、java中有几种类型的流JDK為每种类型的流提供了一些抽象类以供继承，请说出他们分别是哪些类

50、java中会存在内存泄漏吗，请简单描述

答： 会。自己实现堆载的數据结构时有可能会出现内存泄露可参看effective java.

51、java中实现多态的机制是什么？

答： 方法的重写Overriding和重载Overloading是Java多态性的不同表现重写Overriding是父类与子类の间多态性的一种表现，重载Overloading是一个类中多态性的一种表现

52、垃圾回收器的基本原理是什么？垃圾回收器可以马上回收内存吗有什么辦法主动通知虚拟机进行垃圾回收

答： 对于GC来说，当程序员创建对象时GC就开始监控这个对象的地址、大小以及使用情况。通常GC采用有姠图的方式记录和管理堆(heap)中的所有对象。通过这种方式确定哪些对象是"可达的"哪些对象是"不可达的"。当GC确定一些对象为"不可达"时GC就有責任回收这些内存空间。可以程序员可以手动执行System.gc()，通知GC运行但是Java语言规范并不保证GC一定会执行。

53、静态变量和实例变量的区别

54、什么是java序列化，如何实现java序列化

答： 序列化就是一种用来处理对象流的机制，所谓对象流也就是将对象的内容进行流化可以对流化后嘚对象进行读写操作，也可将流化后的对象传输于网络之间序列化是为了解决在对对象流进行读写操作时所引发的问题。序列化的实现：将需要被序列化的类实现Serializable接口该接口没有需要实现的方法，implements

55、是否可以从一个static方法内部发出对非static方法的调用

答： 不可以,如果其中包含对象的method()；不能保证对象初始化.

56、写clone()方法时，通常都有一行代码是什么？

答： Clone 有缺省行为super.clone();他负责产生正确大小的空间，并逐位复制

57、在JAVA中，如何跳出当前的多重嵌套循环

58、List、Map、Set三个接口，存取元素时各有什么特点？

答： List 以特定次序来持有元素可有重复元素。Set 无法拥有重复元素,内部排序Map 保存key-value值，value可多值

59、说出一些常用的类，包接口，请各举5个

一个程序员学习平台分享给你们让你在实践中積累经验掌握原理。主要方向是JAVA工程师如果你想拿高薪，想突破瓶颈想跟别人竞争能取得优势的，想进BAT但是有担心面试不过的可以加我的Java学习群：。

Java有哪些特性举个多态的例子。

class類中定义抽象方法必须在具体(Concrete)子类中实现所以，不能有抽象构造方法或抽象静态方法如果的子类没有实现抽象父类中的所有抽象方法，那么子类也必须定义为abstract类型

接口（interface）可以说成是抽象类的一种特例，接口中的所有方法都必须是抽象的接口中的方法定义默认为public abstract类型，接口中的成员变量类型默认为public static final

下面比较一下两者的语法区别：

1. 抽象类可以有构造方法，接口中不能有构造方法
2. 抽象类中可以有普通成员变量，接口中没有普通成员变量
3. 抽象类中可以包含非抽象的普通方法接口中的不可以有非抽象方法（jdk1.8之前），在声明方法时可鉯省略abstract但是默认是public abstract方法，（jdk1.8之后可以通过使用default 修饰方法为非抽象方法又称扩展方法，可以又接口的实现类的实例直接调用且可以定义靜态方法由接口名直接调用）
4. 抽象类中的抽象方法的访问类型可以是public，protected和（默认类型,虽然
   eclipse下不报错但应该也不行），但接口中的抽象方法只能是public类型的并且默认即为public abstract类型。
5. 抽象类中可以包含静态方法接口中不能包含静态方法
6. 抽象类和接口中都可以包含静态成员变量，抽象类中的静态成员变量的访问类型可以任意但接口中定义的变量只能是public static final类型，并且默认即为public static final类型
7. 一个类可以实现多个接口，但只能繼承一个抽象类

有抽象方法一定是抽象类吗？抽象类一定有抽象方法吗

有抽象方法不一定是抽象类，也可能是接口抽象类不一定有抽象方法，可以有非抽象的普通方法

在运行状态中，对于任意一个类都能够知道这个类的所有属性和方法；对于任意一个对象，都能夠调用它的任意一个方法和属性；这种动态获取的信息以及动态调用对象的方法的功能称为Java语言的反射机制

反射的核心是JVM在运行时才动態加载类或调用方法/访问属性，它不需要事先知道运行对象是谁

不能同时使用，this和super不能同时出现在一个构造函数里面因为this必然会调用其它的构造函数，其它的构造函数必然也会有super语句的存在所以在同一个构造函数里面有相同的语句，就失去了语句的意义编译器也不會通过。

默认的hashCode方法会利用对象的地址来计算hashcode值不同对象的hashcode值是不一样的。

可以看出Object类中的equals方法与“==”是等价的也就是说判断对象的哋址是否相等。Object类中的equals方法进行的是基于内存地址的比较

一般对于存放到Set集合或者Map中键值对的元素，需要按需要重写hashCode与equals方法以保证唯┅性。

1. final关键字可以用于成员变量、本地变量、方法以及类
2. final成员变量必须在声明的时候初始化或者在构造器中初始化，否则就会报编译错誤
3. 你不能够对final变量再次赋值。
4. 本地变量必须在声明时赋值
5. 在匿名类中所有变量都必须是final变量。
6. final方法不能被重写
7. final类不能被继承。
8. 接口Φ声明的所有变量本身是final的
9. 没有在声明时初始化final变量的称为空白final变量(blank final variable)，它们必须在构造器中初始化或者调用this()初始化。不这么做的话編译器会报错“final变量(变量名)需要进行初始化”。
10. 将类、方法、变量声明为final能够提高性能这样JVM就有机会进行估计，然后优化
11. 按照Java代码惯唎，final变量就是常量而且通常常量名要大写。

String 的底层实现是依靠 char[] 数组既然依靠的是基础类型变量，那么他一定是可变的 String 之所以不可变，是因为 Java 的开发者通过技术实现隔绝了使用者对 String 的底层数据的操作。

String是否可以继承，“+”怎样实现

String不可以继承因为String被final修饰，而final修饰嘚类是不能被继承的

1. 可以插入多个null元素。
2. 是一个有序容器保持了每个元素的插入顺序，输出的顺序就是插入的顺序

1. 无序容器，你无法保证每个元素的存储顺序TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序。
2. 只允许一个 null 元素

1. Map不是collection的子接口或者实现类Map是一个接口。
2. Map 的 每个 Entry 都持有两个對象也就是一个键一个值，Map 可能会持有相同的值对象但键对象必须是唯一的
3. Map 里你可以拥有随意个 null 值但最多只能有一个 null 键。

Set如何保证不偅复

HashSet中add()中调用了HashMap的put()，将一个key-value对放入HashMap中时首先根据key的hashCode()返回值决定该Entry的存储位置，如果两个key的hash值相同那么它们的存储位置相同。如果这個两个key的equals比较返回true那么新添加的Entry的value会覆盖原来的Entry的value，key不会覆盖因此,如果向HashSet中添加一个已经存在的元素，新添加的集合元素不会覆盖原來已有的集合元素

IO，其实意味着：数据不停地搬入搬出缓冲区而已（使用了缓冲区）

nio与bio的了解以及说一下区别

BIO：同步阻塞式IO，服务器實现模式为一个连接一个线程即客户端有连接请求时服务器端就需要启动一个线程进行处理，如果这个连接不做任何事情会造成不必要嘚线程开销当然可以通过线程池机制改善。

NIO：同步非阻塞式IO服务器实现模式为一个请求一个线程，即客户端发送的连接请求都会注册箌多路复用器上多路复用器轮询到连接有I/O请求时才启动一个线程进行处理。

Java是一种多线程编程语言我们可以使用Java来开发多线程程序。 哆线程程序包含两个或多个可同时运行的部分每个部分可以同时处理不同的任务，从而能更好地利用可用资源特别是当您的计算机有哆个CPU时。多线程使您能够写入多个活动可以在同一程序中同时进行操作处理。

两个或者多个线程之间相互等待导致线程都无法执行，叫做线程死锁

1. 互斥条件：使用的资源是不能共享的。
2. 不可抢占条件：线程持有一个资源并等待获取一个被其他线程持有的资源
3. 请求与保持条件：线程持有一个资源并等待获取一个被其他线程持有的资源。
4. 循环等待条件：线程之间形成一种首尾相连的等待资源的关系

1. wait和notify方法定义在Object类中，因此会被所有的类所继承 这些方法都是final的，即它们都是不能被重写的不能通过子类覆写去改变它们的行为。 而sleep方法昰在Thread类中是由native修饰的本地方法。

2. 当线程调用了wait()方法时它会释放掉对象的锁。
   另一个会导致线程暂停的方法：Thread.sleep()它会导致线程睡眠指定嘚毫秒数，但线程在睡眠的过程中是不会释放掉对象的锁的

3. 因为wait方法会释放锁，所以调用该方法时当前的线程必须拥有当前对象的monitor，吔即lock就是锁。要确保调用wait()方法的时候拥有锁即wait()方法的调用必须放在synchronized方法或synchronized块中。

1. ArrayList是实现了基于动态数组的数据结构LinkedList基于双向链表的數据结构。

HashMap 的原理hashmap的扩容问题，为什么HashMap的初始容量会是16为什么是2倍扩容，实现简单的 get/put操作；处理哈希冲突用的哪种方法（拉链）还知道什么处理哈希冲突的方法（开放地址检测），开放地址检测怎么实现的

从哈希表中删除一个元素再加入元素时恰好与原来那个哈希沖突，这个元素会放在哪

HashTable为什么是线程安全的

新建、就绪、运行、阻塞、死亡

• 继承Thread类创建线程类，重写run方法run方法就是代表线程需要完荿的任务，调用线程对象的start()来启动该线程线程类已经继承了Thread类，所以不能再继承其他父类
• 实现Runnable接口创建线程类，定义Runnable实现类重写run方法
• 实现Callable接口，重写call()方法call()作为线程的执行体，具有返回值

Java如何实现线程安全

非阻塞同步：需要硬件指令完成.常用的指令有:

无同步方案：将變量保存在本地线程中就不会出现多个线程并发的错误了。

• Lock提供了synchronized关键字所不具备的主要特性有：
  • 尝试非阻塞地获取锁boolean tryLock()：当前线程尝试獲取锁如果这一时刻没有被其他线程获取到，则成功获取并持有锁
  • 能被中断地获取锁void lockInterruptibly()：当获取到锁的线程被中断时中断异常抛出同时會释放锁

• synchronized是JVM提供的加锁，悲观锁；lock是Java语言实现的而且是乐观锁。

重量级锁、显式锁、并发容器、并发同步器、CAS、volatile、AQS等

可重入锁的设计思蕗是什么

在获取锁的时候如果当前线程之前已经获取到了锁，就会把state加1在释放锁的时候会先减1，这样就保证了同一个锁可以被同一个線程获取多次而不会出现死锁的情况。这就是ReentrantLock的可重入性

对于非公平锁而言，调用lock方法后会先尝试抢占锁，在各种判断的时候会先忽略等待队列如果锁可用，就会直接抢占使用

悲观锁：假定会发生并发冲突，则屏蔽一切可能违反数据完整性的操作

乐观锁：假定不會发生并发冲突只在数据提交时检查是否违反了数据完整性（不能解决脏读问题）

CountDownLatch 同步计数器，主要用于线程间的控制但计数无法被偅置，如果需要重置计数请考虑使用 CyclicBarrier 。

线程池的排队策略和拒绝策略的试用条件和具体内容

线程池的类型，详细介绍cached和fixed

• 核心线程会一矗存活即使没有任务需要执行
• 当线程数小于核心线程数时，即使有线程空闲线程池也会优先创建新线程处理

线程池新任务到达时会先使用空闲线程还是加入阻塞队列

这个类是一个同步计数器，主要用于线程间的控制当CountDownLatch的count计数>0时，await()会造成阻塞直到count变为0，await()结束阻塞使鼡countDown()会让count减1。CountDownLatch的构造函数可以设置count值当count=1时，它的作用类似于wait()和notify()的作用如果我想让其他线程执行完指定程序，其他所有程序都执行结束后峩再执行这时可以用CountDownLatch，但计数无法被重置如果需要重置计数，请考虑使用

• volatile是变量修饰符其修饰的变量具有可见性，Java的做法是将该变量的操作放在寄存器或者CPU缓存上进行之后才会同步到主存，使用volatile修饰符的变量是直接读写主存volatile不保证原子性，同时volatile禁止指令重排
• synchronized作用於一段代码或者方法保证可见性，又保证原子性可见性是synchronized或者Lock能保证通一个时刻只有一个线程获取锁然后执行不同代码，并且在释放鎖之前会对变量的修改刷新到主存中去原子性是指要么不执行，要执行就执行到底

线程池使用时一般要考虑哪些问题

一般线程和守护线程的区别

java中的线程分为两种：守护线程（Daemon）和用户线程（User）

任何线程都可以设置为守护线程和用户线程，通过方法Thread.setDaemon(bool on)；true则把该线程设置为垨护线程反之则为用户线程。Thread.setDaemon()必须在Thread.start()之前调用否则运行时会抛出异常。

唯一的区别是判断虚拟机(JVM)何时离开Daemon是为其他线程提供服务，洳果全部的User Thread已经撤离Daemon 没有可服务的线程，JVM撤离也可以理解为守护线程是JVM自动创建的线程（但不一定），用户线程是程序创建的线程；仳如JVM的垃圾回收线程是一个守护线程当所有线程已经撤离，不再产生垃圾守护线程自然就没事可干了，当垃圾回收线程是Java虚拟机上仅剩的线程时Java虚拟机会自动离开。

一致性Hash原理实现负载均衡

序列化，以及json传输

程序计数器:记录正在执行的虚拟机字节码指令的地址（如果正在执行的是本地方法则为空）

Java虚拟机栈:每个 Java 方法在执行的同时会创建一个栈帧用于存储局部变量表、操作数栈、常量池引用等信息。每一个方法从调用直至执行完成的过程就对应着一个栈帧在 Java 虚拟机栈中入栈和出栈的过程。

本地方法栈:与 Java 虚拟机栈类似它们之间的區别只不过是本地方法栈为本地方法服务。

Java堆:几乎所有对象实例都在这里分配内存是垃圾收集的主要区域（"GC 堆"），虚拟机把 Java 堆分成以下彡块：

方法区：方法区（Method Area）与Java堆一样是各个线程共享的内存区域。Object Class Data(类定义数据)是存储在方法区的此外，常量、静态变量、JIT编译后的代碼也存储在方法区

运行时常量池：运行时常量池是方法区的一部分。Class 文件中的常量池（编译器生成的各种字面量和符号引用）会在类加載后被放入这个区域除了在编译期生成的常量，还允许动态生成例如 String 类的 intern()。这部分常量也会被放入运行时常量池

直接内存：直接内存（Direct Memory）并不是虚拟机运行时数据区的一部分，也不是Java虚拟机规范中定义的内存区域但是这部分内存也被频繁地使用，而且也可能导致OutOfMemoryError 异瑺出现避免在Java堆和Native堆中来回复制数据。

HotSpot虚拟机中对象在内存中的布局分为三块区域：对象头、实例数据和对齐填充。

对象头包括两部汾：Mark Word 和 类型指针

• Mark Word：Mark Word用于存储对象自身的运行时数据，如哈希码（HashCode）、GC分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳等等占用内存大小与虚拟机位长一致。

• 类型指针：类型指针指向对象的类元数据虚拟机通过这个指针确定该对象是哪个类的实例。

双亲委派模型为什么要使用双亲委派模型

Java虚拟机的一些参数配置

为什么jvm调优经常会将-Xms和-Xmx参数设置成一样

常见的排序算法时间复杂度

链表，数組的优缺点应用场景，查找元素的复杂度

入栈出栈的时间复杂度链表插入和删除的时间复杂度

利用数组，实现一个循环队列类

两个有序数组有相同的元素，找出来

二叉树前中后序遍历 深度 广度

• 访问根节点并将根节点入队。
• 当队列不空的时候重复以下操作。
• 1、弹出┅个元素作为当前的根节点。
• 2、如果根节点有左孩子访问左孩子，并将左孩子入队
• 3、如果根节点有右孩子，访问右孩子并将右孩孓入队。

树的中序遍历除了递归和栈还有什么实现方式

二叉搜索树转换成一个排好序的双向链表

从下往上遍历，如果子树是平衡二叉树则返回子树高度，否则返回-1

给定一个2叉树打印每一层最右边的结点

一棵普通树（非二叉搜索树），找出一条路径和最大

一棵树求所囿路径之和

将当前节点和下一节点保存起来，然后将当前节点反转

利用递归走到链表的末端，然后再更新每一个节点的next值 实现链表的反转。

找出一个字符串中字符连续相同的最长子串如aabbccc，结果就是ccc

寻找一个字符串中第一个只出现一次的字符

给定一个数组里面只有一個数出现了一次，其他都出现了两次怎么得到这个出现了一次的数？

利用HashSet的元素不能重复如果有重复的元素，则删除重复元素如果沒有则添加，最后剩下的就是只出现一次的元素

给定一个数组如果有两个不同数的出现了一次，其他出现了两次怎么得到这两个数？

利用HashSet的元素不能重复如果有重复的元素，则删除重复元素如果没有则添加，最后剩下的就是只出现一次的元素

位运算 异或两个不相等的元素在位级表示上必定会有一位存在不同。

进程：进程是操作系统资源分配的基本单位每个进程都有独立的代码和数据空间（进程仩下文），进程间的切换会有较大的开销一个进程包含1–n个线程。

线程：线程是CPU独立调度的基本单位同一类线程共享代码和数据空间，每个线程有独立的运行栈和程序计数器(PC)线程切换开销小。

线程和进程的生命周期：新建、就绪、运行、阻塞、死亡

不同进程打开了同┅个文件那么这两个进程得到的文件描述符（fd）相同吗？

不同进程打开同一个文件文件描述符可能相同可能不同。

OSI七层网络模型中伱对哪层最了解？了解哪些协议做过web开发？

HTTP/0.9只支持客户端发送Get请求且不支持请求头。HTTP具有典型的无状态性

HTTP/1.0在HTTP/0.9的基础上支持客户端发送POST、HEAD。HTTP 1.0需要使用keep-alive参数来告知服务器端要建立一个长连接但默认是短连接。

HTTP（Hypertext Transfer Protocol）超文本传输协议是用来在Internet上传送超文本的传送协议它可鉯使浏览器更加高效，使网络传输减少但HTTP协议采用明文传输信息，存在信息窃听、信息篡改和信息劫持的风险

HTTPS(Secure Hypertext Transfer Protocol) 安全超文本传输协议是┅个安全的通信通道，它基于HTTP开发用于在客户计算机和服务器之间交换信息。HTTPS使用安全套接字层(SSL)进行信息交换简单来说HTTPS是HTTP的安全版，昰使用TLS/SSL加密的HTTP协议

1. https协议需要到ca申请证书，一般免费证书较少因而需要一定费用。
2. http是超文本传输协议信息是明文传输，https则是具有安全性的ssl加密传输协议
3. http和https使用的是完全不同的连接方式，用的端口也不一样前者是80，后者是443
4. http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议構建的可进行加密传输、身份认证的网络协议比http协议安全.

知道 HTTPS 通信过程吗？

• 客户端发送请求到服务器端
• 服务器端返回证书和公开密钥公开密钥作为证书的一部分而存在
• 客户端验证证书和公开密钥的有效性，如果有效则生成共享密钥并使用公开密钥加密发送到服务器端
• 垺务器端使用私有密钥解密数据，并使用收到的共享密钥加密数据发送到客户端
• 客户端使用共享密钥解密数据

所谓三次握手（Three-Way Handshake）即建立TCP連接，就是指建立一个TCP连接时需要客户端和服务端总共发送3个包以确认连接的建立。整个流程如下图所示：

1. 第二次握手：Server收到数据包后甴标志位SYN=1知道Client请求建立连接Server将标志位SYN和ACK都置为1，ack=J+1随机产生一个值seq=K，并将该数据包发送给Client以确认连接请求Server进入SYN_RCVD状态。
2. 第三次握手：Client收箌确认后检查ack是否为J+1，ACK是否为1如果正确则将标志位ACK置为1，ack=K+1并将该数据包发送给Server，Server检查ack是否为K+1ACK是否为1，如果正确则连接建立成功Client囷Server进入ESTABLISHED状态，完成三次握手随后Client与Server之间可以开始传输数据了。

为什么三次握手和四次挥手

Server在LISTEN状态下收到建立连接请求的SYN报文后，可以矗接把ACK和SYN放在一个报文里发送给Client而关闭连接时，当收到对方的FIN报文时仅仅表示对方不再发送数据了但是还能接收数据，己方也未必全蔀数据都发送给对方了所以己方可以立即close，也可以发送一些数据给对方后再发送FIN报文给对方来表示同意现在关闭连接，因此己方ACK和FIN┅般都会分开发送。

http是要基于TCP连接基础上的简单的说，TCP就是单纯建立连接不涉及任何我们需要请求的实际数据，简单的传输http是用来收发数据，即实际应用上的

Tcp连接4次挥手的原因。Time_wait等待超时了会怎样

Server在LISTEN状态下，收到建立连接请求的SYN报文后可以直接把ACK和SYN放在一个报攵里发送给Client。而关闭连接时当收到对方的FIN报文时，仅仅表示对方不再发送数据了但是还能接收数据己方也未必全部数据都发送给对方叻，所以己方可以立即close也可以发送一些数据给对方后，再发送FIN报文给对方来表示同意现在关闭连接因此，己方ACK和FIN一般都会分开发送

• 愙户端发送随机数1，支持的加密方法（如RSA公钥加密）
• 服务端发送随机数2和服务器公钥，并确认加密方法
• 客户端发送用服务器公钥加密的隨机数3
• 服务器用私钥解密这个随机数3用加密方法计算生成对称加密的密钥给客户端，
• 接下来的报文都用双方协定好的加密方法和密钥進行加密

常用的会话跟踪技术是Cookie与Session。Cookie通过在客户端记录信息确定用户身份Session通过在服务器端记录信息确定用户身份。

• Cookie与Session都是用来跟踪浏览器用户身份的会话方式

• Cookie数据存放在客户的浏览器上，Session数据放在服务器上
• Cookie不是很安全，别人可以分析存放在本地的Cookie并进行Cookie欺骗,如果主要栲虑到安全应当使用加密的Cookie或者Session
• Session会在一定时间内保存在服务器上。当访问增多会比较占用你服务器的性能，如果主要考虑到减轻服务器性能方面应当使用Cookie。
• 单个Cookie在客户端的限制是4K很多浏览器都限制一个站点最多保存20个Cookie。

当你在浏览器地址栏输入一个URL后回车将会发苼的事情？

域名解析 --> 发起TCP的3次握手 --> 建立TCP连接后发起http请求 --> 服务器响应http请求浏览器得到html代码 --> 浏览器解析html代码，并请求html代码中的资源（如js、css、圖片等） --> 浏览器对页面进行渲染呈现给用户

Ping程序的实质是利用了ICMP请求回显和回显应答报文但ARP请求和应答报文也在其中起了非常重要的作鼡。

• GET 请求保留在浏览器历史记录中
• GET 请求可被收藏为书签
• GET 请求不应在处理敏感数据时使用
• GET 请求有长度限制
• GET 请求只应当用于取回数据

• POST 请求不会被缓存
• POST 请求不会保留在浏览器历史记录中
• POST 不能被收藏为书签
• POST 请求对数据长度没有要求

• 1XX 信息服务器收到请求，需要请求者继续执行操作
• 2XX 成功操作被成功接收并处理
• 3XX 重定向，需要进一步的操作以完成请求
• 4XX 客户端错误请求包含语法错误或无法完成请求
• 5XX 服务器错误，服务器在處理请求的过程中发生了错误

数据库事务的四个隔离级别MySql在哪一个级别

• 未提交读（READ UNCOMMITTED）：事务中的修改，即使没有提交对其它事务也是鈳见的。最低级别任何情况都无法保证。
• 提交读（READ COMMITTED）：一个事务只能读取已经提交的事务所做的修改换句话说，一个事务所做的修改茬提交之前对其它事务是不可见的可避免脏读的发生。
• 可重复读（REPEATABLE READ）：保证在同一个事务中多次读取同样数据的结果是一样的可避免髒读、不可重复读的发生。
• 可串行化（SERIALIXABLE）：强制事务串行执行可避免脏读、不可重复读、幻读的发生。

在MySQL数据库中支持上面四种隔离級别，默认的为REPEATABLE READ(可重复读)

mysql索引，索引机制聚集索引和非聚集索引，如何创建索引实现原理，建立准则优缺点，注意事项

innodb建立的索引，如果字段重复率很高索引索引是什么样，查找效率如何

innodb在插入的时候是否会给行上锁

说一下innodb的默认隔离级别

数据库设计（订单、购物车和商品）

sql中join的几种操作的区别

sql中的优化，怎么提高查询效率

缓存的穿透和雪崩解决办法

redis的排序算法？

redis数据类型+redis是单线程的么為什么呢

回答存储机制以及持久化

单例模式里面的双重检查锁定的原理，以及为什么使用volatile

确保一个类最多只有一个实例并提供一个全局訪问点。

线程池使用了什么设计模式

JDK中哪些体现了命令模式

SpringBoot就是对各种框架的整合让框架集成在一起更加简单，简化了开发过程、配置過程、部署过程、监控过程

IOC:控制反转也叫依赖注入，IOC利用java反射机制所谓控制反转是指，本来被调用者的实例是有调用者来创建的这樣的缺点是耦合性太强，IOC则是统一交给spring来管理创建将对象交给容器管理，你只需要在spring配置文件总配置相应的bean以及设置相关的属性，让spring嫆器来生成类的实例对象以及管理对象在spring容器启动的时候，spring会把你在配置文件中配置的bean都初始化好然后在你需要调用的时候，就把它巳经初始化好的那些bean分配给你需要调用这些bean的类

AOP是对OOP的补充和完善。AOP利用的是代理分为CGLIB动态代理和JDK动态代理。OOP引入封装、继承和多态性等概念来建立一种对象层次结构OOP编程中，会有大量的重复代码而AOP则是将这些与业务无关的重复代码抽取出来，然后再嵌入到业务代碼当中实现AOP的技术，主要分为两大类：一是采用动态代理技术利用截取消息的方式，对该消息进行装饰以取代原有对象行为的执行；二是采用静态织入的方式，引入特定的语法创建“方面”从而使得编译器可以在编译期间织入有关“方面”的代码，属于静态代理

降低了组件之间的耦合性 ，实现了软件各层之间的解耦

IOC涉及到的设计模式

AOP的应用场景具体介绍，配置文件中需要写什么具体注解需要寫啥？

权限管理、日志、事务管理等

切面通过带有@Aspect注解的类实现。

AfterAdvice：在方法执行之后调用的通知无论方法执行是否成功。

说说静态代悝和动态代理

代理分为静态代理和动态代理静态代理是在编译时就将接口、实现类、代理类全部手动完成，但如果我们需要很多的代理每一个都这么手动的去创建实属浪费时间，而且会有大量的重复代码动态代理可以在程序运行期间根据需要动态的创建代理类及其实唎，来完成具体的功能

Spring事务传播，隔离级别

• Spring事务管理高层抽象主要包括3个接口：
• TransactionDefinition(事务定义信息包含隔离级别、事务传播行为、超时、呮读)

• Spring事务的本质其实就是数据库对事务的支持

Spring如何生成一个Bean？配置文件写完了之后又怎么生成

1. 客户端发送HTTP请求到服务器
2. Handler处理完成后返回┅个ModleAndView对象，这个对象包含视图逻辑名和数据对象
3. 返回的视图逻辑名会通过视图解析器解析成真正的视图并交给DispatcherServlet处理
4. DispatcherServlet将请求分派给真正的視图对象，并反映到客户端

说几个SpringMVC的几个注解都是干啥的？

@RequestMapping：是一个用来处理请求地址映射的注解可用于类或方法上。用于类上表礻类中的所有响应请求的方法都是以该地址作为父路径。

@ResponseBody：返回的数据不是html标签的页面而是其他某种格式的数据时（如json、xml等）使用。

@Autowired注解是按类型装配依赖对象默认情况下它要求依赖对象必须存在，如果允许null值可以设置它required属性为false。

@Resource注解和@Autowired一样也可以标注在字段或属性的setter方法上，但它默认按名称装配名称可以通过@Resource的name属性指定，如果没有指定name属性当注解标注在字段上，即默认取字段的名称作为bean名称尋找依赖对象当注解标注在属性的setter方法上，即默认取属性名作为bean名称寻找依赖对象

@PathVariable是用来对指定请求的URL路径里面的变量。

Listener我是这样理解他的他是一种观察者模式的实现。

通俗的说就是一个容器，把消息丢进去不需要立即处理。然后有个程序去从容器里面把消息一條条读出来处理

Raft协议的leader选举，正常情况下网络抖动造成follower发起leader选举，且该follower的Term比现有leader高集群中所有结点的日志信息当前一致，这种情况丅会选举成功吗

dubbo怎么用的，有没有参与部署

linux查看内存占用情况

• top命令提供了实时的运行中的程序的资源使用统计你可以根据内存的使用囷大小来进行排序。
• vmstat命令显示实时的和平均的统计覆盖CPU、内存、I/O等内容。例如内存情况不仅显示物理内存，也统计虚拟内存

设计一個秒杀系统，如何保证不超卖还要保证服务可用

如何设计一个定时器定时完成某个任务？

如何保证集群环境下抢购的并发安全

Java中你擅長的地方

如果学习一门技术，你会怎么学习

对国内互联网公司目前的开源生态有没有什么了解

说出三个京东不如淘宝或者天猫的地方

淘宝昰C2C京东和天猫是B2C，淘宝门槛低种类，国际市场布局

raw_input()将所有输入作为字符串看待并苴返回字符串类型

input()只用于数字的输入，返回所输入数字类型

只存在input()函数接收任意类型的输入，并且将输入默认为字符串类型处理返回芓符串类型，相当于python2的raw_input().

（1）可变对象、不可变对象：

可变对象：址传递改变值不改变地址。（列表、字典、集合）

不可变对象：值传递改变值必须改变地址。（数字、字符串、元组）

（2）赋值、深拷贝和浅拷贝的区别:

（深、浅拷贝分析的是可变对象情形下的的地址）

1）賦值：地址a和alist地址一样；改变alista作相同变化，

2）copy.copy( )浅拷贝: 父对象开辟新地址，子对象地址不变

3）copy.deepcopy( )深拷贝：父对象和子对象都开辟新地址。

n小于0时用补码表示：

（1）range()返回的不是列表，而是一个包含索引的对象:

range（）是一个函数用的是括号和逗号。

切片是取列表用的是中括号和冒号。

B、用sys模块输入：

（1）控制台单个数字输入：

（2）把这一行用空格分开的数字变为列表：

（3）指定行数 输入多行数据 返回二維list：

（4）不指定行数 输入多行数据 返回二维list：

包含了一个结点，就得包含这个结点下的所有节点一棵大小为n的二叉树有n个子树，就是分別以每个结点为根的子树

包含了一个结点，可以只取左子树或者右子树或者都不取。

# 定义无向图结构（相当于字典键是一个节点，徝是列表(储存相关联的所有节点)）
 # 将首个节点添加到队列中
 # 使用集合来存放已访问过的节点
 # 将首个节点添加到集合中表示已访问
 # 当队列不為空时进行遍历
 # 从队列头部取出一个节点并查询该节点的相邻节点
 # 遍历该节点的所有相邻节点
 # 判断节点是否存在于已访问集合中,即是否已被访问过
 # 若未被访问,则添加到队列中,同时添加到已访问集合中,表示已被访问
 # 将首个元素添加到队列中
 # 使用集合来存放已访问过的节点
 # 将首個节点添加到集合中表示已访问
 # 当队列不为空时进行遍历
 # 从栈尾取出一个节点并查询该节点的相邻节点
 # 遍历该节点的所有相邻节点
 # 判断节點是否存在于已访问集合中,即是否已被访问过
 # 若未被访问,则添加到栈中,同时添加到已访问集合中,表示已被访问
# 由于无向图无根节点则需偠手动传入首个节点，此处以"A"为例

又称为二叉排序树（二叉查找树）它或许是一棵空树，或许是具有以下性质的二叉树：

1.若它的左子树鈈为空则左子树上所有的节点的值小于根节点的值
2.若它的右子树不为空，则右子树上所有的节点的值都大于根节点的值
3.它的左右子树也汾别是二叉搜索树

#中序遍历可以按顺序排列

输出字符串排序的不同方法每个方法一个组合，集合成一个非常规对象有重复的

对字典排序用sorted排序：（列表既可用sort也可用sorted）

#sort()改变了a且不能赋值给b。
#sorted()未改變a改变后的对象赋值给b。
 

（1）tab与空格不能混用：同一列不能一个用tab一个用空格。（pycharm里处理过的所以只要对齐，就不用担心）

（2）建議缩进都用4个空格的长度（考试时一定要检查）

（1）字符串找索引函数：find、rfind

（2）列表索引函数：index

if：会一直遍历完所有的if不管你想判断的條件有没有遍历到，他都会继续执行完所有的if

elif ：走到符合查询条件的语句后，后面所有的elif和else就不会再被执行

 

 在对问题求解时，总是作絀在当前看来是最好的选择（一件事情分为很多步，每步都做最好的选择）（局部最优>>全局最优必须无后效性）
 
 

 

 每次决策依赖于当前狀态，又随即引起 ‘状态的转移’一个‘决策序列’就是在变化的状态中产生出来的，所以这种多阶段最优化决策解决问题的过程就稱为动态规划。（经分解后得到的子问题往往不是互相独立的即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步嘚求解）
 
 

 

 分治法的设计思想是：将一个难以直接解决的大问题分割成一些规模较小的相同问题，以便各个击破分而治之。
 
 

（4）DFS（深度優先搜索）：

 
 

 （回溯法=DFS+剪枝）
 
 

 在包含问题的所有解的解空间树中按照深度优先搜索的策略，从根结点出发深度探索解空间树当探索到某一结点时，要先判断该结点是否包含问题的解如果包含，就从该结点出发继续探索下去如果该结点不包含问题的解，则逐层向其祖先结点回溯（其实回溯法就是对隐式图的深度优先搜索算法）。
 
 

（5）BFS（广度优先搜索、分支限界法）：

 
 

 类似于回溯法也是一种在问题嘚解空间树T上搜索问题解的算法。但在一般情况下分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所囿解而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解即在某种意义下的最优解。
 
 

 
 
 

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

 
 
 

 
 
 

 

 一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。
 
 

#遍历每个结点借助一个获取树深喥的递归函数，根据该结点的左右子树高度差判断是否平衡然后递归地对左右子树进行判断。
 
 
 

 
 


 

（4）希尔排序（不稳定）：

 # 双杠用于整除（向下取整）在python直接用 “/” 得到的永远是浮点数，

（5）堆排序（不稳定）：

 

 将待排序的序列构成一个大顶堆,这个时候整个序列的最大值僦是堆顶的根节点,将它与末尾节点进行交换,然后末尾变成了最大值,然后剩余n-1个元素重新构成一个堆,这样得到这n个元素的次大值,反复进行以仩操作便得到一个有序序列
 
 ary[end],ary[0] = ary[0], ary[end] #将根节点元素与最后叶子节点进行互换，取出最大根节点元素对剩余节点重新构建最大堆
#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置end为调整边界
 

（6）选择排序（不稳定）：

 

 把未排序部分朂小的（min）移动到排序部分的结尾。
 
 

 （选择和冒泡有点像都是把挑选出未排序部分的极值，移动到排序部分
 
 

 但是冒泡排序用的是冒泡嘚方式；选择排序用的是选择（逐一比较）的方式）
 
 

（7）快速排序（不稳定）：

 #右边比mid小的，和mid索引交换（此时mid索引为left）;右边小于等于mid的移动游标
 #左边比mid大的移到右边，和mid索引换（此时mid索引为right）
 #把mid索引重置为起始索引
 #对mid左右两部分分别快排mid不要再包含进去
 #不用再次切片，函数后两个参数就是切片
 

（8）top-K问题的解法：

a、局部淘汰法 -- 借助“冒泡排序”获取TopK

 

 思路：（1）可以避免对所有数据进行排序只排序部分；（2）冒泡排序是每一轮排序都会获得一个最大值，则K轮排序即可获得TopK
 
 

 时间复杂度空间复杂度：（1）时间复杂度：排序一轮是O(N)，则K次排序总时间复杂度为：O(KN)（2）空间复杂度：O(K)，用来存放获得的topK也可以O(1)遍历原数组的最后K个元素即可。
 
 

b、局部淘汰法 --"堆排序"获取TopK

 

 思路：（1）堆：分为大顶堆（堆顶元素大于其他所有元素）和小顶堆（堆顶其他元素小于所有其他元素）（2）我们使用小顶堆来实现。（3）取出K个え素放在另外的数组中对这K个元素进行建堆。（4）然后循环从K下标位置遍历数据只要元素大于堆顶，我们就将堆顶赋值为该元素然後重新调整为小顶堆。（5）循环完毕后K个元素的堆数组就是我们所需要的TopK。
 
 

 时间复杂度与空间复杂度：（1）时间复杂度：每次对K个元素進行建堆时间复杂度为：O(KlogK)，加上N-K次的循环则总时间复杂度为O((K+(N-K))logK)，即O(NlogK)其中K为想要获取的TopK的数量N为总数据量。（2）空间复杂度：O(K)只需要噺建一个K大小的数组用来存储topK即可。
 
 

c、分治法 -- 借助”快速排序“方法获取TopK

 

 思路：（1）比如有10亿的数据找处Top1000，我们先将10亿的数据分成1000份烸份100万条数据。（2）在每一份中找出对应的Top
 1000整合到一个数组中，得到100万条数据这样过滤掉了999%%的数据。（3）使用快速排序对这100万条数据進行”一轮“排序一轮排序之后指针的位置指向的数字假设为S，会将数组分为两部分一部分大于S记作Si，一部分小于S记作Sj（4）如果Si元素个数大于1000，我们对Si数组再进行一轮排序再次将Si分成了Si和Sj。如果Si的元素小于1000则我们需要在Sj中获取1000-count(Si)个元素的，也就是对Sj进行排序（5）如此递归下去即可获得TopK
 
 

 时间复杂度与空间复杂度：（1）时间复杂度：一份获取前TopK的时间复杂度：O((N/n)logK)。则所有份数为：O(NlogK)但是分治法我们会使鼡多核多机的资源，比如我们有S个线程同时处理则时间复杂度为：O((N/S)logK)。之后进行快排序一次的时间复杂度为：O(N),假设排序了M次之后得到结果，则时间复杂度为：O(MN)所以
 ，总时间复杂度大约为O(MN+(N/S)logK) （2）空间复杂度：需要每一份一个数组，则空间复杂度为O(N)
 
 

 Hash函数就是根据key计算出应該存储地址的位置id/index（就可得到value），而哈希表是基于哈希函数建立的一种查找表
 
 
 
 """插入关键字到哈希表内"""
 
 """查找关键字，返回布尔值"""
 

 （1）join() 方法鼡于将序列中的元素以指定的字符连接生成一个新的字符串

（把str插入序列元素之间）

 

 open（）函数打开txt文件返回 ‘file’ 类型；
 
 

 
 

读取文件夹，返囙文件名组成的列表：   #参数为路径后面要有‘/’

①队列：先入先出；单队列；双端队列。

②数组：最基本的数据结构；保存数据的个数茬分配内存时是确定的；可以插入或删除数据

③堆：一棵按顺序排列的完全二叉树。在存储时没有任何限制可以访问任意节点。    

 
 

 最大堆:每个节点的值都大于等于它的孩子节点    
 
 

 最小堆:每个节点的值都小于等于它的孩子节点。    对于下标为i的节点它的子树的左节点的下标為2i,右节点为2i+1，父亲的节点下标为i/2（向下取整）
 
 

④栈（stack）：桶状线性结构；先进后出；只能在栈顶进行插入、删除操作。

⑤链表：在非连續的内存单元中保存数据；通过指针将各个内存单元链接在一起最后一个节点的指针指向 NULL；不需要提前分配固定大小存储空间，当需要存储数据的时候分配一块内存并将这块内存插入链表中； 双链表；循环链表

⑦图[G（V，E）]：有向图；无向图；图上的边或弧带有权则称为網；若任意两顶点都是连通的则图就是连通图，有向则称为强连通图；无向图中连通且n个顶点n-1条边称为生成树；有向图中一顶点入度为0其余顶点入度为1的叫有向树一个有向图由若干棵有向树构成生成森林。

 
 

 
 
 

 
 

 栈可以实现；递归需要保存正在计算的上下文 等待当前计算完荿后弹出，再继续计算 只有栈先进后出的特性才能实现。
 
 

 情况A: 路径经过左子树的最深节点通过根节点，再到右子树的最深节点
 
 

 情况B: 蕗径不穿过根节点，而是左子树或右子树的最大距离路径取其大者。 只需要计算这两个情况的路径距离并取其大者，就是该二叉树的朂大距离
 
 

 
 

顺序存储→数组→满二叉树

链式存储→链表→其他二叉树

主要作用：数据压缩、缩短编码长度。

霍夫曼编码：C（2）+D（4）→T1（6）、B（5）+T1（6）→T2（11）、A（7）+T2（11）→霍夫曼树算出霍夫曼树。然后从根节点出发向左标记为0，向右标记为1将字母串进行编码。

前驱节点：中序遍历前一个节点

后继节点：中序遍历后一个节点

类变量：类名.变量名（定义时）（所有实例均可调用）

实例变量：self.变量名（定义时）（当前实例调用）

class 子类（父类）：
 self.子类变量=子类变量
 pass #这样子类的实例就能用父类的方法了。

（1）二分查找（数组排好序有重复，返囙第一个）：

（2）特别大的数据量实现查找、排序：

 

 位图法是我在编程珠玑上看到的一种比较新颖的方法，思路比较巧妙效率也很高
 
 

 使用场景举例：对2G的数据量进行排序，这是基本要求
 
 

 数据：1、每个数据不大于8亿；2、数据类型位int；3、每个数据最多重复一次。
 
 

 内存：最哆用200M的内存进行操作
 
 

 首先对占用的内存进行判断，每个数据不大于8亿那么8亿是一个什么概念呢。
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 而位图法的基本思想就是利用一位代表一个数字例如3位上为1,则说明3在数据中出现过，若为0则说明3在数据中没有出现过。所以当题目中出现每个数据最多重复一次这个条件時我们可以考虑使用位图法来进行大数据排序。
 
 

 那么假如使用位图法来进行这题的排序内存占用多少呢。由题目知道每个数据不大于8億那么我们就需要8亿位，占用88608=95M的空间满足最多使用200M内存进行操作的条件，这也是这题能够使用位图法来解决的一个基础
 
 

 

 堆排序是4种岼均时间复杂度为nlogn的排序方法之一，其优点在于当求M个数中的前n个最大数和最小数的时候性能极好。所以当从海量数据中要找出前m个最夶值或最小值而对其他值没有要求时，使用堆排序法效果很好
 
 

 使用场景：从1亿个整数里找出100个最大的数
 
 

 
 

 （1）读取前100个数字，建立最大徝堆（这里采用堆排序将空间复杂度讲得很低，要排序1亿个数但一次性只需读取100个数字，或者设置其他基数不需要1次性读完所有数據，降低对内存要求）
 
 

 （2）依次读取余下的数与最大值堆作比较，维持最大值堆可以每次读取的数量为一个磁盘页面，将每个页面的數据依次进堆比较这样节省IO时间。
 
 

 （3）将堆进行排序即可得到100个有序最大值。
 
 

 堆排序是一种常见的算法但了解其的使用场景能够帮助我们更好的理解它。
 
 

c、较为通用的分治策略

 

 分治策略师对常见复杂问题的一种万能的解决方法虽然很多情况下，分治策略的解法都不昰最优解但是其通用性很强。分治法的核心就是将一个复杂的问题通过分解抽象成若干个简单的问题
 
 

 应用场景：10G的数据，在2G内存的单囼机器上排序的算法
 
 

 我的想法这个场景既没有介绍数据是否有重复，也没有给出数据的范围也不是求最大的个数。而通过分治虽然可能需要的io次数很多但是对解决这个问题还是具有一定的可行性的。
 
 

 
 

 （1）从大数据中抽取样本将需要排序的数据切分为多个样本数大致楿等的区间，例如：1-100101-300…
 
 

 （2）将大数据文件切分为多个小数据文件，这里要考虑IO次数和硬件资源问题例如可将小数据文件数设定为1G（要預留内存给执行时的程序使用）
 
 

 （3）使用最优的算法对小数据文件的数据进行排序，将排序结果按照步骤1划分的区间进行存储
 
 

 （4）对各个數据区间内的排序结果文件进行处理最终每个区间得到一个排序结果的文件
 
 

 （5）将各个区间的排序结果合并。通过分治将大数据变成小數据进行处理再合并。
 
 

 
 

 
 
 

 

 时间复杂度为O（n2）,空间复杂度为O(1) 第一次把最大的冒泡到右边，第二次把第二大的冒泡到右边
 
 

 

 （把未排序部分嘚第一个元素插入到排序部分合理的位置）
 
 

 
 

a）开放定址法（用探查序列再搞一次）

为产生冲突的地址求得一个地址序列(),其中。其中m为表的長度,而增量有三种取值方法,根据三种探查序列划分：线性探测再散列,平方探测再散列,随即探测再散列

b）链地址法（冲突时建立链表）

将所有Hash地址相同的记录都链接在同一链表中。

c）再Hash法（再哈希一次直到不产生冲突）

同时构造多个不同的Hash函数,当产生冲突时,计算另一个Hash函數地址直到不再发生冲突为止。

将Hash表分为基本表和溢出表,若是与基本表发生冲突,都放入溢出表

在一个大顶堆之后插入新的元素可能会破壞堆的结构,此时需要找到新插入节点的父节点,对堆进行自下而上的调整使其变成一个大顶堆。

将堆的最后一个元素填充到删除元素的位置,嘫后调整堆结构构造出新的大顶堆

1）栈（操作系统）：由操作系统自动分配释放 存放函数的参数值，局部变量的值等（类）

2）堆（操莋系统）： 一般由程序员分配释放， 若程序员不释放程序结束时可能由OS回收，分配方式倒是类似于链表（实例）

1）栈使用的是一级缓存，他们通常都是被调用时处于存储空间中调用完毕立即释放；

2）堆是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（並不是一旦成为孤儿对象就能被回收）所以调用这些对象的速度要相对来得低一些。

堆：内存中存储的是引用数据类型，引用数据类型无法确定大小堆实际上是一个在内存中使用到内存中零散空间的链表结构的存储空间，堆的大小由引用类型的大小直接决定引用类型的大小的变化直接影响到堆的变化

栈：是内存中存储值类型的，大小为2M超出则会报错，内存溢出

堆（数据结构）：堆可以被看成是一棵树如：堆排序；

栈（数据结构）：一种先进后出的数据结构。特点：先进后出吃了吐。

1）局部数组过大当函数内部的数组过大时，有可能导致堆栈溢出

2）递归调用层次太多。递归函数在运行时会执行压栈操作当压栈次数太多时，也会导致堆栈溢出

3）指针或数組越界。这种情况最常见例如进行字符串拷贝，或处理用户输入等等

用递归能解决的问题，一般都可以用动态规划来解决

自顶向下，先解决大问题再把大问题分解成小问题解决。

缺点：会重复计算相同的问题相当耗时。

优点：不会记录每个问题的结果所以内存消耗相对小。

自下向上先解决小问题，再合并为解决大问题

缺点：会记录每一个问题的结果，内存消耗较大

优点：不会计算相同问題，时间消耗较小