撈撈面經

生產場景下什么時候用 ArrayList ，什么時候用 LinkedList

ArrayList 和 LinkedList 都是 Java 中常用的 List 實現，但是由于它們內部數據結構的不同，所以在不同的場景下，我們會選擇使用不同的List。

1. ArrayList：ArrayList 內部是使用動態數組來存儲數據的，所以它在隨機訪問（get和set操作）時有很好的性能，時間復雜度為O(1)。但是在列表中間插入和刪除元素時的性能較差，因為需要移動元素，時間復雜度為O(n)。所以，如果你的需求是大量的隨機訪問操作，少量的插入和刪除操作，那么 ArrayList 是一個好的選擇。
2. LinkedList：LinkedList 內部是使用雙向鏈表來存儲數據的，所以它在列表中間插入和刪除元素時有很好的性能，時間復雜度為 O(1)（需要提前獲取到節點的引用，否則查找節點的時間復雜度為 O(n)）。但是在隨機訪問時的性能較差，因為需要從頭部或者尾部開始遍歷，時間復雜度為 O(n)。所以，如果你的需求是大量的插入和刪除操作，少量的隨機訪問操作，那么 LinkedList 是一個好的選擇。

總的來說，我們需要根據實際的需求和使用場景來選擇合適的 List 實現。

創建線程的方式

1. 繼承Thread類：這是創建線程的最基本方法。我們可以創建一個新的類，繼承自 Thread 類，然后重寫其 run() 方法，將我們的任務代碼寫在 run() 方法中。然后創建該類的對象并調用其 start() 方法來啟動線程。
2. 實現Runnable接口：我們也可以創建一個新的類，實現 Runnable 接口，然后將我們的任務代碼寫在 run() 方法中。然后創建該類的對象，將其作為參數傳遞給 Thread 類的構造器，創建 Thread 類的對象并調用其 start() 方法來啟動線程。
3. 實現Callable接口和FutureTask類：Callable 接口與 Runnable 接口類似，但是它可以返回一個結果，或者拋出一個異常。我們可以創建一個新的類，實現 Callable 接口，然后將我們的任務代碼寫在 call() 方法中。然后創建該類的對象，將其作為參數傳遞給FutureTask 類的構造器，創建 FutureTask 類的對象。最后，將FutureTask類的對象作為參數傳遞給 Thread 類的構造器，創建Thread 類的對象并調用其 start() 方法來啟動線程。
4. 使用線程池：Java 提供了線程池 API（Executor框架），我們可以通過 Executors 類的一些靜態工廠方法來創建線程池，然后調用其 execute() 或 submit() 方法來啟動線程。線程池可以有效地管理和控制線程，避免大量線程的創建和銷毀帶來的性能開銷。

以上四種方式，前兩種是最基本的創建線程的方式，但是在實際開發中，我們通常會選擇使用線程池，因為它可以提供更好的性能和更易于管理的線程生命周期。

在并發量特別高的情況下是使用 synchronized 還是 ReentrantLock

在并發量特別高的情況下，一般推薦使用 ReentrantLock，原因如下：

1. 更高的性能：在Java 1.6之前，synchronized 的性能一般比 ReentrantLock 差一些。雖然在 Java 1.6 及之后的版本中，synchronized進行了一些優化，如偏向鎖、輕量級鎖等，但在高并發情況下，ReentrantLock 的性能通常會優于 synchronized。
2. 更大的靈活性：ReentrantLock 比 synchronized 有更多的功能。例如，ReentrantLock 可以實現公平鎖和非公平鎖（synchronized只能實現非公平鎖）；ReentrantLock 提供了一個 Condition 類，可以分組喚醒需要喚醒的線程（synchronized 要么隨機喚醒一個線程，要么喚醒所有線程）；ReentrantLock 提供了 tryLock 方法，可以嘗試獲取鎖，如果獲取不到立即返回，不會像synchronized 那樣阻塞。
3. 更好的可控制性：ReentrantLock可以中斷等待鎖的線程（synchronized無法響應中斷），也可以獲取等待鎖的線程列表，這在調試并發問題時非常有用。

但是，雖然 ReentrantLock 在功能上比 synchronized 更強大，但也更復雜，使用不當容易造成死鎖。而 synchronized 由 JVM 直接支持，使用更簡單，不容易出錯。所以，在并發量不高，對性能要求不高的情況下，也可以考慮使用 synchronized。

說一下 ConcurrentHashMap 中并發安全的實現

ConcurrentHashMap 在 Java 1.7 和 Java 1.8 中的實現方式有所不同，但它們的共同目標都是提供高效的并發更新操作。下面我將分別介紹這兩個版本的實現方式。

1. Java 1.7：在Java 1.7中，ConcurrentHashMap 內部使用一個 Segment 數組來存儲數據。每個Segment 對象包含一個 HashEntry 數組，每個 HashEntry 對象就是一個鍵值對。Segment 對象是可鎖定的，每個Segment對象都可以看作是一個獨立的 HashMap。在更新數據時，只需要鎖定相關 Segment 對象，而不需要鎖定整個HashMap，這樣就可以實現真正的并發更新。Segment 的數量默認為 16，這意味著 ConcurrentHashMap 最多支持 16 個線程的并發更新。
2. Java 1.8：在 Java 1.8 中，ConcurrentHashMap 的實現方式進行了改進。它取消了 Segment 數組，直接使用 Node 數組來存儲數據。每個Node對象就是一個鍵值對。在更新數據時，使用 CAS 操作和 synchronized 來保證并發安全。具體來說，如果更新操作發生在鏈表的頭節點，那么使用 CAS 操作；如果發生在鏈表的其他位置，或者發生在紅黑樹節點，那么使用synchronized。這樣，ConcurrentHashMap可以支持更多線程的并發更新。

總的來說，ConcurrentHashMap 通過分段鎖（Java 1.7）或 CAS+synchronized（Java 1.8）的方式，實現了高效的并發更新操作，從而保證了并發安全

你說高并發下 ReentrantLock 性能比 synchronized 高，那為什么 ConcurrentHashMap 在 JDK 1.7 中要用 ReentrantLock，而 ConcurrentHashMap 在 JDK 1.8 要用 Synchronized

這是一個很好的問題。首先，我們需要明確一點，雖然 ReentrantLock 在某些情況下的性能優于synchronized，但這并不意味著在所有情況下都是這樣。

實際上，synchronized 在JDK 1.6 及以后的版本中已經進行了大量的優化，例如偏向鎖、輕量級鎖等，使得在競爭不激烈的情況下，synchronized 的性能已經非常接近甚至超過 ReentrantLock。

在 JDK 1.7的 ConcurrentHashMap中，使用 ReentrantLock（Segment）是為了實現分段鎖的概念，即將數據分成多個段，每個段獨立加鎖，從而實現真正的并發更新。這種設計在當時是非常先進和高效的。

然而，在 JDK 1.8 的 ConcurrentHashMap 中，為了進一步提高并發性能，引入了更復雜的數據結構（如紅黑樹）和更高效的并發控制機制（如CAS操作）。在這種情況下，使用 synchronized 比 ReentrantLock 更加簡單和高效。首先，synchronized 可以直接與JVM進行交互，無需用戶手動釋放鎖，減少了出錯的可能性。

其次，synchronized 在 JDK 1.6及以后的版本中已經進行了大量的優化，性能已經非常接近 ReentrantLock。最后，synchronized 可以與其他 JVM 特性（如偏向鎖、輕量級鎖、鎖消除、鎖粗化等）更好地配合，進一步提高性能。

總的來說，選擇使用 ReentrantLock 還是 synchronized，需要根據具體的需求和使用場景來決定。在 JDK 1.8 的 ConcurrentHashMap中，使用 synchronized 是一種更加合理和高效的選擇。

有哪些并發安全的實現方式

1. synchronized關鍵字：這是最基本的并發安全實現方式，它可以保證同一時刻最多只有一個線程執行該段代碼，從而保證了類的實例狀態的線程安全。
2. volatile關鍵字：volatile 關鍵字可以保證變量的可見性和禁止指令重排序，但不能保證復合操作的原子性。它通常用于標記狀態變量。
3. Lock接口和其實現類：例如ReentrantLock、ReentrantReadWriteLock等。相比于synchronized，Lock接口提供了更強大的功能，例如嘗試獲取鎖、可中斷的獲取鎖以及獲取公平鎖等。
4. 原子類：例如 AtomicInteger、AtomicLong、AtomicReference 等。這些類通過 CAS（Compare and Swap）操作實現了原子性更新。
5. 并發集合：Java 提供了一些線程安全的集合類，例如 ConcurrentHashMap、CopyOnWriteArrayList等。
6. ThreadLocal類：ThreadLocal 可以為每個線程創建一個單獨的變量副本，每個線程都只能操作自己的副本，從而實現了線程隔離，保證了線程安全。
7. Semaphore信號量：Semaphore 可以控制同時訪問特定資源的線程數量，通過acquire()獲取一個許可，如果沒有就等待，通過release()釋放一個許可。
8. CountDownLatch：CountDownLatch允許一個或多個線程等待其他線程完成操作。
9. CyclicBarrier：CyclicBarrier 讓一組線程到達一個屏障（也可以叫同步點）時被阻塞，直到最后一個線程到達屏障時，屏障才會開門，所有被阻塞的線程才會繼續運行。
10. Phaser：Phaser 是 JDK 1.7引入的一個用于解決控制多個線程分階段共同完成任務的類。

以上就是 Java 中常見的一些并發安全的實現方式。

不用 ThreadLocal 你會想用什么方式存用戶信息

如果不使用 ThreadLocal 來存儲用戶信息，我會考慮以下幾種方式：

1. 參數傳遞：這是最直接的方式，將用戶信息作為方法的參數傳遞。這種方式的優點是簡單直接，不依賴任何特定的技術。缺點是如果調用鏈很長，那么需要在很多方法之間傳遞用戶信息，可能會使代碼變得復雜。
2. 全局變量：可以將用戶信息存儲在全局變量中。但是，這種方式需要注意并發控制和內存泄漏問題。如果是Web應用，可以考慮將用戶信息存儲在 Session 或 Cookie 中。
3. 數據庫或緩存：可以將用戶信息存儲在數據庫或緩存中，如 Redis。這種方式的優點是可以持久化用戶信息，適合存儲大量的用戶信息。缺點是訪問數據庫或緩存的速度比訪問內存慢，可能會影響性能。
4. 上下文對象：可以創建一個上下文對象，將用戶信息存儲在上下文對象中。然后將上下文對象傳遞給需要使用用戶信息的方法。這種方式的優點是可以避免在方法之間傳遞大量的參數。缺點是需要手動管理上下文對象的生命周期。

以上就是我考慮的幾種存儲用戶信息的方式，具體使用哪種方式，需要根據實際的需求和場景來決定。

有千萬級數據，如何判斷一個整數是否存在

對于千萬級的數據，如果要判斷一個整數是否存在，可以考慮以下幾種方法：

1. 哈希表：哈希表（如 Java 中的 HashSet 或 HashMap）可以在 O(1) 的時間復雜度內判斷一個元素是否存在。但是，哈希表需要大量的內存空間來存儲數據和哈希表本身。如果內存空間有限，那么這可能不是一個好的選擇。
2. 布隆過濾器：布隆過濾器是一種空間效率極高的隨機數據結構，它利用位數組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是它存在一定的誤識別率和刪除困難。
3. 位圖：如果整數的范圍不大，例如都是非負整數，那么可以使用位圖（BitSet）來判斷一個整數是否存在。位圖的每一位代表一個整數，如果整數存在，那么對應的位就置為 1。位圖需要的內存空間遠小于哈希表，但是如果整數的范圍非常大，那么位圖可能就不適用了。
4. 數據庫：如果數據已經存儲在數據庫中，那么可以直接使用 SQL 查詢來判斷一個整數是否存在。這種方法的效率取決于數據庫的性能和數據的索引情況。
5. 二分查找：如果數據是有序的，那么可以使用二分查找來判斷一個整數是否存在。二分查找的時間復雜度是 O(log n)，但是它需要數據是有序的。

以上就是判斷一個整數是否存在的幾種方法，具體使用哪種方法，需要根據實際的需求和場景來決定。

如何理解：布隆過濾器說某個元素存在，則大概率在。布隆過濾器說某個元素不在，則一定不在

布隆過濾器是一種概率型的數據結構，它的主要特點是高效地判斷一個元素是否在一個集合中。它的基本原理是通過多個哈希函數將元素映射到一個位數組中。當查詢一個元素是否存在時，通過同樣的哈希函數計算出位數組中的位置，如果所有的位置都是1，那么就認為元素可能存在；如果有任何一個位置是 0，那么就認為元素一定不存在。

這里的 "可能存在”  和  “一定不存在” 是因為布隆過濾器的特性決定的：

1. 當布隆過濾器說某個元素存在時，實際上可能會出現誤判的情況。因為不同的元素可能會被哈希到位數組的同一位置，這就可能出現一個元素實際上不存在，但是因為其哈希位置被其他元素占用，所以布隆過濾器判斷它存在。這就是所謂的“假陽性”。
2. 當布隆過濾器說某個元素不存在時，那么這個元素一定不存在。因為如果一個元素存在，那么它的哈希位置一定會被設置為1。如果布隆過濾器說某個元素不存在，那么說明至少有一個哈希位置是 0，那么這個元素一定不存在。這就是所謂的“真陰性”。

因此，布隆過濾器的一個重要特性就是，它可能會誤判一個不存在的元素為存在（假陽性），但是絕不會誤判一個存在的元素為不存在（真陰性）。這就是“布隆過濾器說某個元素存在，則大概率在。布隆過濾器說某個元素不在，則一定不在”的含義。

千萬級數據用布隆過濾器初始化的時候 redis 太慢了，有沒有什么好方法

對于千萬級的數據，如果直接使用Redis來初始化布隆過濾器確實可能會比較慢。這是因為Redis的操作都是網絡IO操作，相比于內存操作，網絡IO的速度要慢很多。以下是一些可能的優化方法：

1. 批量操作：Redis支持批量操作，可以一次性發送多個命令，然后一次性接收所有的結果。這樣可以減少網絡IO的次數，提高效率。
2. 管道操作：Redis還支持管道操作，可以一次性發送多個命令，不需要等待上一個命令的結果就可以發送下一個命令。這樣可以進一步減少網絡IO的次數。
3. 多線程或多進程：可以使用多線程或多進程來并行初始化布隆過濾器。每個線程或進程負責一部分數據，這樣可以充分利用多核CPU，提高效率。
4. 使用更快的存儲：如果條件允許，可以考慮使用更快的存儲，例如SSD硬盤，或者直接在內存中初始化布隆過濾器。
5. 預熱數據：如果數據不經常變動，可以考慮預先計算好布隆過濾器的狀態，然后保存在文件或數據庫中。需要使用時，直接加載預先計算好的狀態，這樣可以避免實時初始化布隆過濾器。

以上就是一些可能的優化方法，具體使用哪種方法，需要根據實際的需求和場景來決定。

多線程間如何傳值

多線程間傳遞值主要有以下幾種方式：

1. 共享內存：多個線程可以共享同一個進程的內存空間，因此可以通過修改內存中的變量來傳遞值。但是，需要注意的是，多個線程同時修改同一個變量可能會導致數據不一致的問題，因此通常需要使用鎖或其他同步機制來保證數據的一致性。
2. 線程局部變量：例如 Java 中的 ThreadLocal，可以為每個線程創建一個獨立的變量副本，每個線程只能訪問和修改自己的副本，不會影響其他線程的副本。
3. 通過隊列傳遞：可以使用線程安全的隊列（如 Java 中的 BlockingQueue ）來傳遞值。一個線程將值放入隊列，另一個線程從隊列中取出值。
4. 通過管道傳遞：某些編程語言（如 Python ）支持使用管道（Pipe）來傳遞值。一個線程將值寫入管道，另一個線程從管道中讀取值。
5. 通過Future和Callable：在 Java 中，可以使用 Future 和 Callable 來在多線程間傳遞值。Callable 是一個可以返回值的任務，Future 可以用來獲取 Callable 任務的返回值。

以上就是多線程間傳遞值的幾種方式，具體使用哪種方式，需要根據實際的需求和場景來決定。

如何設計登陸黑名單

設計登錄黑名單的主要目的是防止惡意用戶或者機器人進行暴力破解或者惡意登錄。以下是一種可能的設計方案：

1. 記錄登錄失敗次數：對每個用戶或者 IP 地址，記錄其登錄失敗的次數。如果在一定時間內登錄失敗次數超過某個閾值，那么就將該用戶或者 IP 地址加入黑名單。
2. 設置黑名單有效期：黑名單不應該永久有效，否則可能會誤傷正常用戶?？梢栽O置一個有效期，例如 24 小時。超過有效期后，自動將用戶或者 IP 地址從黑名單中移除。
3. 使用布隆過濾器：為了高效地判斷一個用戶或者 IP 地址是否在黑名單中，可以使用布隆過濾器。布隆過濾器可以在近似 O(1) 的時間復雜度內判斷一個元素是否存在。
4. 黑名單同步：如果系統是分布式的，那么需要考慮黑名單的同步問題。可以使用消息隊列或者Redis等工具來同步黑名單。
5. 提供解封接口：對于誤傷的正常用戶，應該提供一個解封的接口或者方式。例如，可以通過驗證郵箱或者手機短信來解封。
6. 記錄黑名單日志：對于被加入黑名單的用戶或者 IP 地址，應該記錄詳細的日志，包括被加入黑名單的時間，原因，以及登錄失敗的詳細信息。這對于后期的審計和分析都是非常有幫助的。

以上就是設計登錄黑名單的一種可能的方案，具體的設計可能還需要根據實際的需求和場景來調整。