JAVA后端八股文（更新中）

• java
• • String，StringBuffer和StringBuilder
  • java集合

• String：String对象维护了一个char数组，并且String对象是不可修改的（在不使用反射的情况下）。
  （1）String对象源代码，可以看到当用new关键字创建一个String对象时，如果不出入参数，会创建一个空的字符串，如果传入对象，则将这个对象的char数组赋值给当前对象，并将这个对象的hash值赋值给当前对象。

public final class String
    implements java.io.Serializable, Comparable, CharSequence {
    private final char value[];
    private int hash; // Default to 0
    private static final long serialVersionUID = -6849794470754667710L;
    private static final ObjectStreamField[] serialPersistentFields =
        new ObjectStreamField[0];
    public String() {
        this.value = new char[0];
    }
    public String(String original) {
        this.value = original.value;
        this.hash = original.hash;
    }
    public String(char value[]) {
        this.value = Arrays.copyOf(value, value.length);
    }
}

（2）String对象的值为什么不可被修改？
可能会觉得是因为char数组用final关键字修改，可是这只是说明数组不能被修改而数组中的值是可以修改的。事实上修改char数组的值有4种方法：第一种如果数组是public修饰的则可以直接通过对象访问并修改，第二种通过String提供的诸如set等方法修改，第三种通过继承String类在子类中修改，第四种通过反射进行修改。事实上前三种方法都被java的api开发者堵死了。
第一种：数组是private修饰的无法直接访问。
第二种：String类并没有提供可以修改char数组的方法。
第三种：String类时final进行修改的无法继承。
（3）String对象的两种创建方式
<1>使用双引号“ ”创建：使用双引号创建时创建的是常量，存放在常量池中。
<2>使用new关键字创建：使用new关键字创建时创建的是对象，存放在堆中。
使用new关键字创建有三种：第一种使用无参数构造函数，此时的字符串为空。第二种有参构造函数，参数为一个String对象，这时会将传入String对象的数组和hash值赋值给创建的对象。第三种有参构造函数，参数为一个char数组，这时会将传入的char数组赋值给被创建的对象。
（4）两个字符串对象是否相等
在此之前我们需要知道一些变量的存放位置：
栈：存放基本类型的变量数据和对象的引用
堆：存放使用new创建的对象
常量池：存放字符串常量和基本类型常量
静态于：存放静态成员（static定义的

注意用==判断是，其实是判断这两个字符串是否是一个对象。
下面的代码中会返回false，这是因为二者并不是同一个对象。在前面我们也介绍了使用new关键字时会重新创建一个对象，这两个当然不是一个对象。需要注意的是hash值相等两个对象可能不是通过一个对象，能够判断两个对象是否是同一个只能看这两个对象地址是否相同。

String a = "hello";
String b = new String("hello");
System.out.println(a == b);

返回true，使用""创建对象只会创建一次。其实这个很好理解，如果创建两次，怎么区分“hello”与“hello”呢。

String a = "hello";
String b = "hello";
System.out.println(a == b);

返回false，很显然二者不是同一个对象。

String a = new String(new char[]{'h','e','l','l','o'});
String b = new String(new char[]{'h','e','l','l','o'});
System.out.println(a == b);

下面比较复杂，其实我们用==判断两个对象是否相等（引用指向的地址）时，如果这两个对象的值相等并且都存放在常量池中那这两个对象一定相等。可以简单点记，如果+两边是常量，并且常量是"*"表示的字符串或者常量指向的是存放在常量池中的字符串，那新创建的字符串对象一定也存放在常量池中，否则不存放在常量池中。

String a = "hello";
String b = "world";
String c = a + b;
String d = "hello" + "world";
System.out.println(c == d);
//返回false
final String a = "hello";
final String b = "world";
String c = a + b;
String d = a + b;
System.out.println(c == d);
//返回true
String c = "hello" + "world";
String d = "hello" + "world";
System.out.println(c == d);
//返回true
final String a = new String("hello");
final String b = new String("world");
String c = a + b;
String d = a + b;
System.out.println(c == d);
//返回false

• StringBuilder：StringBuilder继承自AbstractStringBuilder，里面的方法几乎都由AbstractStringBuilder实现。AbstractStringBuilder也维护了一个char数组，与String不同的是这个数组没有用final修饰，这也就说明可以对其中的char数组进行修改。
  （1）容量：如果没有指定大小默认为16，如果传入的是字符串，char数组为字符串大小再加16

public StringBuilder() {
        super(16);
    }
public StringBuilder(int capacity) {
	super(capacity);
}
public StringBuilder(String str) {
	super(str.length() + 16);
	append(str);
}

（2）扩容：直接扩容为原来容量的两倍，如果不够大则设置容量为需要容量的大小。

• StringBuffer：与StringBuilder类似，但在所有的写方法上都添加了synchronized关键字。

java集合分为两部分：Map（以键值对形式存放元素），Collection（集合，以元素形式存放数据）
一、Map

• HashMap：维护这一个Entry（对应着JDK1.7）/Node（对应则JDK1.8）类型的数组，数组的每个位置对应着一个桶（链表）。当插入一个键值对时，先获取键对应的hash值，然后模除Entry数组的长度得到对应的下标，采用头插法（JDK1.7）/尾插法（JDK1.8）将创建的节点插入对应的链表。
  （1）初始容量：默认大小为16（HashMap的容量必须为2的幂次，这样是为了得到地址比较均匀，如果指定的初始容量不是2的幂次则会取大于初始容量的最小2的幂次）。
  n%length等价于n&(length - 1)，如果length取得是2的幂次，那么末尾一定是连续的1，这样如果hash值取得是均匀的，得到的数组下标也是均匀的。比如length取16，length - 1 = 000…01111，如果length取15，length - 1 = 000…01110，而1与某个数（取0或1）进行&运行得到的都是这个数本身，而0与这个数&得到就是0，这样如果给定的数是均匀的，模除得到的结果也是均匀的。例如如果对于给定的两个n1, n2他们的末尾分布是0和1，比如n1 = 1，n2 = 0，n1 & (16 - 1）= 1，n2 & (16 - 1) = 0, 而n1 & (15 - 1）= 0，n2 & (15 - 1) = 0，length取15就会导致这两个数进行模除后得到的值相同。
  （2）插入元素：JDK1.7采用头插法插入元素，JDK1.8采用尾插法插入元素，这样可以保持相对顺序并且避免了在多线程环境下可能出现环。在JDK1.8中，当某个链表的长度大8时，会首先检查当前数组的长度，如果小于64则优先进行扩容，否则将这条链表转为红黑树。
  （3）扩容（插入键值对时可能会触发此操作）：当size >= threshold = loadFactor*capacity 时进行扩容，扩容后大小原大小的2倍。size是当前插入元素的个数，threshold是阈值，loadFactor是装载因子默认大小为0.75，capacity是数组大小。除此之外，当有链表的数组大于8时并且当前数组长度小于64时会进行扩容。
  （4）键值可以为空：HashMap运行插入的键值对的值或者键为null，由于null无法获得hash值，所以规定键为null的元素都的hash值都取为0。由于值可能为null，所以判断元素是否存在应该使用containsKey而非判断的到的value是否为null。
  （5）线程不安全：HashMap是线程不安全的，因为没有对修改操作进行加锁。可以使用Collections类中的synchronizedMap方法对HashMap进行包装，得到线程安全的HashMap，本质是对所有的修改操作都加synchronized关键字。
  （6）迭代器：使用Iterator迭代器，是fail-fast的。
• LinkedHashMap：继承了HashMap。LinkedHashMap中的Entry继承了HashMap中的Node节点，通过在Entry中添加before和after来指向前驱和后继节点以此为维持一种顺序（插入顺序或者访问顺序），并且LinkedHashMap维护了head和tail两个节点。
  （1）插入数据时维护链表：HashMap使用put方法添加数据，put方法调用了putVal方法，putVal方法又调用了newNode方法。LinkedHashMap重写了newNode方法，newNode里调用linkNodeLast方法将节点添加在链表末尾。

Node newNode(int hash, K key, V value, Node e) {
	LinkedHashMap.Entry p =
	new LinkedHashMap.Entry(hash, key, value, e);
	linkNodeLast(p);
	return p;
}

（2）删除时维护链表：HashMap使用remove方法移除数据，remove调用了removeNode，removeNode调用了afterNodeRemoval方法。LinkedHashMap重写了afterNodeRemoval方法，该方法维护了删除后节点后链表的操作。

void afterNodeRemoval(Node e) { // unlink
        LinkedHashMap.Entry p =
            (LinkedHashMap.Entry)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

（3）维护链表的顺序：LinkedHashMap支持两种链表排序规则，FIFO（默认顺序，插入顺序，最近插入的在链表尾部），LRU（最近访问的在链表尾部）。accessOrder用来控制使用哪种规则排序，默认为false使用FIFO，如果为true则使用LRU。主要使用下面两种方法来维护链表的顺序

void afterNodeAccess(Node p) { }	//访问时调用，插入时键已经存在（如果不存在，FIFO和LRU插入的位置都在链表尾部）
void afterNodeInsertion(boolean evict) { }	//插入时调用

当访问一个节点时，如果accessOrder = true并且被访问节点不在链表尾部则将被访问节点移到链表尾部。

void afterNodeAccess(Node e) { // move node to last
        LinkedHashMap.Entry last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry p =
                (LinkedHashMap.Entry)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

当插入一个节点后，执行afterNodeInsertion方法，如果evict（accessOrder的值）为true，链表不为空，removeEldestEntry(first)返回true，则删除链表头部节点。removeEldestEntry(first)方法默认返回false。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

（4）利用LinkedHashMap实现LRU 缓存：我们只需要继承LinkedHashMap，设置accessOrder为true，然后重写removeEldestEntry(first)方法，当容量大于设定的值时返回true。

class LRUCache extends LinkedHashMap {
    private static final int MAX_ENTRIES = 3;

    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

    LRUCache() {
        super(MAX_ENTRIES, 0.75f, true);
    }
}

• Hasthable：是线程安全的（通过对部分读写操作添加synchronized实现），但其在单线程和多线程环境下效率比较地下，因此不Oracle官方已将其弃用。
  （1）初始容量：默认大小为11（不要求容量是2的幂次，因此得到的散列地址不均匀）。
  （2）插入元素：与HashMap类似，但Hashtable一直采用链表而没有使用红黑树
  （3）扩容（插入键值对时可能会触发此操作）：当size >= threshold = loadFactor*capacity 时进行扩容，扩容后大小原大小的2倍加1。size是当前插入元素的个数，threshold是阈值，loadFactor是装载因子默认大小为0.75，capacity是数组大小。
  （4）Hashtable的键与值都不允许为null，假设可以为null
  在多线程环境下，如果我们用get得到的是null，这有两种可能，值为null或者不存在。假设查找的键不存在，在调用containsKey时应该返回false，但如果在此之前插入键并且值为null，那containsKey就返回true，所以在多线程环境下不允许值或者键为null。
  （5）Hashtable的散列地址计算与HashMap不同，HashMap使用位运算，Hashtable使用(hash & 0x7FFFFFFF) % length，先将hash值得大小控制在int类型的范围内再进行模除。
  （6）迭代器：支持用Iterator（fail-fast） 和Enumeration（fail-safe）两种。
  fail-fast：一种快速发现系统故障的机制。一旦发生异常，立即停止当前的操作，并上报给上层的系统来处理这些故障（这类似于一种检错纠错机制）。
  java.util包下的集合类都是fail-fast的，除了迭代器本身的方法 remove 可以改变集合的结构外，其他的因素如若改变了集合的结构，都将会抛出 ConcurrentModificationException 异常。删除或者添加元素将导致结构改变，而修改不会。
  集合中维护了一个modCount变量，用来记录该集合的删除或者添加操作的次数，在创建迭代器时会维护一个变量expectedModCount，并且值设为modCount的值，在迭代过程中如果expectedModCount与modCount不相同则向外抛出异常。需要注意的是迭代器的remove方法不会导致异常，因为在删除元素后它会重新设置expectedModCount=modCount。
  fail-safe：在故障发生之后会维持系统继续运行。
  当在迭代器遍历时添加或者删除元素是，fail-safe的集合类不会抛出异常。java.util.concurrent 包下的容器都是 fail-safe 的。
  fail-safe有两种情况，第一种是迭代器操作的是原始集合的拷贝，在迭代的过程中即使修改了原来的数据，迭代器中的元素也不会改变。
• ConcurrentHashMap：ConcurrentHashMap是线程安全的，相比于Hashtable，它的执行效率更高。ConcurrentHashMap 迭代器是弱一致性。ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。这样迭代器线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。
  jdk1.7和jdk1.8的ConcurrentHashMap的实现原理不相同。
  （1）JDK1.7：维护了一个Segment数组（默认大小为16），每个Segment又维护着一个HashEntry（类似于HashMap中的Entry）数组，HashEntry的value和next指针都是用volatile修饰的。Segment数组中的每个Segment对象分别使用一个锁（继承ReentrantLock），这样不同的Segment对象就可以实现并发操作。
  <1>put操作：根据hash值来找待插入节点属于哪个Segment，执行这个Segment的put方法，先执行tryLock()获取锁，若执行失败则执行scanAndLockForPut()自旋获取锁。
  <2>get操作：根据hash值来找待插入节点属于哪个Segment，然后再去这个Segment找对应的值，注意get操作不需要加锁
  <3>并发度：与Segment数组长度相同，默认为16
  
  
  （2）JDK1.8：JDK1.8放弃了原有的 Segment 分段锁，采用CAS（compare and swap，解决多线程并行情况下使用锁造成性能损耗的一种机制） + synchronized实现更加细粒度的锁，被加锁的部分只要Node数组中的头节点。
  <1>JDK1.8使用内置锁 synchronized替换 可重入锁 ReentrantLock。
  在 JDK1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。
  减少内存开销 。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承 AQS（jdk1.7中的使用volatile属性修饰每个节点和next指针） 来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。
  <2>put操作：如果对待插入节点的key的hash值得散列地址对应的链表为空则使用CAS方式添加，如果其他线程在扩容则参与扩容，如果以上条件都不满足则直接加锁并进行插入操作。
  <3>get操作：和HashMap差不多，不需要加锁。
  <4>并发度：与Node数组的长度相同，默认为16

 final V putVal(K key, V value, boolean onlyIfAbsent) {
 		//键和值不能为空
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node[] tab = table;;) {
            Node f; int n, i, fh;
            //数组为空初始化数组
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //对应数组的位置为空，使用CAS方法添加
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            //如果其他线程在扩容则一起参与扩容
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
            //否则对待插入元素对应的链表的表头节点进行加锁
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node p;
                            binCount = 2;
                            if ((p = ((TreeBin)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

• WeakHashMap（没有继承HashMap）：WeakHashMap中的Entry继承了WeakReference，因此Entry对象具有弱引用的性质（不论内存充足与否，Entry对象都有可能被回收）。
  （1）强引用、软引用、弱引用和虚引用
  <1>强引用：如果一个对象具有强引用，它就不会被垃圾回收器回收。即使当前内存空间不足，JVM也不会回收它，而是抛出 OutOfMemoryError 错误，使程序异常终止。比如String str = "hello"这时候str就是一个强引用。
  <2>软引用：内存足够的时候，软引用对象不会被回收，只有在内存不足时，系统则会回收软引用对象，如果回收了软引用对象之后仍然没有足够的内存，才会抛出内存溢出异常。
  <3>弱引用：如果一个对象具有弱引用，在垃圾回收时候，一旦发现弱引用对象，无论当前内存空间是否充足，都会将弱引用回收。
  <5>虚引用：如果一个对象具有虚引用，就相当于没有引用，在任何时候都有可能被回收。使用虚引用的目的就是为了得知对象被GC的时机，所以可以利用虚引用来进行销毁前的一些操作，比如说资源释放等。
  （2）实现机制：WeakHashMap中的Entry可能会被随时回收，如果被回收就需要删除对应的节点。jvm在回收弱引用对象时会将其添加到与之关联的一个队列中，WeakHashMap中维护了这样一个队列，WeakHashMap只需要查看哪些Entry节点被加入到que中并且从Hash表中删除这个Entry即可。

private final ReferenceQueue