Java面經

基礎

interface, abstract class區別

https://blog.csdn.net/b271737818/article/details/3950245

集合

說一下數組和鍊表的區別?它們分別使用於什麼場合?

數組和鍊表。數組的特點是：尋址容易，插入和刪除困難；而鍊表的特點是：尋址困難，插入和刪除容易。

HashMap衝突解決

Java 8 之前：HashMap和其他基於map的類都是通過鏈地址法解決衝突，它們使用單向鍊表來存儲相同索引值的元素。在最壞的情況下，這種方式會將HashMap的get方法的性能從O(1)降低到O(n)。

Java 8中：為了解決在頻繁衝突時hashmap性能降低的問題，Java 8中使用平衡樹來替代鍊表存儲衝突的元素。這意味着我們可以將最壞情況下的性能從O(n)提高到O(logn)。 在Java 8中使用常量TREEIFY_THRESHOLD來控制是否切換到平衡樹來存儲。目前，這個常量值是8，這意味着當有超過8個元素的索引一樣時，HashMap會使用樹來存儲它們。

為什麼產生衝突： HashMap中調用hashCode()方法來計算hashCode。 由於在Java中兩個不同的對象可能有一樣的hashCode,所以不同的鍵可能有一樣hashCode，從而導致衝突的產生。

hashmap put get實現原理（JDK1.8後）

• put

1. 對key的hashCode()做hash，然後再計算index; ----! 通過 array大小&hashcode 算出index, get時也是同樣==先算hashcode, 有衝突後再equals
2. 如果沒碰撞直接放到bucket里；
3. 如果碰撞了，以鍊表的形式存在buckets後；
4. 如果碰撞導致鍊表過長(大於等於TREEIFY_THRESHOLD)，就把鍊表轉換成紅黑樹；
5. 如果節點已經存在就替換old value(保證key的唯一性)
6. 如果bucket滿了(超過load factor*current capacity)，就要resize。
   

• get

1. bucket里的第一個節點，直接命中；
2. 如果有衝突，則通過key.equals(k)去查找對應的entry
   1. 若為樹，則在樹中通過key.equals(k)查找，O(logn)；
   2. 若為鍊表，則在鍊表中通過key.equals(k)查找，O(n)。

• put

public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算index，并对null做处理
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 节点存在
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 该链为树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 写入
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 超过load factor*current capacity，resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

• get

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 直接命中
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 未命中
        if ((e = first.next) != null) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

JVM

jvm內存模型

運行時內存模型：分為線程私有和共享數據區兩大類

• 線程私有的數據區：程序計數器、虛擬機棧、本地方法區
• 所有線程共享的數據區：Java堆、方法區，在方法區內有一個常量池。

• 

  運行時內存模型

數據庫

三範式

1. 第一範式：要求有主鍵，並且要求每一個字段原子性不可再分
2. 第二範式：要求所有非主鍵字段完全依賴主鍵，不能產生部分依賴
3. 第三範式：所有非主鍵字段和主鍵字段之間不能產生傳遞依賴

事務隔離級別

✔️表示會發生， ❌表示不會發生

隔離級別	髒讀(Dirty Read)	不可重複讀(NonRepeatable Read)	幻讀(Phantom Read)
未提交讀(Read uncommitted)	✔️	✔️	✔️
已提交讀(Read committed)	❌	✔️	✔️
可重複讀(Repeatable read)	❌	❌	✔️
可串行化(Serializable)	❌	❌	❌

• 未提交讀(Read Uncommitted)： 一個事務可以讀取到另一個事務未提交的修改。

• 提交讀(Read Committed)： 一個事務只能讀取另一個事務已經提交的修改。

• 可重複讀(Repeated Read)： 同一個事務中多次讀取相同的數據返回的結果是一樣的。因為：在事務執行期間會鎖定該事務以任何方式引用的所有行。這是MySQL中InnoDB默認的隔離級別。

• 可串行化(Serializable)： 事務串行執行。每次讀都需要獲得表級共享鎖，讀寫相互都會阻塞

1. 不可重複讀和幻讀的區別

如果使用锁机制来实现这两种隔离级别，在可重复读中，该sql第一次读取到数据后，就将这些数据加锁，其它事务无法修改这些数据，就可以实现可重复读了。但这种方法却无法锁住insert的数据，所以当事务A先前读取了数据，或者修改了全部数据，事务B还是可以insert数据提交，这时事务A就会发现莫名其妙多了一条之前没有的数据，这就是幻读，不能通过行锁来避免。需要Serializable隔离级别 ，读用读锁，写用写锁，读锁和写锁互斥，这么做可以有效的避免幻读、不可重复读、脏读等问题，但会极大的降低数据库的并发能力。

所以说不可重复读和幻读最大的区别，就在于如何通过锁机制来解决他们产生的问题。

MySQL、ORACLE、PostgreSQL等成熟的数据库，出于性能考虑，都是使用了以乐观锁为理论基础的MVCC（多版本并发控制）来避免这两种问题。

算法

swap(a, b) 深究 值拷貝，引用傳遞

public class Main {

    // 反射
    public void swap(Integer a, Integer b) {
        int temp = a;

        try {
            Class clazz = a.getClass();
            Field value = clazz.getDeclaredField("value");
            value.setAccessible(true);
            value.setInt(a, b);
            value.setInt(b, temp);
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        /* Integer 换成 int a = 1, 不行！！！*/
        Integer a = 1;
        Integer b = 2;
        main.swap(a, b);
        System.out.println("a = " + a + ", b= " + b);
    }
}