欢迎在我的 Github 上下载该面经 https://github.com/haiyusun/Interview-Notes
Java 基础
1,Hashmap 是怎么实现的, 底层原理?
HashMap 的底层使用数组 + 链表 / 红黑树实现.
transient Node<K,V>[] table; 这表示 HashMap 是 Node 数组构成, 其中 Node 类的实现如下, 可以看出这其实就是个链表, 链表的每个结点是一个 < K,V > 映射.
- static class Node<K,V> implements Map.Entry<K,V> {
- final int hash;
- final K key;
- V value;
- Node<K,V> next;
- }
HashMap 的每个下标都存放了一条链表.
常量 / 变量定义
- /* 常量定义 */
- // 初始容量为 16
- static final int DEFAULT_INITIAL_CAPACITY = 1 <<4;
- // 最大容量
- static final int MAXIMUM_CAPACITY = 1 << 30;
- // 负载因子, 当键值对个数达到 DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR 会触发 resize 扩容
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- // 当链表长度大于 8, 且数组长度大于 MIN_TREEIFY_CAPACITY, 就会转为红黑树
- static final int TREEIFY_THRESHOLD = 8;
- // 当 resize 时候发现链表长度小于 6 时, 从红黑树退化为链表
- static final int UNTREEIFY_THRESHOLD = 6;
- // 在要将链表转为红黑树之前, 再进行一次判断, 若数组容量小于该值, 则用 resize 扩容, 放弃转为红黑树
- // 主要是为了在建立 Map 的初期, 放置过多键值对进入同一个数组下标中, 而导致不必要的链表 ->红黑树的转化, 此时扩容即可, 可有效减少冲突
- static final int MIN_TREEIFY_CAPACITY = 64;
- /* 变量定义 */
- // 键值对的个数
- transient int size;
- // 键值对的个数大于该值时候, 会触发扩容
- int threshold;
- // 非线程安全的集合类中几乎都有这个变量的影子, 每次结构被修改都会更新该值, 表示被修改的次数
- transient int modCount;
关于 modCount 的作用见这篇 blog
在一个迭代器初始的时候会赋予它调用这个迭代器的对象的 modCount, 如果在迭代器遍历的过程中, 一旦发现这个对象的 modCount 和迭代器中存储的 modCount 不一样那就抛异常.
Fail-Fast 机制: java.util.HashMap 不是线程安全的, 因此如果在使用迭代器的过程中有其他线程修改了 map, 那么将抛出 ConcurrentModificationException, 这就是所谓 fail-fast 策略. 这一策略在源码中的实现是通过 modCount 域, modCount 顾名思义就是修改次数, 对 HashMap 内容的修改都将增加这个值, 那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount. 在迭代过程中, 判断 modCount 跟 expectedModCount 是否相等, 如果不相等就表示已经有其他线程修改了 Map.
注意初始容量和扩容后的容量都必须是 2 的次幂, 为什么呢?
hash 方法
先看散列方法
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
HashMap 的散列方法如上, 其实就是将 hash 值的高 16 位和低 16 位异或, 我们将马上看到 hash 在与 n - 1 相与的时候, 高位的信息也被考虑了, 能使碰撞的概率减小, 散列得更均匀.
在 JDK 8 中, HashMap 的 putVal 方法中有这么一句
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
关键就是这句(n - 1) & hash, 这行代码是把待插入的结点散列到数组中某个下标中, 其中 hash 就是通过上面的方法的得到的, 为待插入 Node 的 key 的 hash 值, n 是 table 的容量即 table.length,2 的次幂用二进制表示的话, 只有最高位为 1, 其余为都是 0. 减去 1, 刚好就反了过来. 比如 16 的二进制表示为 10000, 减去 1 后的二进制表示为 01111, 除了最高位其余各位都是 1, 保证了在相与时, 可以使得散列值分布得更均匀(因为如果某位为 0 比如 1011, 那么结点永远不会被散列到 1111 这个位置), 且当 n 为 2 的次幂时候有(n - 1) & hash == hash % n, 举个例子, 比如 hash 等于 6 时候, 01111 和 00110 相与就是 00110,hash 等于 16 时, 相与就等于 0 了, 多举几个例子便可以验证这一结论. 最后来回答为什么 HashMap 的容量要始终保持 2 的次幂
使散列值分布均匀
位运算的效率比取余的效率高
注意 table.length 是数组的容量, 而 transient int size 表示存入 Map 中的键值对数.
int threshold 表示临界值, 当键值对的个数大于临界值, 就会扩容. threshold 的更新是由下面的方法完成的.
- static final int tableSizeFor(int cap) {
- int n = cap - 1;
- n |= n>>> 1;
- n |= n>>> 2;
- n |= n>>> 4;
- n |= n>>> 8;
- n |= n>>> 16;
- return (n <0) ? 1 : (n>= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
- }
该方法返回大于等于 cap 的最小的二次幂数值. 比如 cap 为 16, 就返回 16,cap 为 17 就返回 32.
put 方法
put 方法主要由 putVal 方法实现:
如果没有产生 hash 冲突, 直接在数组
tab[i = (n - 1) & hash]
处新建一个结点;
否则, 发生了 hash 冲突, 此时 key 如果和头结点的 key 相同, 找到要更新的结点, 直接跳到最后去更新值
否则, 如果数组下标中的类型是 TreeNode, 就插入到红黑树中
如果只是普通的链表, 就在链表中查找, 找到 key 相同的结点就跳出, 到最后去更新值; 到链表尾也没有找到就在尾部插入一个新结点. 接着判断此时链表长度若大于 8 的话, 还需要将链表转为红黑树(注意在要将链表转为红黑树之前, 再进行一次判断, 若数组容量小于 64, 则用 resize 扩容, 放弃转为红黑树)
get 方法
get 方法由 getNode 方法实现:
如果在数组下标的链表头就找到 key 相同的, 那么返回链表头的值
否则如果数组下标处的类型是 TreeNode, 就在红黑树中查找
否则就是在普通链表中查找了
都找不到就返回 null
remove 方法的流程大致和 get 方法类似.
HashMap 的扩容, resize()过程?
newCap = oldCap <<1
resize 方法中有这么一句, 说明是扩容后数组大小是原数组的两倍.
- Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- table = newTab;
- if (oldTab != null) {
- for (int j = 0; j <oldCap; ++j) {
- Node<K,V> e;
- if ((e = oldTab[j]) != null) {
- oldTab[j] = null;
- // 如果数组中只有一个元素, 即只有一个头结点, 重新哈希到新数组的某个下标
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e;
- else if (e instanceof TreeNode)
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- else { // preserve order
- // 数组下标处的链表长度大于 1, 非红黑树的情况
- Node<K,V> loHead = null, loTail = null;
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- do {
- next = e.next;
- // oldCap 是 2 的次幂, 最高位是 1, 其余为是 0, 哈希值和其相与, 根据哈希值的最高位是 1 还是 0, 链表被拆分成两条, 哈希值最高位是 0 分到 loHead.
- if ((e.hash & oldCap) == 0) {
- if (loTail == null)
- loHead = e;
- else
- loTail.next = e;
- loTail = e;
- }
- // 哈希值最高位是 1 分到 hiHead
- else {
- if (hiTail == null)
- hiHead = e;
- else
- hiTail.next = e;
- hiTail = e;
- }
- } while ((e = next) != null);
- if (loTail != null) {
- loTail.next = null;
- // loHead 挂到新数组 [原下标] 处;
- newTab[j] = loHead;
- }
- if (hiTail != null) {
- hiTail.next = null;
- // hiHead 挂到新数组中 [原下标 + oldCap] 处
- newTab[j + oldCap] = hiHead;
- }
- }
- }
- }
- }
- return newTab;
举个例子, 比如 oldCap 是 16, 二进制表示是 10000,hash 值的后五位和 oldCap 相与, 因为 oldCap 的最高位 (从右往左数的第 5 位) 是 1 其余位是 0, 因此 hash 值的该位是 0 的所有元素被分到一条链表, 挂到新数组中原下标处, hash 值该位为 1 的被分到另外一条链表, 挂到新数组中原下标 + oldCap 处. 举个例子: 桶 0 中的元素其 hash 值后五位是 0XXXX 的就被分到桶 0 种, 其 hash 值后五位是 1XXXX 就被分到桶 4 中.
2,Java 中的错误和异常?
Java 中的所有异常都是 Throwable 的子类对象, Error 类和 Exception 类是 Throwable 类的两个直接子类.
Error: 包括一些严重的, 程序不能处理的系统错误类. 这些错误一般不是程序造成的, 比如 StackOverflowError 和 OutOfMemoryError.
Exception: 异常分为运行时异常和检查型异常.
检查型异常要求必须对异常进行处理, 要么往上抛, 要么 try-catch 捕获, 不然不能通过编译. 这类异常比较常见的是 IOException.
运行时异常, 可处理可不处理, 在编译时可以通过, 异常在运行时才暴露. 比如数组下标越界, 除 0 异常等.
3,Java 的集合类框架介绍一下?
首先接口 Collection 和 Map 是平级的, Map 没有实现 Collection.
Map 的实现类常见有 HashMap,TreeMap,LinkedHashMap 和 HashTable 等. 其中 HashMap 使用散列法实现, 低层是数组, 采用链地址法解决哈希冲突, 每个数组的下标都是一条链表, 当长度超过 8 时, 转换成红黑树. TreeMap 使用红黑树实现, 可以按照键进行排序. LinkedHashMap 的实现综合了 HashMap 和双向链表, 可保证以插入时的顺序 (或访问顺序, LRU 的实现) 进行迭代. HashTable 和 HashMap 比, 前者是线程安全的, 后者不是线程安全的. HashTable 的键或者值不允许 null,HashMap 允许.
Collection 的实现类常见的有 List,Set 和 Queue.List 的实现类有 ArrayList 和 LinkedList 以及 Vector 等, ArrayList 就是一个可扩容的对象数组, LinkedList 是一个双向链表. Vector 是线程安全的(ArrayList 不是线程安全的).Set 的里的元素不可重复, 实现类常见的有 HashSet,TreeSet,LinkedHashSet 等, HashSet 的实现基于 HashMap, 实际上就是 HashMap 中的 Key, 同样 TreeSet 低层由 TreeMap 实现, LinkedHashSet 低层由 LinkedHashMap 实现. Queue 的实现类有 LinkedList, 可以用作栈, 队列和双向队列, 另外还有 PriorityQueue 是基于堆的优先队列.
4,Java 反射是什么? 为什么要用反射, 有什么好处, 哪些地方用到了反射?
反射: 允许任意一个类在运行时获取自身的类信息, 并且可以操作这个类的方法和属性. 这种动态获取类信息和动态调用对象方法的功能称为 Java 的反射机制.
反射的核心是 JVM 在运行时才动态加载类或调用方法 / 访问属性. 它不需要事先 (写代码的时候或编译期) 知道运行对象是谁, 如 Class.ForName()根本就没有指定某个特定的类, 完全由你传入的类全限定名决定, 而通过 new 的方式你是知道运行时对象是哪个类的. 反射避免了将程序 "写死".
反射可以降低程序耦合性, 提高程序的灵活性. new 是造成紧耦合的一大原因. 比如下面的工厂方法中, 根据水果类型决定返回哪一个类.
- public class FruitFactory {
- public Fruit getFruit(String type) {
- Fruit fruit = null;
- if ("Apple".equals(type)) {
- fruit = new Apple();
- } else if ("Banana".equals(type)) {
- fruit = new Banana();
- } else if ("Orange".equals(type)) {
- fruit = new Orange();
- }
- return fruit;
- }
- }
- class Fruit {}
- class Banana extends Fruit {}
- class Orange extends Fruit {}
- class Apple extends Fruit {}
但是我们事先并不知道之后会有哪些类, 比如新增了 Mango, 就需要在 if-else 中新增; 如果以后不需要 Banana 了就需要从 if-else 中删除. 这就是说只要子类变动了, 我们必须在工厂类进行修改, 然后再编译. 如果用反射呢?
- public class FruitFactory {
- public Fruit getFruit(String type) {
- Fruit fruit = null;
- try {
- fruit = (Fruit) Class.forName(type).newInstance();
- } catch (Exception e) {
- e.printStackTrace();
- }
- return fruit;
- }
- }
- class Fruit {}
- class Banana extends Fruit {}
- class Orange extends Fruit {}
- class Apple extends Fruit {}
如果再将子类的全限定名存放在配置文件中.
class-type=com.fruit.Apple
那么不管新增多少子类, 根据不同的场景只需修改文件就好了, 上面的代码无需修改代码, 重新编译, 就能正确运行.
哪些地方用到了反射? 举几个例子
加载数据库驱动时
Spring 的 IOC 容器, 根据 XML 配置文件中的类全限定名动态加载类
工厂方法模式中(如上)
5, 说说你对面向对象, 封装, 继承, 多态的理解?
封装: 隐藏实现细节, 明确标识出允许外部使用的所有成员函数和数据项. 防止代码或数据被破坏.
继承: 子类继承父类, 拥有父类的所有功能, 并且可以在父类基础上进行扩展. 实现了代码重用. 子类和父类是兼容的, 外部调用者无需关注两者的区别.
多态: 一个接口有多个子类或实现类, 在运行期间 (而非编译期间) 才决定所引用的对象的实际类型, 再根据其实际的类型调用其对应的方法, 也就是 "动态绑定".
Java 实现多态有三个必要条件: 继承, 重写, 向上转型.
继承: 子类继承或者实行父类
重写: 在子类里面重写从父类继承下来的方法
向上转型: 父类引用指向子类对象
- public class OOP {
- public static void main(String[] args) {
- /*
- * 1. Cat 继承了 Animal
- * 2. Cat 重写了 Animal 的 eat 方法
- * 3. 父类 Animal 的引用指向了子类 Cat.
- * 在编译期间其静态类型为 Animal; 在运行期间其实际类型为 Cat, 因此 animal.eat()将选择 Cat 的 eat 方法而不是其他子类的 eat 方法
- */
- Animal animal = new Cat();
- printEating(animal);
- }
- public static void printEating(Animal animal) {
- animal.eat();
- }
- }
- abstract class Animal {
- abstract void eat();
- }
- class Cat extends Animal {
- @Override
- void eat() {
- System.out.println("Cat eating...");
- }
- }
- class Dog extends Animal {
- @Override
- void eat() {
- System.out.println("Dog eating...");
- }
- }
6, 实现不可变对象的策略? 比如 JDK 中的 String 类.
不提供 setter 方法(包括修改字段, 字段引用到的的对象等方法)
将所有字段设置为 final,private
将类修饰为 final, 不允许子类继承, 重写方法. 可以将构造函数设为 private, 通过工厂方法创建.
如果类的字段是对可变对象的引用, 不允许修改被引用对象. 1)不提供修改可变对象的方法; 2)不共享对可变对象的引用. 对于外部传入的可变对象, 不保存该引用. 如要保存可以保存其复制后的副本; 对于内部可变对象, 不要返回对象本身, 而是返回其复制后的副本.
7,Java 序列话中如果有些字段不想进行序列化, 怎么办?
对于不想进行序列化的变量, 使用 transient 关键字修饰. 功能是: 阻止实例中那些用此关键字修饰的的变量序列化; 当对象被反序列化时, 被 transient 修饰的变量值不会被持久化和恢复. transient 只能修饰变量, 不能修饰类和方法.
8,== 和 equals 的区别?
== 对于基本类型, 比较值是否相等, 对于对象, 比较的是两个对象的地址是否相同, 即是否是指相同一个对象.
equals 的默认实现实际上使用了 == 来比较两个对象是否相等, 但是像 Integer,String 这些类对 equals 方法进行了重写, 比较的是两个对象的内容是否相等.
对于 Integer, 如果依然坚持使用 == 来比较, 有一些要注意的地方. 对于 [-128,127] 区间里的数, 有一个缓存. 因此
- Integer a = 127;
- Integer b = 127;
- System.out.println(a == b); // true
- Integer a = 128;
- Integer b = 128;
- System.out.println(a == b); // false
- // 不过采用 new 的方式, a 在堆中, 这里打印 false
- Integer a = new Integer(127);
- Integer b = 127;
- System.out.println(a == b);
对于 String, 因为它有一个常量池. 所以
- String a = "gg" + "rr";
- String b = "ggrr";
- System.out.println(a == b); // true
- // 当然牵涉到 new 的话, 该对象就在堆上创建了, 所以这里打印 false
- String a = "gg" + "rr";
- String b = new String("ggrr");
- System.out.println(a == b);
9, 接口和抽象类的区别?
Java 不能多继承, 一个类只能继承一个抽象类; 但是可以实现多个接口.
继承抽象类是一种 IS-A 的关系, 实现接口是一种 LIKE-A 的关系.
继承抽象类可以实现对父类代码的复用, 也可以重写抽象方法实现子类特有的功能. 实现接口可以为类新增额外的功能.
抽象类定义基本的共性内容, 接口是定义额外的功能.
调用者使用动机不同, 实现接口是为了使用他规范的某一个行为; 继承抽象类是为了使用这个类属性和行为.
10, 给你一个 Person 对象 p, 如何将该对象变成 JSON 表示?
本质是考察 Java 反射, 因为要实现一个通用的程序. 实现可能根本不知道该类有哪些字段, 所以不能通过 get 和 set 等方法来获取键 - 值. 使用反射的 getDeclaredFields()可以获得其声明的字段. 如果字段是 private 的, 需要调用该字段的 f.setAccessible(true);, 才能读取和修改该字段.
- import java.lang.reflect.Field;
- import java.util.HashMap;
- public class Object2Json {
- public static class Person {
- private int age;
- private String name;
- public Person(int age, String name) {
- this.age = age;
- this.name = name;
- }
- }
- public static void main(String[] args) throws IllegalAccessException {
- Person p = new Person(18, "Bob");
- Class<?> classPerson = p.getClass();
- Field[] fields = classPerson.getDeclaredFields();
- HashMap<String, String> map = new HashMap<>();
- for (Field f: fields) {
- // 对于 private 字段要先设置 accessible 为 true
- f.setAccessible(true);
- map.put(String.valueOf(f.getName()), String.valueOf(f.get(p)));
- }
- System.out.println(map);
- }
- }
得到了 map, 再弄成 JSON 标准格式就好了.
11,JDBC 中 sql 查询的完整过程? 操作事务呢?
- @Test
- public void fun2() throws SQLException, ClassNotFoundException {
- // 1. 注册驱动
- Class.forName("com.mysql.jdbc.Driver");
- String url = "jdbc:mysql://localhost:3306/xxx?useUnicode=true&characterEncoding=utf-8";
- // 2. 建立连接
- Connection connection = DriverManager.getConnection(url, "root", "admin");
- // 3. 执行 sql 语句使用的 Statement 或者 PreparedStatment
- Statement statement = connection.createStatement();
- String sql = "select * from stu;";
- ResultSet resultSet = statement.executeQuery(sql);
- while (resultSet.next()) {
- // 第一列是 id, 所以从第二行开始
- String name = resultSet.getString(2); // 可以传入列的索引, 1 代表第一行, 索引不是从 0 开始
- int age = resultSet.getInt(3);
- String gender = resultSet.getString(4);
- System.out.println("学生姓名:" + name + "| 年龄:" + age + "| 性别:" + gender);
- }
- // 关闭结果集
- resultSet.close();
- // 关闭 statemenet
- statement.close();
- // 关闭连接
- connection.close();
- }
ResultSet 维持一个指向当前行记录的 cursor(游标)指针
注册驱动
建立连接
准备 sql 语句
执行 sql 语句得到结果集
对结果集进行遍历
关闭结果集(ResultSet)
关闭 statement
关闭连接(connection)
由于 JDBC 默认自动提交事务, 每执行一个 update ,delete 或者 insert 的时候都会自动提交到数据库, 无法回滚事务. 所以若需要实现事务的回滚, 要指定 setAutoCommit(false).
true:sql 命令的提交 (commit) 由驱动程序负责
false:sql 命令的提交由应用程序负责, 程序必须调用 commit 或者 rollback 方法
JDBC 操作事务的格式如下, 在捕获异常中进行事务的回滚.
- try {
- con.setAutoCommit(false);// 开启事务...
- ....
- ...
- con.commit();//try 的最后提交事务
- } catch() {
- con.rollback();// 回滚事务
- }
12, 实现单例, 有哪些要注意的地方?
就普通的实现方法来看.
不允许在其他类中直接 new 出对象, 故构造方法私有化
在本类中创建唯一一个 static 实例对象
定义一个 public static 方法, 返回该实例
- public class SingletonImp {
- // 饿汉模式
- private static SingletonImp singletonImp = new SingletonImp();
- // 私有化 (private) 该类的构造函数
- private SingletonImp() {
- }
- public static SingletonImp getInstance() {
- return singletonImp;
- }
- }
饿汉模式: 线程安全, 不能延迟加载.
- public class SingletonImp4 {
- private static volatile SingletonImp4 singletonImp4;
- private SingletonImp4() {}
- public static SingletonImp4 getInstance() {
- if (singletonImp4 == null) {
- synchronized (SingletonImp4.class) {
- if (singletonImp4 == null) {
- singletonImp4 = new SingletonImp4();
- }
- }
- }
- return singletonImp4;
- }
- }
双重检测锁 + volatile 禁止语义重排. 因为 singletonImp4 = new SingletonImp4(); 不是原子操作.
- public class SingletonImp6 {
- private SingletonImp6() {}
- // 专门用于创建 Singleton 的静态类
- private static class Nested {
- private static SingletonImp6 singletonImp6 = new SingletonImp6();
- }
- public static SingletonImp6 getInstance() {
- return Nested.singletonImp6;
- }
- }
静态内部类, 可以实现延迟加载.
最推荐的是单一元素枚举实现单例.
写法简单
枚举实例的创建默认就是线程安全的
提供了自由的序列化机制. 面对复杂的序列或反射攻击, 也能保证是单例
- public enum Singleton {
- INSTANCE;
- public void anyOtherMethod() {}
- }
数据结构与算法
1, 二叉树的遍历方式? 它们属于深搜还是广搜?
先序遍历. 父结点 -> 左子结点 -> 右子结点
中序遍历. 左子结点 -> 父结点 -> 右子结点
后序遍历. 左子结点 -> 右子结点 -> 父结点
层序遍历. 一层一层自上而下, 从左往右访问.
其中, 先序, 中序, 后序遍历属于深度优先搜索(DFS), 层序遍历属于广度优先搜索(BFS)
2, 什么是平衡二叉树, 它的好处是什么? 被应用在哪些场景中?
平衡二叉树首先是一棵二叉查找树, 其次它需要满足其左右两棵子树的高度之差不超过 1, 且子树也必须是平衡二叉树, 换句话说对于平衡二叉树的每个结点, 要求其左右子树高度之差都不超过 1.
二叉查找树在最坏情况下, 退化成链表, 查找时间从平均 O(lg n)降到 O(n), 平衡二叉树使树的结构更加平衡, 提高了查找的效率; 但是由于插入和删除后需要重新恢复树的平衡, 所以插入和删除会慢一些.
应用场景比如在 HashMap 中用到了红黑树(平衡二叉树的特例), 数据库索引中的 B + 树等.
3, 数组和链表的区别?
数组是一段连续的内存空间, 所以支持随机访问, 可以通过下标以 O(1)的时间进行查找. 链表中的元素在内存中不是连续的, 可以分散在内存中各个地方. 因此它不支持随机访问, 查找效率是 O(n)
数组的插入和删除元素时间是 O(n), 插入和删除后要移动元素; 而链表只需断开结点链接再重新连上, 所以链表的删除和插入时间是 O(1)
数组必须指定初始大小, 达到最大容量如果不扩容就不能再存入新的元素; 而链表没有容量的限制
应用场景: 数组适合读多写少, 事先知道元素大概个数的情况; 链表适合写多读少的情况.
4, 冒泡和快排的区别, 最差和平均的时间复杂度?
冒泡: 相邻元素进行两两比较, 将最大值推动到最右边. 重复以上过程. 时间复杂度平均 O(N^2)最差 O(N^2), 空间复杂度 O(1)
快排: 选择数组中第一个元素作为基准, 从左边向右找到第一个大于等于基准的元素, 从右边向左找到第一个小于等于基准的元素, 交换这两个元素, 最后基准左边的元素都小于等于基准, 基准右边的元素都大于等于基准. 然后固定基准元素, 对其左边和右边采取同样的做法. 典型的分治思想. 时间复杂度平均 O(N lgN)最差 O(N^2), 基于递归的实现由于用到了系统栈, 所以平均情况下空间复杂度为 O(lgN)
冒泡排序是稳定的排序算法, 快速排序不是稳定的排序算法.
排序中所说的稳定是指, 对于两个相同的元素, 在排序后其相对位置没有发生变化.
常见的稳定排序有, 冒泡, 插入, 归并, 基数排序. 选择, 希尔, 快排, 堆排序都不是稳定的.
5, 说说常用的散列方法? 解决哈希冲突的方法有哪些?
最常用的除留余数法(取余), 大小为 M 的数组, key 的哈希值为 k, 那么 k % M 的值一定是落在 0-M-1 之间的.
直接定址法. 用一个函数对 key 作映射得到哈希值. 如线性函数:
hash(key) = a * key + b
其他(略)
解决哈希冲突的方法:
开放定址法: 采用 M 大小的数组存放 N 个键值对, 其中 M> N. 开放定址中最简单的是线性探测法, 当发生碰撞时, 直接检查散列表中的下一个位置. 如果到了数组末尾, 折回到索引 0 处继续查找.
链地址法: 采用链表数组实现, 当发生哈希冲突时, 将冲突键值以头插或者尾插的方式插入数组下标所在的链表, HashMap 中正是使用了这种方法.
再哈希法: 当发生哈希冲突时, 换一个散列函数重新计算哈希值.
公共溢出区法: 建立一个基本表和溢出表, 所有冲突的键值都存放到溢出表中. 在查找时, 先在基本表中查, 相等, 查找成功, 如不相等则去溢出表中进行顺序查找.
6, 堆排序的过程说一下?
堆排序使用了最大堆 / 最小堆, 拿数组升序排序来说, 需要建立一个最大堆, 基于数组实现的二叉堆可以看作一棵完全二叉树, 其满足堆中每个父结点它左右两个结点值都大, 且堆顶的元素最大.
将堆顶元素和数组最后一个元素交换, 最大元素被交换数组最后一个位置, 同时从堆中删除原来处于堆顶的最大元素
被交换到堆顶的元素一般会打破堆结构的定义, 因此需要进行堆的调整(下沉). 将堆顶的元素和其左右两个结点比较, 将三者中的最大的交换到堆顶, 然后继续跟踪此结点, 循环上述过程, 直到他比左右两个结点都大时停止调整, 此时堆调整完毕, 再次满足堆结构的定义
重复以上两个过程. 直到堆中只剩一个元素, 此时排序完成
每次调整堆的平均时间为 O(lg N), 因此对大小为 N 的数组排序, 时间复杂度最差和平均都 O(N lg N).
7, 堆排序和快排应用场景的? 时间复杂度和空间复杂度各是多少?
快排序在平均情况下, 比绝大多数排序算法都快些. 很多编程语言的 sort 默认使用快排, 像 Java 的 Array.sort()就采用了双轴快速排序 . 堆排序使用堆实现, 空间复杂度只有 O(1). 堆排序使用堆的结构, 能以 O(1)的时间获得最大 / 最小值, 在处理 TOP K 问题时很方便, 另外堆还可以实现优先队列.
时间复杂度:
快排, 平均 O(N lg N) , 最差 O(N^2), 这种情况发生在数组本身就有序, 这样每次切分元素都是数组中的最小值, 切分得就极为不平衡.
堆排序, 平均和最差都是 O(N lgN). 因为每次调整堆结构都是 O(lg N), 因此对大小为 N 的数组排序, 时间复杂度最差和平均都 O(N lg N).
空间复杂度:
快排, 一般基于递归实现, 需要使用系统栈 O(lg N)
堆排序, 额外空间复杂度 O(1)
放一张神图
8, 双向链表, 给你 Node a, 在其后插入 Node c?
- c.next = a.next;
- a.next = c;
- c.prev = a;
- // 如果 a 不是最后一个结点, 就有下面一句
- c.next.prev = c;
9, 写并查集?
- public class UnionFind {
- // id 相同的分量是连通的
- private int[] id;
- // 连通分量的个数
- private int count;
- public UnionFind(int n) {
- count = n;
- id = new int[n];
- for (int i = 0; i <n; i++) {
- id[i] = i;
- }
- }
- // 所属连通分量的 id
- public int find(int p) {
- return id[p];
- }
- // 将和 p 同一个连通分量的结点全部归到和 q 一个分量中, 即将 p 所在连通分量与 q 所在连通分量合并.
- // 反过来也可以
- // if (id[i] == qID) {
- // id[i] = pID;
- // }
- public void union(int p, int q) {
- int pId = find(p);
- int qId = find(q);
- if (pId == qId) return;
- for (int i = 0; i < id.length; i++) {
- if (id[i] == pId) {
- id[i] = qId;
- }
- }
- // 合并后, 连通分量减少 1
- count--;
- }
- public boolean connected(int p, int q) {
- return find(p) == find(q);
- }
- }
还可以有优化的写法, 一个连通分量看成是一棵树. 同一个连通分量其树的根结点相同.
- public class UnionFind {
- private int[] parentTo;
- private int count;
- public UnionFind(int n) {
- count = n;
- parentTo = new int[n];
- for (int i = 0; i < n; i++) {
- parentTo[i] = i;
- }
- }
- public int find(int p) {
- // 向上一直到根结点
- // p = parentTo[p]说明到达树的根结点, 返回根结点
- while (p != parentTo[p]) {
- p = parentTo[p];
- }
- return p;
- }
- // 这行的意思就是 q 所在连通分量和 q 所在连通分量合并
- // 从树的角度来看, p 树的根结点成为了 q 树根结点的孩子结点
- // 反过来也可以, parentTo[qRoot] = pRoot;
- public void union(int p, int q) {
- int pRoot = find(p);
- int qRoot = find(q);
- if (pRoot == qRoot) return;
- parentTo[pRoot] = qRoot;
- count--;
- }
- public boolean connected(int p, int q) {
- return find(p) == find(q);
- }
- }
10,HashMap 存了若干 (name, age) 这样的键值对, 现在想按照年龄排序, 打印出姓名?
因为人类的年龄在一个固定范围内, 假设 0~100 吧. 可以设置 101 个桶, 每个桶中放的是该年龄的所有用户名.
- public static void printNameOrderByAge(Map<String, Integer> map) {
- LinkedList<String>[] bucket = new LinkedList[101];
- for (String name : map.keySet()) {
- int age = map.get(name);
- if (bucket[age] == null) {
- bucket[age] = new LinkedList<>();
- }
- bucket[age].add(name);
- }
- for (int i = 0;i <bucket.length;i++) {
- if (bucket[i] != null) {
- System.out.print(i + ":");
- System.out.println(bucket[i]);
- }
- }
- }
- public static void main(String[] args) throws InterruptedException {
- Map<String, Integer> map = new HashMap<>();
- map.put("Alice", 20);
- map.put("Bob", 20);
- map.put("Tim", 19);
- map.put("Joker", 19);
- map.put("Carlos", 18);
- map.put("XiaoMing", 22);
- printNameOrderByAge(map);
- }
打印如下内容
- 18 : [Carlos]
- 19 : [Joker, Tim]
- 20 : [Bob, Alice]
- 22 : [XiaoMing]
计算机网络
1,HTTP 有哪些请求方法? 它们的作用或者说应用场景?
GET: 请求指定的页面信息, 并返回实体主体.
HEAD: 和 GET 类似, 只不过不返回报文主体, 只返回响应首部. 可用于确认 URI 的有效性及资源更新的日期时间;
POST: 向指定资源提交数据进行处理请求(例如提交表单或者上传文件). 数据被包含在请求体中. POST 请求可能会导致新的资源的建立和 / 或已有资源的修改.
PUT: 用来传输文件, 要求请求报文的主体中包含文件内容, 然后保存到请求 URI 指定的位置.
DELETE: 和 PUT 相反, 按请求 URI 删除指定的资源.
OPTIONS: 用来查询针对请求 URI 指定的资源支持的方法. 如果请求成功, 会有一个 Allow 的头包含类似 "GET,POST" 这样的信息
TRACE: 让服务端将之前的请求通信返回给客户端的方法(因此客户端可以得知请求是怎么一步步到服务端的). 主要用于测试或诊断.
CONNECT: 使用 SSL(Secure Sockets Layer, 安全套接层)和 TLS(Transport Layer Security, 传输层安全)协议把通信内容加密后经网络隧道传输.
2,GET 和 POST 的对比, 或者说区别?
GET 用于获取数据, POST 用于提交数据;
GET 的参数长度有限制(不同的浏览器和服务器限制不同),POST 没有限制
GET 把参数包含在 URL 中, POST 通过封装参数到请求体中发送;
GET 请求只能进行 url 编码, 而 POST 支持多种编码方式.
GET 可以发送的参数只能是 ASCII 类型, POST 没有限制, 甚至可以传输二进制.
GET 比 POST 更不安全, 因为参数直接暴露在 URL 上, 所以不能用来传递敏感信息;
GET 刷新无害, 而 POST 会再次提交数据
还有 GET 请求会被保存浏览器历史记录, 可以被收藏为书签, 而 POST 请求不能等等
GET 和 POST 本质都是 TCP 连接. 不过 GET 产生一个 TCP 数据包; POST 产生两个 TCP 数据包.
对于 GET 方式的请求, 浏览器会把 http header 和 data 一并发送出去, 服务器响应 200 OK(返回数据);
而对于 POST, 浏览器先发送 header, 服务器响应 100 continue, 浏览器再发送 data, 服务器响应 200 OK(返回数据).
3,TCP 三次握手? 四次挥手?
三次握手
请求先由客户端发起. 客户端发送 SYN = 1 和客户端序号 c 给服务端, 同时进入 SYN-SENT 状态
服务端收到 SYN 后需要做出确认, 于是发送 ACK = 1, 同时自己也发送 SYN = 1, 服务端序号 s, 还有确认号 c + 1, 表示想收到的下一个序号. 此时服务端进入 SYN-RCVD 状态
客户端收到服务端的 SYN 和 ACK, 做出确认, 发送 ACK = 1, 以及序号 c +1, 同时发送确认号 s + 1, 表示客户端想收到下一个序号. 此时客户端和服务端进入 ESTABLISHED 状态, 连接已建立!
四次挥手
关闭连接也是先有客户端发起. 客户端发送 FIN = 1 和序号 c 向服务端请求断开连接. 此时客户端进入 FIN-WAIT-1 状态
服务端收到 FIN 后做出确认, 发送 ACK = 1 和服务端序号, 还有确认号 c + 1 表示想要收到的下一个序号. 服务端此时还可以向客户端发送数据. 此时服务端进入 CLOSE-WAIT 状态, 客户端进入 FIN-WAIT-2 状态
服务端没有数据发送时, 它向客户端发送 FIN= 1,ACK = 1 请求断开连接, 同时发送服务端序号 s 以及确认号 c + 1. 此时服务端进入 LAST-ACK 状态
客户端收到后进行确认, 发送 ACK = 1, 以及需要 c + 1 和确认号 s + 1. 此时客户端进入 TIME-WAIT 状态. 客户端需要等待 2MSL, 确保服务端收到了 ACK, 若这期间客户端没有收到服务端的消息, 便可认为服务端收到了确认, 此时可以断开连接. 客户端和服务端进入 CLOSED 状态.
4,TCP 为什么需要三次握手? 两次不行吗?
两次握手的话, 只要服务端发出确认就建立连接了. 有一种情况是客户端发出了两次连接请求, 但由于某种原因, 使得第一次请求被滞留了. 第二次请求先到达后建立连接成功, 此后第一次请求终于到达, 这是一个失效的请求了, 服务端以为这是一个新的请求于是同意建立连接, 但是此时客户端不搭理服务端, 服务端一直处于等待状态, 这样就浪费了资源. 假设采用三次握手, 由于服务端还需要等待客户端的确认, 若客户端没有确认, 服务端就可以认为客户端没有想要建立连接的意思, 于是这次连接不会生效.
5, 四次握手, 为什么客户端发送确认后还需要等待 2MSL?
因为第四次握手客户端发送 ACK 确认后, 有可能丢包了, 导致服务端没有收到, 服务端就会再次发送 FIN = 1, 如果客户端不等待立即 CLOSED, 客户端就不能对服务端的 FIN = 1 进行确认. 等待的目的就是为了能在服务端再次发送 FIN = 1 时候能进行确认. 如果在 2MSL 内客户端都没有收到服务端的任何消息, 便认为服务端收到了确认. 此时可以结束 TCP 连接.
6,cookie 和 session 区别和联系?
Session 是在服务端保存的一个数据结构, 用来跟踪用户的状态, 这个数据可以保存在集群, 数据库, 文件中;
Cookie 是客户端保存用户信息的一种机制, 用来记录用户的一些信息, 也是实现 Session 的一种方式.
session 的运行依赖 session id, 而 session id 是存在 cookie 中的, 也就是说, 如果浏览器禁用了 cookie , 同时 session 也会失效(但是可以通过 url 重写, 即在 url 中传递 session_id)
7, 为何使用 session?session 的原理?
比如网上购物, 每个用户有自己的购物车, 当点击下单时, 由于 HTTP 协议无状态, 并不知道是哪个用户操作的, 所以服务端要为特定的用户创建特定的 Session, 用于标识这个用户, 并且跟踪用户.
Session 原理: 浏览器第一次访问服务器时, 服务器会响应一个 cookie 给浏览器. 这个 cookie 记录的就是 sessionId, 之后每次访问携带着这个 sessionId, 服务器里查询该 sessionId, 便可以识别并跟踪特定的用户了.
Cookie 原理: 第一次访问服务器, 服务器响应时, 要求浏览器记住一个信息. 之后浏览器每次访问服务器时候, 携带第一次记住的信息访问. 相当于服务器识别客户端的一个通行证. Cookie 不可跨域, 浏览览器判断一个网站是否能操作另一个网站 Cookie 的依据是域名. Google 与 Baidu 的域名不一样, 因此 Google 不能操作 Baidu 的 Cookie, 换句话说 Google 只能操作 Google 的 Cookie.
8, 网络的 7 层模型了解吗?
即 OSI 参考模型.
应用层. 针对特定应用的协议, 为应用程序提供服务. 如电子邮件, 远程登录, 文件传输等协议.
表示层. 主要负责数据格式的转换, 把不同表现形式的信息转换成适合网络传输的格式.
会话层. 通信管理, 负责建立和断开通信连接. 即何时建立连接, 何时断开连接以及保持多久的连接.
传输层. 在两个通信结点之间负责数据的传输, 起着可靠传输的作用.
网络层. 路由选择. 在多个网络之间转发数据包, 负责将数据包传送到目标地址.
数据链路层. 负责物理层面上互联设备之间的通信传输. 例如与一个以太网相连的两个节点之间的通信. 是数据帧与 1,0 比特流之间的转换.
物理层. 主要是 1,0 比特流与电子信号的高低电平之间的转换.
还有一种 TCP/IP 五层模型, 就是把应用层, 表示层, 会话层统一归到应用层. 借用一张图.
9, 有了传输层为什么还需要网络层? 或者说网络层和传输层是如何协作的?
网络层是针对主机与主机之间的服务. 而传输层针对的是不同主机进程之间的通信. 传输层协议将应用进程的消息传送到网络层, 但是它并不涉及消息是怎么在网络层之间传送(这部分是由网络层的路由选择完成的). 网络层真正负责将数据包从源 IP 地址转发到目标 IP 地址, 而传输层负责将数据包再递交给主机中对应端口的进程.
打个比方. 房子 A 中的人要向房子 B 中的人写信. 房子中都有专门负责将主人写好的信投递到邮箱, 以及从邮箱接收信件后交到主人手中的管家. 那么:
房子 = 主机
信的内容 = 应用程序消息
信封 = 数据包, 带有源端口, 目的端口, 源 IP 地址, 目的 IP 地址.
邮递员 = 网络层协议, 知道信从哪个房子开始发的, 以及最后要送到哪个具体的房子.
管家 = 传输层协议, 负责将信投入到信箱中, 以及从信箱中接收信件. 知道这封信是谁写的以及要送到谁手上(具体端口号)
以上只是个人理解, 如有误请联系更正.
10,TCP 和 UDP 的区别?
TCP 面向连接, 传输数据之前要需要建立会话. UDP 是无连接的.
TCP 提供可靠传输, 保证数据不丢包, 不重复且按顺序到达; UDP 只尽努力交付, 不保证可靠交付
TCP 提供了拥塞控制; UDP 不提供
TCP 是面向字节流的; UDP 面向报文.
TCP 只支持点到点通信; UDP 支持一对一, 一对多, 多对多的交互通信.
TCP 首部开销大 20 字节, UDP 首部开销小 8 字节.
11, 传输层的可靠传输指的是什么? 是如何实现的?
可靠传输是指
传输的信道不产生差错
保证传输数据的正确性, 无差错, 不丢失, 不重复且按顺序到达.
TCP 如何实现可靠传输:
应用数据被分割成 TCP 认为最适合发送的块进行传输
超时重传, TCP 发出一个分组后, 它启动一个定时器, 等接收方确认收到这个分组. 如果发送方不能及时收到一个确认, 将重传给接收方.
序号, 用于检测丢失的分组和冗余的分组.
确认, 告知对方已经正确收到的分组以及期望的下一个分组
校验和, 校验数据在传输过程中是否发生改变, 如校验有错则丢弃分组;
流量控制, 使用滑动窗口, 发送窗口的大小由接收窗口和拥塞窗口的的大小决定(取两者中小的那个), 当接收方来不及处理发送方的数据, 能提示发送方降低发送的速率, 防止包丢失.
拥塞控制: 当网络拥塞时, 减少数据的发送.
12, 主机 A 向主机 B 发送数据, 在这个过程中, 传输层和网络层做了什么?
当 TCP 连接建立之后, 应用程序就可使用该连接进行数据收发. 应用程序将数据提交给 TCP,TCP 将数据放入自己的缓存, 数据会被当做字节流并进行分段, 然后加上 TCP 头部并提交给网络层. 再加上 IP 头后被网络层提交给到目的主机, 目的主机的 IP 层会将分组提交给 TCP,TCP 根据报文段的头部信息找到相应的 socket, 并将报文段提交给该 socket,socket 是和应用关联的, 于是数据就提交给了应用.
对于 UDP 会简单些, UDP 面向报文段. 传输层加上 UDP 头部递交给网络层, 再加上 IP 头部经路由转发到目的主机, 目的主机将分组提交给 UDP,UDP 根据头部信息找到相应的 socket, 并将报文段提交给该 socket,socket 是和应用关联的, 于是数据就提交给了应用.
13,TCP 序号的作用? 怎么保证可靠传输的?
序号和确认号是实现可靠传输的关键.
序号: 当前数据包的首个字节的顺序号.
确认号: 表示下一个想要接收的字节序号, 同时确认号表示对发送方的一个确认回应, 表示已经正确收到确认号之前的字节了.
通信双方通过序号和确认号, 来判断数据是否丢失, 是否按顺序到达, 是否冗余等, 以此决定要不要进行重传丢失的分组或丢弃冗余的分组. 换句话说, 因为有了序号, 确认号和重传机制, 保证了数据不丢失, 不重复, 有序到达.
14, 浏览器发起 HTTP 请求后发生了什么? 越详细越好.
当在浏览器输入网址 www.baidu.com 并敲下回车后:
DNS 域名解析, 将域名 www.baidu.com 解析成 IP 地址
发起 TCP 三次握手, 建立 TCP 连接. 浏览器以一个随机端口 (1024~65535) 向服务器的 80 端口发起 TCP 连接.
TCP 连接建立后, 发起 HTTP 请求.
服务端响应 HTTP 请求, 将 html 代码返回给浏览器.
浏览器解析 html 代码, 请求 html 中的资源
浏览器对页面进行渲染呈现给用户
15,DNS 域名解析的请求过程?
先在浏览器自身的 DNS 缓存中搜索
如上述步骤未找到, 浏览器搜索操作系统本身的 DNS 缓存
如果在系统 DNS 缓存中未找到, 则尝试读取 hosts 文件, 寻找有没有该域名对应的 IP
如果 hosts 文件中没找到, 浏览器会向本地配置的首选 DNS 服务器发起域名解析请求 . 运营商的 DNS 服务器首先查找自身的缓存, 若找到对应的条目且没有过期, 则解析成功. 如果没有找到, 运营商的 DNS 代我们的浏览器, 以根域名 ->顶级域名 ->二级域名 ->三级域名这样的顺序发起迭代 DNS 解析请求.
16,HTTP 是基于 TCP 还是 UDP 的?
HTTP 协议是基于 TCP 协议的, 客户端向服务端发送一个 HTTP 请求时, 需要先与服务端建立 TCP 连接(三次握手), 握手成功以后才能进行数据交互.
17,HTTP 请求和响应的报文结构(格式)?
HTTP 请求的报文格式:
请求行: 包括请求方法, URL,HTTP 协议版本号
请求头: 若干键值对组成
请求空行: 告诉服务器请求头的键值对已经发送完毕
请求主体
HTTP 响应的报文格式:
响应行: HTTP 协议版本号, 状态码, 状态码描述
响应头: 若干键值对表示
响应空行: 标识响应头的结束
响应主体
18,HTTP 常见的状态码?
1XX: 信息性状态码, 表示接收的请求正在处理
2XX: 成功状态码, 表示请求正常处理完毕
3XX: 重定向状态码, 表示需要进行附加操作以完成请求
4XX: 客户端错误状态码, 表示服务器无法处理请求
5XX: 服务端错误状态码, 表示服务器处理请求出错
常见的状态码有:
200 OK, 请求被正常处理
301 Move Permanently, 永久性重定向
302 Found, 临时性重定向
400 Bad Request, 请求报文中存在语法错误
403 Forbidden, 对请求资源的访问被服务器拒绝
404 Not Found, 在服务器上不能找到请求的资源
500 Internal Server Error, 服务器内部错误
并发 / 多线程
1, 两个线程对可以同一个 ArrayList 进行 add 操作吗? 会出现什么结果?
- import java.util.ArrayList;
- import java.util.List;
- public class A {
- static List<Integer> list = new ArrayList<>();
- static class BB implements Runnable {
- @Override
- public void run() {
- for (int j = 0; j <100; j++) {
- list.add(j);
- }
- }
- }
- public static void main(String[] args) throws InterruptedException {
- BB b = new BB();
- Thread t1 = new Thread(b);
- Thread t2 = new Thread(b);
- t1.start();
- t2.start();
- t1.join();
- t2.join();
- System.out.println(list.size());
- }
- }
比如上面的例子, 打印的结果不一定是 200.
因为 ArrayList 不是线程安全的, 问题出在 add 方法
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
上面的程序, 可能有三种情况发生:
数组下标越界. 首先要检查容量, 必要时进行扩容. 每当在数组边界处, 如果 A 线程和 B 线程同时进入并检查容量, 也就是它们都执行完 ensureCapacityInternal 方法, 因为还有一个空间, 所以不进行扩容, 此时如果 A 暂停下来, B 成功自增; 然后接着 A 从
elementData[size++] = e
开始执行, 由于 A 之前已经检查过没有扩容, 而 B 成功自增使得现在没有空余空间了, 此时 A 就会发生数组下标越界.
小于 200.size++ 可以看成是 size = size + 1, 这一行代码包括三个步骤, 先读取 size, 然后将 size 加 1, 最后将这个新值写回到 size. 此时若 A 和 B 线程同时读取到 size 假设为 10,B 先自增成功 size 变 11, 然后回来 A 因为它读到的 size 也是 10, 所以自增后写入 size 被更新成 11, 也就是说两次自增, 实际上 size 只增大了 1. 因此最后的 size 会小于 200.
200. 运气很好, 没有发生以上的情况.
2,volatile 和 synchronized 讲一下?
synchronized 保证了当有多个线程同时操作共享数据时, 任何时刻只有一个线程能进入临界区操作共享数据, 其他线程必须等待. 因此它可以保证操作的原子性. synchronized 通过同步锁保证线程安全, 进入临界区前必须获得对象的锁, 其他没有获得锁的线程不可进入. 当临界区中的线程操作完毕后, 它会释放锁, 此时其他线程可以竞争锁, 得到锁的那个线程便可以进入临界区.
synchronized 还可以保证可见性. 因为对一个变量的 unlock 操作之前, 必须先把次变量同步回主内存中. 它还可以保证有序性, 因为一个变量在任何时刻只能有一个线程对其进行 lock 操作(也就是任何时刻只有一个线程可以获得该锁对象), 这决定了持有同一把锁的两个同步块只能串行进入.
volatile 是一个关键字, 用于修饰变量. 被其修饰的变量具有可见性和有序性.
可见性, 当一条线程修改了这个变量的值, 新值能被其他线程立刻观察到. 具体来说, volatile 的作用是: 在本 CPU 对变量的修改直接写入主内存中, 同时这个写操作使得其他 CPU 中对应变量的缓存行无效, 这样其他线程在读取这个变量时候必须从主内存中读取, 所以读取到的是最新的, 这就是上面说得能被立即 "看到".
有序性, volatile 可以禁止指令重排. volatile 在其汇编代码中有一个 lock 操作, 这个操作相当于一个内存屏障, 指令重排不能越过内存屏障. 具体来说在执行到 volatile 变量时, 内存屏障之前的语句一定被执行过了且结果对后面是已知的, 而内存屏障后面的语句一定还没执行到; 在 volatile 变量之前的语句不能被重排后其之后, 相反其后的语句也不能被重排到之前.
3,synchronized 和重入锁的区别?
synchronized 是 JVM 的内置锁, 而重入锁是 Java 代码实现的. 重入锁是 synchronized 的扩展, 可以完全代替后者. 重入锁可以重入, 允许同一个线程连续多次获得同一把锁. 其次, 重入锁独有的功能有:
可以相应中断, synchronized 要么获得锁执行, 要么保持等待. 而重入锁可以响应中断, 使得线程在迟迟得不到锁的情况下, 可以不再等待. 主要由
lockInterruptibly()
实现, 这是一个可以对中断进行响应的锁申请动作, 锁中断可以避免死锁.
锁的申请可以有等待时限, 用 tryLock()可以实现限时等待, 如果超时还未获得锁会返回 false, 也防止了线程迟迟得不到锁时一直等待, 可避免死锁.
公平锁, 即锁的获得按照线程先来后到的顺序依次获得, 不会产生饥饿现象. synchronized 的锁默认是不公平的, 重入锁可通过传入构造方法的参数实现公平锁.
重入锁可以绑定多个 Condition 条件, 这些 condition 通过调用 await/singal 实现线程间通信.
4,synchronized 作了哪些优化?
synchronized 对内置锁引入了偏向锁, 轻量级锁, 自旋锁, 锁消除等优化. 使得性能和重入锁差不多了.
偏向锁: 偏向锁会偏向第一个获得它的线程, 如果在接下来的执行过程中, 该锁没有被其他线程获取, 则持有偏向锁的线程永远也不需要再进行同步. 偏向锁是在无竞争的情况下把整个同步都消除掉, CAS 操作也没有了. 适合于同一个线程请求同一个锁, 不适用于不同线程请求同一个锁, 此时会造成偏向锁失效.
轻量级锁: 如果偏向锁失效, 虚拟机不会立即挂起线程, 会使用一种称为轻量级锁的优化手段, 轻量级锁的加锁和解锁都是通过 CAS 操作完成的. 如果线程获得轻量级锁成功, 则可以顺利进入临界区. 如果轻量级锁加锁失败, 表示其他线程抢先得到了锁, 轻量级锁将膨胀为重量级锁.
自旋锁: 锁膨胀后, 虚拟机为了避免线程真实地在操作系统层面挂起, 虚拟机还会做最后的努力 -- 自旋锁. 如果共享数据的锁定状态只有很短的一段时间, 为了这段时间去挂起和恢复线程 (都需要转入内核态) 并不值得, 所以此时让后面请求锁的那个线程稍微等待以下, 但不放弃处理器的执行时间. 这里的等待其实就是执行了一个忙循环, 这就是所谓的自旋. 虚拟机会让当前线程做几个循环, 若干次循环后如果得到了锁, 就顺利进入临界区; 如果还是没得到, 这才将线程在操作系统层面挂起.
锁消除: 虚拟机即时编译时, 对一些代码上要求同步, 但被检测到不可能存在共享数据竞争的锁进行消除. 锁消除的依据来源于 "逃逸分析" 技术. 堆上的所有数据都不会逃逸出去被其他线程访问到, 就可以把它们当栈上的数据对待, 认为它们是线程私有的, 同步加锁就是没有必要的.
5,Java 中线程的创建方式有哪些?
继承 Thread 并重写 run 方法
实现 Runnable 并重写 run 方法, 然后作为参数传入 Thread
实现 Callable, 并重写 call(),call 方法有返回值. 使用 FutureTask 包装 Callable 实现类, 其中 FutureTask 实现了 Runnable 和 Future 接口, 最后将 FutureTask 作为参数传入 Thread 中
由线程池创建并管理线程.
6,Java 中线程池怎么实现的, 核心参数讲一讲?
Executors 是线程池的工厂类, 通过调用它的静态方法如
- Executors.newCachedThreadPool();
- Executors.newFixedThreadPool(n);
可返回一个线程池. 这些静态方法统一返回一个 ThreadPoolExecutor, 只是参数不同而已.
- public ThreadPoolExecutor(int corePoolSize,
- int maximumPoolSize,
- long keepAliveTime,
- TimeUnit unit,
- BlockingQueue<Runnable> workQueue,
- ThreadFactory threadFactory,
- RejectedExecutionHandler handler) {}
包括以上几个参数, 其中:
corePoolSize: 指定了线程池中线程的数量;
maximumPoolSize: 线程池中的最大线程数量;
keepAliveTime: 当线程池中线程数量超过 corePoolSize 时, 多余的空闲线程的存活时间;
unit: 上一个参数 keepAliveTime 的单位
任务队列, 被提交但还未被执行额任务
threadFactory: 线程工厂, 用于创建线程, 一般用默认工厂即可.
handler: 拒绝策略. 当任务太多来不及处理的时候, 采用什么方法拒绝任务.
最重要的是任务队列和拒绝策略.
任务队列主要有 ArrayBlockingQueue 有界队列, LinkedBlockingQueue 无界队列, SynchronousQueue 直接提交队列.
使用 ArrayBlockingQueue, 当线程池中实际线程数小于核心线程数时, 直接创建线程执行任务; 当大于核心线程数而小于最大线程数时, 提交到任务队列中; 因为这个队列是有界的, 当队列满时, 在不大于最大线程的前提下, 创建线程执行任务; 若大于最大线程数, 执行拒绝策略.
使用 LinkedBlockingQueue 时, 当线程池中实际线程数小于核心线程数时, 直接创建线程执行任务; 当大于核心线程数而小于最大线程数时, 提交到任务队列中; 因为这个队列是有无界的, 所以之后提交的任务都会进入任务队列中. newFixedThreadPool 就采用了无界队列, 同时指定核心线程和最大线程数一样.
使用 SynchronousQueue 时, 该队列没有容量, 对提交任务的不做保存, 直接增加新线程来执行任务. newCachedThreadPool 使用的是直接提交队列, 核心线程数是 0, 最大线程数是整型的最大值, keepAliveTime 是 60s, 因此当新任务提交时, 若没有空闲线程都是新增线程来执行任务, 不过由于核心线程数是 0, 当 60s 就会回收空闲线程.
当线程池中的线程达到最大线程数时, 就要开始执行拒绝策略了. 有如下几种
直接抛出异常
在调用者的线程中, 运行当前任务
丢弃最老的一个请求, 也就是将队列头的任务 poll 出去
默默丢弃无法处理的任务, 不做任何处理
7,BIO,NIO,AIO 的区别?
首先要搞明白在 I/O 中的同步, 异步, 阻塞, 非阻塞是什么意思.
同步 I/O. 由用户进程自己处理 I/O 的读写, 处理过程中不能做其他事. 需要主动去询问 I/O 状态.
异步 I/O. 由系统内核完成 I/O 操作, 完成后系统会通知用户进程.
阻塞. I/O 请求操作需要的条件不满足, 请求操作一直等待, 直到条件满足.
非阻塞. I/O 请求操作需要的条件不满足, 会立即返回一个标志, 而不会一直等待.
现在来看 BIO,NIO,AIO 的区别.
BIO: 同步并阻塞. 用户进程在发起一个 I/O 请求后, 必须等待 I/O 准备就绪, I/O 操作也由自己来处理, 在 IO 操作未完成之前, 用户进程必须等待.
NIO: 同步非阻塞. 用户进程发起一个 I/O 请求后可立即返回去做其他任务, 当 I/O 准备就绪时它会收到通知. 接着由这个线程自行进行 I/O 操作, I/O 操作本身还是同步的.
AIO: 异步非阻塞. 用户进程发起一个 I/O 操作以后可立即返回去做其他任务, 真正的 I/O 操作由内核完成后通知用户进程.
NIO 和 AIO 的不同: NIO 是操作系统通知用户进程 I/O 已经准备就绪, 由用户进程自行完成 I/O 操作; AIO 是操作系统完成 I/O 后通知用户进程.
BIO 是为每一个客户端连接开启一个线程, 简单说就是一个连接一个线程.
NIO 主要组件有 Seletor,Channel,Buffer, 数据需要通过 BUffer 包装后才能使用 Channel 进行读取和写入. 一个 Selector 可以由一个线程管理, 每一个 Channel 可看作一个客户端连接. 一个 Selector 可以监听多个 Channel, 即使用一个或极少数的线程来管理大量的客户端连接. 当与客户端连接的数据没有准备好时, Selector 处于等待状态, 一旦某个 Channel 的准备好了数据, Selector 就能立即得到通知.
8, 两个线程交替打印奇数和偶数?
先使用 synchronized 实现. PrintOdd 用于打印奇数; PrintEven 用于打印偶数. 核心就是判断当前 count 如果是奇数, 就让 PrintEven 阻塞, PrintOdd 打印后唤醒在 lock 对象上等待的 PrintEven 并且释放锁. 此时 PrintEven 获得锁打印偶数再唤醒 PrintOdd, 两个线程如此交替唤醒对方就实现了交替打印奇偶数.
- public class PrintOddEven {
- private static final Object lock = new Object();
- private static int count = 1;
- static class PrintOdd implements Runnable {
- @Override
- public void run() {
- for (int i = 0; i <10; i++) {
- synchronized (lock) {
- try {
- while ((count & 1) != 1) {
- lock.wait();
- }
- System.out.println(Thread.currentThread().getName() + " " +count);
- count++;
- lock.notify();
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- }
- }
- static class PrintEven implements Runnable {
- @Override
- public void run() {
- for (int i = 0; i < 10; i++) {
- synchronized (lock) {
- try {
- while ((count & 1) != 0) {
- lock.wait();
- }
- System.out.println(Thread.currentThread().getName() + " " +count);
- count++;
- lock.notify();
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- }
- }
- public static void main(String[] args) {
- new Thread(new PrintOdd()).start();
- new Thread(new PrintEven()).start();
- }
- }
如果要实现 3 个线程交替打印 ABC 呢? 这次打算使用重入锁, 和上面没差多少, 但是由于现在有三个线程了, 在打印完后需要唤醒其他线程, 注意不可使用 sigal(), 因为唤醒的线程是随机的, 不能保证打印顺序不说, 还会造成死循环. 一定要使用 sigalAll()唤醒所有线程.
- import java.util.concurrent.locks.Condition;
- import java.util.concurrent.locks.ReentrantLock;
- public class ThreeThreadPrintABC {
- private static ReentrantLock lock = new ReentrantLock();
- private static Condition wait = lock.newCondition();
- // 用来控制该打印的线程
- private static int count = 0;
- public static void main(String[] args) {
- Thread printA = new Thread(new PrintA());
- Thread printB = new Thread(new PrintB());
- Thread printC = new Thread(new PrintC());
- printA.start();
- printB.start();
- printC.start();
- }
- static class PrintA implements Runnable {
- @Override
- public void run() {
- for (int i = 0; i < 10; i++) {
- lock.lock();
- try {
- while ((count % 3) != 0) {
- wait.await();
- }
- System.out.println(Thread.currentThread().getName() + "A");
- count++;
- wait.signalAll();
- } catch (InterruptedException e) {
- e.printStackTrace();
- } finally {
- lock.unlock();
- }
- }
- }
- }
- static class PrintB implements Runnable {
- @Override
- public void run() {
- for (int i = 0; i < 10; i++) {
- lock.lock();
- try {
- while ((count % 3) != 1) {
- wait.await();
- }
- System.out.println(Thread.currentThread().getName() + "B");
- count++;
- wait.signalAll();
- } catch (InterruptedException e) {
- e.printStackTrace();
- } finally {
- lock.unlock();
- }
- }
- }
- }
- static class PrintC implements Runnable {
- @Override
- public void run() {
- for (int i = 0; i < 10; i++) {
- lock.lock();
- try {
- while ((count % 3) != 2) {
- wait.await();
- }
- System.out.println(Thread.currentThread().getName() + "C");
- count++;
- wait.signalAll();
- } catch (InterruptedException e) {
- e.printStackTrace();
- } finally {
- lock.unlock();
- }
- }
- }
- }
- }
如果觉得不好理解, 重入锁是可以绑定多个条件的. 创建 3 个 Condition 分别让三个打印线程在上面等待. A 打印完了, 唤醒等待在 waitB 对象上的 PrintB;B 打印完了唤醒在 waitC 对象上的 PrintC;C 打印完了, 唤醒在 waitA 对象上等待的 PrintA, 如此循环地唤醒对方即可.
- import java.util.concurrent.locks.Condition;
- import java.util.concurrent.locks.ReentrantLock;
- public class ThreeThreadPrintABC {
- private static ReentrantLock lock = new ReentrantLock();
- private static Condition waitA = lock.newCondition();
- private static Condition waitB = lock.newCondition();
- private static Condition waitC = lock.newCondition();
- // 用来控制该打印的线程
- private static int count = 0;
- public static void main(String[] args) {
- Thread printA = new Thread(new PrintA());
- Thread printB = new Thread(new PrintB());
- Thread printC = new Thread(new PrintC());
- printA.start();
- printB.start();
- printC.start();
- }
- static class PrintA implements Runnable {
- @Override
- public void run() {
- for (int i = 0; i < 10; i++) {
- lock.lock();
- try {
- while ((count % 3) != 0) {
- waitA.await();
- }
- System.out.println(Thread.currentThread().getName() + "A");
- count++;
- waitB.signal();
- } catch (InterruptedException e) {
- e.printStackTrace();
- } finally {
- lock.unlock();
- }
- }
- }
- }
- static class PrintB implements Runnable {
- @Override
- public void run() {
- for (int i = 0; i < 10; i++) {
- lock.lock();
- try {
- while ((count % 3) != 1) {
- waitB.await();
- }
- System.out.println(Thread.currentThread().getName() + "B");
- count++;
- waitC.signal();
- } catch (InterruptedException e) {
- e.printStackTrace();
- } finally {
- lock.unlock();
- }
- }
- }
- }
- static class PrintC implements Runnable {
- @Override
- public void run() {
- for (int i = 0; i < 10; i++) {
- lock.lock();
- try {
- while ((count % 3) != 2) {
- waitC.await();
- }
- System.out.println(Thread.currentThread().getName() + "C");
- count++;
- waitA.signal();
- } catch (InterruptedException e) {
- e.printStackTrace();
- } finally {
- lock.unlock();
- }
- }
- }
- }
- }
9, 进程间通信的方式? 线程间通信的方式?
- import java.util.HashSet;
- import java.util.Set;
- import java.util.concurrent.BlockingQueue;
- import java.util.concurrent.Executors;
- import java.util.concurrent.LinkedBlockingQueue;
- public class MyThreadPool {
- private int workerCount;
- private int corePoolSize;
- private BlockingQueue<Runnable> workQueue;
- private Set<Worker> workers;
- private volatile boolean RUNNING = true;
- public MyThreadPool(int corePoolSize) {
- this.corePoolSize = corePoolSize;
- workQueue = new LinkedBlockingQueue<>();
- workers = new HashSet<>();
- }
- public void execute(Runnable r) {
- if (workerCount <corePoolSize) {
- addWorker(r);
- } else {
- try {
- workQueue.put(r);
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- private void addWorker(Runnable r) {
- workerCount++;
- Worker worker = new Worker(r);
- Thread t = worker.thread;
- workers.add(worker);
- t.start();
- }
- class Worker implements Runnable {
- Runnable task;
- Thread thread;
- public Worker(Runnable task) {
- this.task = task;
- this.thread = new Thread(this);
- }
- @Override
- public void run() {
- while (RUNNING) {
- Runnable task = this.task;
- // 执行当前的任务, 所以把这个任务置空, 以免造成死循环
- this.task = null;
- if (task != null || (task = getTask()) != null) {
- task.run();
- }
- }
- }
- }
- private Runnable getTask() {
- Runnable r = null;
- try {
- r = workQueue.take();
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- return r;
- }
- public static void main(String[] args) {
- MyThreadPool threadPool = new MyThreadPool(5);
- Runnable r = new Writer();
- for (int i = 0; i < 10; i++) {
- threadPool.execute(r);
- }
- }
- }
- class Writer implements Runnable {
- @Override
- public void run() {
- System.out.println(Thread.currentThread().getName() + " ");
- }
- }
- wait()/notify()
- await()/signal()
- BlockingQueue
- public E take() {
- lock.lock();
- try {
- // 当队列为空, 不能取, 必须等待
- while (count==0) {
- notEmpty.await();
- }
- // 不再阻塞说明队列有元素了, 直接删除并返回
- return dequeue();
- } finally {
- lock.unlock();
- }
- }
- private void enqueue(E x) {
- // ...insert element
- // 因为插入了元素, 说明队列不为空, 唤醒在 notEmpty 上等待的线程
- notEmpty.signal();
- }
- public void put(E e) {
- lock.lock();
- try {
- // 队列满了, 不能放入, 必须等待
- while (count == items.length) {
- notFull.await();
- }
- // 此时队列不为满, 可以放入
- enqueue(e);
- } finally {
- lock.unlock();
- }
- }
- private E dequeue() {
- // ...delete element
- // 移除了元素, 因而队列不为满, 唤醒在 notFull 上等待的线程
- E x = (E) items[takeIndex];
- notFull.signal();
- return x;
- }
- package easy;
- import java.util.Random;
- import java.util.concurrent.BlockingQueue;
- import java.util.concurrent.ExecutorService;
- import java.util.concurrent.Executors;
- import java.util.concurrent.LinkedBlockingQueue;
- public class ProducerConsumer {
- public static class Producer implements Runnable {
- private BlockingQueue<Integer> blockingQueue;
- private Random random = new Random();
- public Producer(BlockingQueue<Integer> blockingQueue) {
- this.blockingQueue = blockingQueue;
- }
- @Override
- public void run() {
- while (true) {
- Integer a = makeProduct();
- try {
- blockingQueue.put(a);
- System.out.println(Thread.currentThread().getName() + "生产了" + a + "队列大小" + blockingQueue.size());
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- public Integer makeProduct() {
- try {
- Thread.sleep(1000);
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- return random.nextInt(10);
- }
- }
- public static class Consumer implements Runnable {
- private BlockingQueue<Integer> blockingQueue;
- public Consumer(BlockingQueue<Integer> blockingQueue) {
- this.blockingQueue = blockingQueue;
- }
- @Override
- public void run() {
- while (true) {
- Integer a = useProduct();
- System.out.println(Thread.currentThread().getName() + "消费产品" + a + "队列大小" + blockingQueue.size());
- }
- }
- public Integer useProduct() {
- Integer a = null;
- try {
- a = blockingQueue.take();
- Thread.sleep(1000);
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- return a;
- }
- }
- public static void main(String[] args) {
- BlockingQueue<Integer> blockingQueue = new LinkedBlockingQueue<>(5);
- ExecutorService exec = Executors.newCachedThreadPool();
- int producerNum = 3;
- int consumerNum = 5;
- for (int i = 0; i <producerNum; i++) {
- exec.submit(new Producer(blockingQueue));
- }
- for (int i = 0; i < consumerNum; i++) {
- exec.submit(new Consumer(blockingQueue));
- }
- }
- }
- ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
- Lock readLock = readWriteLock.readLock();
- Lock writeLock = readWriteLock.writeLock();
- if (finishing) {
- nextTable = null;
- table = nextTab;
- sizeCtl = (n << 1) - (n>>> 1);
- return;
- }
- // set 方法
- public void set(T value) {
- Thread t = Thread.currentThread();
- ThreadLocalMap map = getMap(t);
- if (map != null)
- map.set(this, value);
- else
- createMap(t, value);
- }
- // 上面的 getMap 方法
- ThreadLocalMap getMap(Thread t) {
- return t.threadLocals;
- }
- // get 方法
- public T get() {
- Thread t = Thread.currentThread();
- ThreadLocalMap map = getMap(t);
- if (map != null) {
- ThreadLocalMap.Entry e = map.getEntry(this);
- if (e != null) {
- @SuppressWarnings("unchecked")
- T result = (T)e.value;
- return result;
- }
- }
- return setInitialValue();
- }
- t1.threadLocals.set(tl1, obj1) // 等价于在 t1 线程中调用 tl1.set(obj1)
- t1.threadLocals.set(tl2, obj2) // 等价于在 t1 线程中调用 tl2.set(obj1)
- t1.threadLocals.getEntry(tl1) // 等价于在 t1 线程中调用 tl1.get()获得 obj1
- t1.threadLocals.getEntry(tl2) // 等价于在 t1 线程中调用 tl2.get()获得 obj2
- public enum State {
- NEW,
- RUNNABLE,
- BLOCKED,
- WAITING,
- TIMED_WATING,
- TERMINATED;
- }
- private static ThreadLocal<Connection> connectionHolder = new ThreadLocal<Connection>() {
- public Connection initialValue() {
- return DriverManager.getConnection(DB_URL);
- }
- };
- public static Connection getConnection() {
- return connectionHolder.get();
- }
- private static final ThreadLocal threadSession = new ThreadLocal();
- public static Session getSession() throws InfrastructureException {
- Session s = (Session) threadSession.get();
- try {
- if (s == null) {
- s = getSessionFactory().openSession();
- threadSession.set(s);
- }
- } catch (HibernateException ex) {
- throw new InfrastructureException(ex);
- }
- return s;
- }
- SELECT * FROM table WHERE a = 1 AND c = 3; // 使用了索引 a,c 不走索引
- SELECT * FROM table WHERE a = 1 AND b <2 AND c = 3; // 使用到了索引(a,b),c 不走索引
- top - 17:35:12 up 5 min, 1 user, load average: 0.05, 0.16, 0.09
- Tasks: 141 total, 1 running, 105 sleeping, 0 stopped, 0 zombie
- %Cpu(s): 3.5 us, 1.7 sy, 0.0 ni, 94.8 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st
- KiB Mem : 3073524 total, 1547424 free, 528024 used, 998076 buff/cache
- KiB Swap: 4194304 total, 4194304 free, 0 used. 2316492 avail Mem
- PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+
- 585 root 20 0 978032 91332 44924 S 2.0 3.0 0:03.97 Xorg
- 2129 sun 20 0 533920 39272 30000 S 1.7 1.3 0:01.95 deepin-termin+
- 911 sun 20 0 796128 24480 19976 S 1.0 0.8 0:00.94 dde-session-i+
- 330 root 20 0 629996 17244 13288 S 0.7 0.6 0:00.38 dde-system-da+
- 751 sun 20 0 118800 2184 1796 S 0.3 0.1 0:00.90 VBoxClient
- total used free shared buff/cache available
- Mem: 3073524 536724 1603808 75300 932992 2302016
- Swap: 4194304 0 4194304
- udev 1.5G 0 1.5G 0% /dev
- tmpfs 301M 1.2M 299M 1% /run
- /dev/sda1 30G 20G 8.2G 71% /
- tmpfs 1.5G 0 1.5G 0% /dev/shm
- tmpfs 5.0M 4.0K 5.0M 1% /run/lock
- tmpfs 1.5G 0 1.5G 0% /sys/fs/cgroup
- vmshare 238G 193G 46G 81% /mnt/work
- tmpfs 301M 12K 301M 1% /run/user/1000
- /dev/sr0 56M 56M 0 100% /media/sun/VBox_GAs_5.2.12
- UID PID PPID C STIME TTY TIME CMD
- root 1 0 0 15:56 ? 00:00:01 /sbin/init splash
- root 2 0 0 15:56 ? 00:00:00 [kthreadd]
- root 4 2 0 15:56 ? 00:00:00 [kworker/0:0H]
- root 6 2 0 15:56 ? 00:00:00 [mm_percpu_wq]
- root 7 2 0 15:56 ? 00:00:00 [ksoftirqd/0]
- root 8 2 0 15:56 ? 00:00:00 [rcu_sched]
- import java.util.HashMap;
- import java.util.LinkedList;
- public class LRUCache2<K,V> {
- private final int cacheSize;
- private LinkedList<K> cacheList = new LinkedList<>();
- private HashMap<K,V> map = new HashMap<>();
- public LRUCache2(int cacheSize) {
- this.cacheSize = cacheSize;
- }
- public synchronized void put(K key, V val) {
- if (!map.containsKey(key)) {
- if (map.size()>= cacheSize) {
- removeLastElement();
- }
- cacheList.addFirst(key);
- map.put(key, val);
- } else {
- moveToFirst(key);
- }
- }
- public V get(K key) {
- if (!map.containsKey(key)) {
- return null;
- }
- moveToFirst(key);
- return map.get(key);
- }
- private synchronized void moveToFirst(K key) {
- cacheList.remove(key);
- cacheList.addFirst(key);
- }
- private synchronized void removeLastElement() {
- K key = cacheList.removeLast();
- map.remove(key);
- }
- @Override
- public String toString() {
- return cacheList.toString();
- }
- public static void main(String[] args) {
- LRUCache2<String,String> lru = new LRUCache2<>(4);
- lru.put("C", null);
- lru.put("A", null);
- lru.put("D", null);
- lru.put("B", null);
- lru.put("E", null);
- lru.put("B", null);
- lru.put("A", null);
- lru.put("B", null);
- lru.put("C", null);
- lru.put("D", null);
- System.out.println(lru);
- }
- }
- /* out:
- [D, C, B, A]
- */
- import java.util.LinkedHashMap;
- import java.util.Map;
- public class LRUCache<K,V> extends LinkedHashMap<K, V> {
- static final float LOAD_FACTOR = 0.75f;
- static final boolean ACCESS_ORDER = true;
- private int cacheSize;
- public LRUCache(int initialCapacity, int cacheSize) {
- super(initialCapacity, LOAD_FACTOR, ACCESS_ORDER);
- this.cacheSize = cacheSize;
- }
- @Override
- protected synchronized boolean removeEldestEntry(Map.Entry eldest) {
- return size()> cacheSize;
- }
- @Override
- public V get(Object key) {
- return super.get(key);
- }
- @Override
- public synchronized V put(K key, V value) {
- return super.put(key, value);
- }
- public static void main(String[] args) {
- LRUCache<String, String> lru = new LRUCache<>(4, 4);
- lru.put("C", null);
- lru.put("A", null);
- lru.put("D", null);
- lru.put("B", null);
- lru.put("E", null);
- lru.put("B", null);
- lru.put("A", null);
- lru.put("B", null);
- lru.put("C", null);
- lru.put("D", null);
- System.out.println(lru);
- }
- }
- public interface Subject {
- void resisterObserver(Observer o);
- void removeObserver(Observer o);
- void notifyObserver();
- }
- public interface Observer {
- void update(float temp, float humidity, float pressure);
- }
- public class WeatherData implements Subject {
- private List<Observer> observers;
- private float temperature;
- private float humidity;
- private float pressure;
- public WeatherData() {
- observers = new ArrayList<>();
- }
- public void setMeasurements(float temperature, float humidity, float pressure) {
- this.temperature = temperature;
- this.humidity = humidity;
- this.pressure = pressure;
- notifyObserver();
- }
- @Override
- public void resisterObserver(Observer o) {
- observers.add(o);
- }
- @Override
- public void removeObserver(Observer o) {
- int i = observers.indexOf(o);
- if (i>= 0) {
- observers.remove(i);
- }
- }
- @Override
- public void notifyObserver() {
- for (Observer o : observers) {
- o.update(temperature, humidity, pressure);
- }
- }
- }
- /* 观察者 1 */
- public class StatisticsDisplay implements Observer {
- public StatisticsDisplay(Subject weatherData) {
- weatherData.resisterObserver(this);
- }
- @Override
- public void update(float temp, float humidity, float pressure) {
- System.out.println("StatisticsDisplay.update:" + temp + "" + humidity +" " + pressure);
- }
- }
- /* 观察者 2 */
- public class CurrentConditionsDisplay implements Observer {
- public CurrentConditionsDisplay(Subject weatherData) {
- weatherData.resisterObserver(this);
- }
- @Override
- public void update(float temp, float humidity, float pressure) {
- System.out.println("CurrentConditionsDisplay.update:" + temp + "" + humidity +" " + pressure);
- }
- }
- /* 测试类 */
- public class WeatherStation {
- public static void main(String[] args) {
- WeatherData weatherData = new WeatherData();
- CurrentConditionsDisplay currentConditionsDisplay = new CurrentConditionsDisplay(weatherData);
- StatisticsDisplay statisticsDisplay = new StatisticsDisplay(weatherData);
- weatherData.setMeasurements(0, 0, 0);
- weatherData.setMeasurements(1, 1, 1);
- }
- }
- by @sunhaiyu
来源: https://www.cnblogs.com/sun-haiyu/p/9663575.html