[数据结构与算法] 面经总结（一）

继承Thread类，重写run方法。
实现Runnable接口，实现run方法。
实现Callable接口，实现call方法。通过FutureTask创建一个线程，获取到线程执行的返回值。callable和Runnable的区别是callable可以有返回值，也可以抛出异常的特性，而Runnable没有。
通过线程池来开启线程。

2、生产者消费者模式

public class ValueOP {
    private String s="";
    public void setValue(){
        synchronized (this){
            if(!s.equals("")){
                try {
                    this.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            s="produce";
            System.out.println("生产"+s);
            this.notify();
        }
    }
    public void getValue(){
        synchronized (this){
            if(s.equals("")){
                try {
                    this.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            System.out.println("获得"+s);
            s="";
            this.notify();
        }
    }
}

public class Producer extends Thread {
    private ValueOP valueOP;
    public Producer(ValueOP valueOP){
        this.valueOP=valueOP;
    }

    @Override
    public void run() {
        while(true){
            valueOP.setValue();
        }
    }
}

public class Customer extends Thread{
    private ValueOP valueOP;
    public Customer(ValueOP valueOP){
        this.valueOP=valueOP;
    }

    @Override
    public void run() {
        while(true){
            valueOP.getValue();
        }
    }
}

3、怎么保证线程安全？

synchronized修饰
volatile实现同步（只能保证可见性，不能保证原子性）
使用局部变量ThreadLocal
使用原子类（AtomicInteger、AtomicBoolean……）
使用Lock
使用容器类（BlockingQueue、ConcurrentHashMap）

4、HashMap的相关面试题

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

4.1 哈希冲突

????????哈希是通过对数据进行再压缩，提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对应相同的值。这时候就产生了哈希冲突。

解决哈希冲突的四种方法

开放地址方法
- 线性探测：按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。　
- 再平方探测：按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。
- 伪随机探测：　按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。
链式地址法（HashMap的哈希冲突解决方法）：
- 优点：
  - 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
  - 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
  - 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
  - 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
- 缺点：指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。
建立公共溢出区：建立公共溢出区存储所有哈希冲突的数据。
再哈希法：　对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。

4.2 重要变量介绍

DEFAULT_INITIAL_CAPACITY Table数组的初始化长度： 1 << 4 2^4=16
MAXIMUM_CAPACITY Table数组的最大长度： 1<<30 2^30=1073741824
DEFAULT_LOAD_FACTOR 负载因子：默认值为0.75。当元素的总个数>当前数组的长度 * 负载因子。数组会进行扩容，扩容为原来的两倍
TREEIFY_THRESHOLD 链表树化阙值：默认值为 8 。表示在一个node（Table）节点下的值的个数大于8时候，会将链表转换成为红黑树。
UNTREEIFY_THRESHOLD 红黑树链化阙值：默认值为 6 。表示在进行扩容期间，单个Node节点下的红黑树节点的个数小于6时候，会将红黑树转化成为链表。
MIN_TREEIFY_CAPACITY = 64 最小树化阈值，当Table所有元素超过改值，才会进行树化（为了防止前期阶段频繁扩容和树化过程冲突）。

4.3 扩容时为什么要扩容为原来的二倍

??????? 在HashMap中通过hash&(table.length-1)来获取其在数组中的存放位置。只有table.length为2的幂次数，才能使得数据在数组上较为均匀的分布。否则的话，会有一些地方分不到数据。

4.4 put方法的执行过程

对key的hashCode()做hash运算，计算index;
如果没碰撞直接放到bucket?；
如果碰撞了，bucket如果是链表则以链表的形式存在buckets后，在JDK1.8中采用的是尾插法，如果是红黑树，则存入树中，在树中是以hash的大小顺序构建的。
如果碰撞导致链表过?(?于等于TREEIFY_THRESHOLD)，就把链表转换成红?树(JDK1.8中的改动)；
如果节点已经存在就替换old value(保证key的唯?性)
如果bucket满了(超过load factor*current capacity)，就要resize

4.5 get方法的执行过程

对key的hashCode()做hash运算，计算index;
如果在bucket?的第?个节点?直接命中，则直接返回；
如果有冲突，则通过key.equals(k)去查找对应的Entry;
若为树，则在树中通过key.equals(k)查找，O(logn)；
若为链表，则在链表中通过key.equals(k)查找，O(n)。

4.6 hash算法的种类

硬哈希：分布式系统中，假设有 n 个节点，传统方案使用?mod(key, n)?映射数据和节点。当扩容或缩容时(哪怕只是增减1个节点)，映射关系变为?mod(key, n+1)?/?mod(key, n-1)，绝大多数数据的映射关系都会失效。
MD5：一种可以将任意长度的输入转化为固定长度输出的算法（严格来说不能称之为一种加密算法，但是它可以达到加密的效果）。我们知道MD5值总是一个32位的十六进制字符串，换算成二进制就是一个128位的字符串。
MD4：它适用在32位字长的处理器上用高速软件实现——它是基于 32位操作数的位操作来实现的。
MurmurHash： 是一种非加密型哈希函数，适用于一般的哈希检索操作。由Austin Appleby在2008年发明，并出现了多个变种，都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。

4.7? 知道jdk1.8中hashmap改了什么吗？

由数组+链表的结构改为数组+链表+红?树。
jdk1.7中当哈希表为空时，会先调用inflateTable()初始化一个数组；而1.8则是直接调用resize()扩容;
插入键值对的put方法的区别，1.8中会将节点插入到链表尾部，而1.7中是采用头插；
扩容时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序；而且1.8是在元素插入后检测是否需要扩容，1.7则是在元素插入前；
jdk1.8是扩容时通过hash&cap==0将链表分散，无需改变hash值，而1.7是通过更新hashSeed来修改hash值达到分散的目的；
优化了?位运算的hash算法：h^(h>>>16)，这段代码是为了对key的hashCode进行扰动计算，防止不同hashCode的高位不同但低位相同导致的hash冲突。简单点说，就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。
扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。hashmap在1.8中，不会在出现死循环问题。

4.8说一下为什么会出现线程的不安全性

在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。
在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况。

4.9 为什么不一开始就使用红黑树，不是效率很高吗?

????????因为红?树需要进?左旋，右旋，变?这些操作来保持平衡，?单链表不需要。当元素?于8个当时候，此时做查询操作，链表结构已经能保证查询性能。当元素?于8个的时候，此时需要红?树来加快查询速度，但是新增节点的效率变慢了。因此，如果?开始就?红?树结构，元素太少，新增效率??较慢，?疑这是浪费性能的。

4.10 什么时候退化为链表

?????? 为6的时候退转为链表。中间有个差值7可以防?链表和树之间频繁的转换。假设?下，如果设计成链表个数超过8则链表转换成树结构，链表个数?于8则树结构转换成链表，如果?HashMap不停的插?、删除元素，链表个数在8左右徘徊，就会频繁的发?树转链表、链表转树，效率会很低。

4.11 一般用什么作为key值

?????????般?Integer、String这种不可变类当HashMap当key，?且String最为常?。

因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使?字符串。
因为获取对象的时候要?到equals()和hashCode()?法，那么键对象正确的重写这两个?法是?常重要的,这些类已经很规范的覆写了hashCode()以及equals()?法。

4.12 用可变类当Hashmap1的Key会有什么问题

????????hashcode可能会发生变化，导致put进行的值，无法get出来

4.13 实现一个自定义的class作为Hashmap的key该如何实现

重写hashcode和equals方法
- 两个对象相等，hashcode?定相等
- 两个对象不等，hashcode不?定不等
- hashcode相等，两个对象不?定相等
- hashcode不等，两个对象?定不等
设计一个不变的类
- 类添加final修饰符，保证类不被继承。如果类可以被继承会破坏类的不可变性机制，只要继承类覆盖?类的?法并且继承类可以改变成员变量值，那么?旦?类以?类的形式出现时，不能保证当前类是否可变。
- 保证所有成员变量必须私有，并且加上final修饰通过这种?式保证成员变量不可改变。但只做到这?步还不够，因为如果是对象成员变量有可能再外部改变其值。所以第4 点弥补这个不?
- 不提供改变成员变量的?法，包括setter 避免通过其他接?改变成员变量的值，破坏不可变特性。
- 通过构造器初始化所有成员，进?深拷?(deep copy)
- 在getter?法中，不要直接返回对象本?，?是克隆对象，并返回对象的拷? 这种做法也是防?对象外泄，防?通过getter获得内部可变成员对象后对成员变量直接操作，导致成员变量发?改变

4.14 HashMap的遍历方法

方法一：map.keySet();可以用forEach()遍历，也可以采用Iterator()遍历。

public class MyHashMap {
    public static void main(String[] args) {
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(1,2);
        map.put(2,3);
        map.put(3,4);
        Set<Integer> integers = map.keySet();
        for(Integer i:integers){
            System.out.println(map.get(i));
        }

    }
}

? 方法二：map.entrySet()获取节点的集合,可以用forEach()遍历，也可以采用Iterator()遍历。

public class MyHashMap {
    public static void main(String[] args) {
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(1,2);
        map.put(2,3);
        map.put(3,4);
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            System.out.println(entry.getKey()+"----"+entry.getValue());
        }

    }
}

方法三：forEach和lambda表达式

public class TestDemo {
    public static void main(String[] args) {
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(1,2);
        map.put(2,3);
        map.put(3,4);
        map.forEach((key,value)->{
            System.out.println(key+"---"+value);
        });
    }
}

方法四：使用 Stream API 遍历 HashMap

public class TestDemo {
    public static void main(String[] args) {
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(1,2);
        map.put(2,3);
        map.put(3,4);
        map.entrySet().stream().forEach((entrySet)->{
            System.out.println(entrySet.getKey()+"----"+entrySet.getValue());
        });
    }
}

5、HashMap和HashTable的区别

继承的接口和类不同：HashMap?extends?AbstractMap 而Hashtable?extends?Dictionary
线程安全:Hashtable?是线程安全的效率稍低，HashMap?不是线程安全的效率高
hashmap 允许有null的键和值，hashtable 不允许有null的键和值
支持的遍历种类不同，HashMap只支持Iterator(迭代器)遍历，而Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历
通过Iterator迭代器遍历时，遍历的顺序不同，HashMap是“从前向后”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。Hashtabl是“从后往前”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。
容量的初始值和增加方式都不一样，HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”。创建时，如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。也就是说Hashtable会尽量使用素数、奇数。而HashMap则总是使用2的幂作为哈希表的大小。
添加key-value时的hash值算法不同，HashMap添加元素时，是使用自定义的哈希算法。Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。
获取数组下标的方法不同，hashtable使用的是取余，hashmap使用的是位运算。

6、ConcurrentHashMap的相关面试题

6.1 JDK8的ConcurrentHashMap和JDK7的ConcurrentHashMap有什么区别？

JDK8中新增了红黑树
JDK7中使用的是头插法，JDK8中使用的是尾插法
JDK7中使用了分段锁，而JDK8中没有使用分段锁了
JDK7中使用了ReentrantLock，JDK8中没有使用ReentrantLock了，而使用了Synchronized
JDK7中的扩容是每个Segment内部进行扩容，不会影响其他Segment，而JDK8中的扩容和HashMap的扩容类似，只不过支持了多线程扩容，并且保证了线程安全。

6.2 ConcurrentHashMap是如何保证并发安全的？

????????JDK7中ConcurrentHashMap是通过ReentrantLock+CAS+分段思想来保证的并发安全的，在JDK7的ConcurrentHashMap中，首先有一个Segment数组，存的是Segment对象，Segment相当于一个小HashMap，Segment内部有一个HashEntry的数组，也有扩容的阈值，同时Segment继承了ReentrantLock类，同时在Segment中还提供了put，get等方法，比如Segment的put方法在一开始就会去加锁，加到锁之后才会把key,value存到Segment中去，然后释放锁。

????????同时在ConcurrentHashMap的put方法中，会通过CAS的方式把一个Segment对象存到Segment数组的某个位置中。同时因为一个Segment内部存在一个HashEntry数组，所以和HashMap对比来看，相当于分段了，每段里面是一个小的HashMap，每段公用一把锁，同时在ConcurrentHashMap的构造方法中是可以设置分段的数量的，叫做并发级别concurrencyLevel.

????????JDK8中ConcurrentHashMap是通过synchronized+cas（Unsafe类）来实现了。在JDK8中只有一个数组，就是Node数组，Node就是key，value，hashcode封装出来的对象，和HashMap中的Entry一样，在JDK8中通过对Node数组的某个index位置的元素进行同步，达到该index位置的并发安全。同时内部也利用了CAS对数组的某个位置进行并发安全的赋值。

6.3 JDK8中的ConcurrentHashMap为什么使用synchronized来进行加锁？

想比于JDK7中使用ReentrantLock来加锁，因为JDK7中使用了分段锁，所以对于一个ConcurrentHashMap对象而言，分了几段就得有几个ReentrantLock对象，表示得有对应的几把锁。
而JDK8中使用synchronized关键字来加锁就会更节省内存，并且jdk也已经对synchronized的底层工作机制进行了优化，效率更好。

6.4 JDK7中的ConcurrentHashMap是如何扩容的？

????????JDK7中的ConcurrentHashMap和JDK7的HashMap的扩容是不太一样的，首先JDK7中也是支持多线程扩容的，原因是，JDK7中的ConcurrentHashMap分段了，每一段叫做Segment对象，每个Segment对象相当于一个HashMap，分段之后，对于ConcurrentHashMap而言，能同时支持多个线程进行操作，前提是这些操作的是不同的Segment，而ConcurrentHashMap中的扩容是仅限于本Segment，也就是对应的小型HashMap进行扩容，所以是可以多线程扩容的。每个Segment内部的扩容逻辑和HashMap中一样。

6.5 JDK8中的ConcurrentHashMap是如何扩容的？

????????首先，JDK8中是支持多线程扩容的，JDK8中的ConcurrentHashMap不再是分段，或者可以理解为每个桶为一段，在需要扩容时，首先会生成一个双倍大小的数组，生成完数组后，线程就会开始转移元素，在扩容的过程中，如果有其他线程在put，那么这个put线程会帮助去进行元素的转移，虽然叫转移，但是其实是基于原数组上的Node信息去生成一个新的Node的，也就是原数组上的Node不会消失，因为在扩容的过程中，如果有其他线程在get也是可以的。

6.6 JDK8中的ConcurrentHashMap有一个CounterCell，你是如何理解的？

????????CounterCell是JDK8中用来统计ConcurrentHashMap中所有元素个数的，在统计ConcurentHashMap时，不能直接对ConcurrentHashMap对象进行加锁然后再去统计，因为这样会影响ConcurrentHashMap的put等操作的效率，在JDK8的实现中使用了CounterCell+baseCount来辅助进行统计，baseCount是ConcurrentHashMap中的一个属性，某个线程在调用ConcurrentHashMap对象的put操作时，会先通过CAS去修改baseCount的值，如果CAS修改成功，就计数成功，如果CAS修改失败，则会从CounterCell数组中随机选出一个CounterCell对象，然后利用CAS去修改CounterCell对象中的值，因为存在CounterCell数组，所以，当某个线程想要计数时，先尝试通过CAS去修改baseCount的值，如果没有修改成功，则从CounterCell数组中随机取出来一个CounterCell对象进行CAS计数，这样在计数时提高了效率。

????????所以ConcurrentHashMap在统计元素个数时，就是baseCount加上所有CountCeller中的value只，所得的和就是所有的元素个数。

6.7? hashmap，hashtable与concurrenthashMap的区别

HashTable

底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化
初始size为11，扩容：newsize = olesize*2+1
计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

HashMap

底层数组+链表实现，可以存储null键和null值，线程不安全
初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂
扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀
计算index方法：index = hash & (tab.length – 1)

ConcurrentHashMap

底层采用分段的数组+链表实现，线程安全
通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容

6.8 ConcurrentHashMap的读操作不需要加锁

??????? 因为map中的node节点是被volatile修饰的，该关键字能保证线程间的可见性。每次读取数据时都从主存中读取，不是从缓存中读取。

缓存一致性协议：当某个线程在写数据时，如果发现被操作的变量是共享变量，cpu则会通知其他线程该变量的缓存行是无效的，因此其他线程在读取该变量时会发现其变量无效而去主内存中加载数据；

6.9 为什么Java8中HashMap链表使用红黑树而不是AVL树

????????在ConcurrentHashMap中是加锁了的，如果写冲突就会等待，如果插入时间过长必然等待时间更长，而红黑树相对AVL树他的插入更快。而对于读操作没有显式锁，只用了volatile关键字，对并发的影响较小。

6.10 为什么不一直使用树？

????????内存占用与存储桶内查找复杂性之间的权衡，大多数哈希函数将产生非常少的冲突，因此为大小为3或4的桶维护树将是非常昂贵的，没有充分的理由。

7、什么是协程

????????协程，英文Coroutines，是一种比线程更加轻量级的存在。正如一个进程可以拥有多个线程一样，一个线程也可以拥有多个协程。协程既不是进程也不是线程，协程仅仅是一个特殊的函数，协程它与进程和线程不是一个维度的。

??????? 最重要的是，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。

8、什么是上下文切换

????????上下文切换指的是内核（操作系统的核心）在CPU上对进程或者线程进行切换。上下文切换过程中的信息被保存在进程控制块（PCB-Process Control Block）中。PCB又被称作切换帧（SwitchFrame）。上下文切换的信息会一直被保存在CPU的内存中，直到被再次使用。?????

????????上下文切换 (context switch) , 其实际含义是任务切换, 或者CPU寄存器切换。当多任务内核决定运行另外的任务时, 它保存正在运行任务的当前状态, 也就是CPU寄存器中的全部内容。这些内容被保存在任务自己的堆栈中, 入栈工作完成后就把下一个将要运行的任务的当前状况从该任务的栈中重新装入CPU寄存器, 并开始下一个任务的运行, 这一过程就是context switch。

9、红黑树与AVL树，各自的优缺点总结

红黑树不追求"完全平衡"，即不像AVL那样要求节点的 |balFact| <= 1，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。
就插入节点导致树失衡的情况，AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance，旋转的量级是O(1)。删除节点导致失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小。
AVL的结构相较于RB-Tree更为平衡，插入和删除引起失衡，如2所述，RB-Tree复衡效率更高；当然，由于AVL高度平衡，因此AVL的Search效率更高啦。
针对插入和删除节点导致失衡后的rebalance操作，红黑树能够提供一个比较"便宜"的解决方案，降低开销，是对search，insert ，以及delete效率的折衷，总体来说，RB-Tree的统计性能高于AVL。