前言
相信各位在遇到并發場景處理數據時都碰到過該選什么數據結構進行存儲的問題，本文就Java中常用的四種數據結構進行簡單的討論
正文
ConcurrentLinkedQueue
ConcurrentLinkedQueue 是 java.util.concurrent（JUC）包下的一個線程安全的隊列實現。基于非阻塞算法（Michael-Scott 非阻塞算法的一種變體），這意味著 ConcurrentLinkedQueue 不再使用傳統的鎖機制來保護數據安全，而是依靠底層原子的操作（如 CAS）來實現。
Collections.synchronizedList
JDK提供了一個Collections.synchronizedList靜態方法將一個非線程安全的List(并不僅限ArrayList)包裝為線程安全的List。迭代操作必須加鎖，可以使用synchronized關鍵字修飾;synchronized持有的監視器對象必須是synchronized (list),即包裝后的list,使用其他對象如synchronized (new Object())會使add,remove等方法與迭代方法使用的鎖不一致，無法實現完全的線程安全性。
CopyOnWriteArrayList
CopyOnWriteArrayList 是線程安全的，可以在多線程環境下使用。CopyOnWriteArrayList 遵循寫時復制的原則，每當對列表進行修改（例如添加、刪除或更改元素）時，都會創建列表的一個新副本，這個新副本會替換舊的列表，而對舊列表的所有讀取操作仍然可以繼續。
由于在修改時創建了新的副本，所以讀取操作不需要鎖定。這使得在多讀取者和少寫入者的情況下讀取操作非常高效。當然，由于每次寫操作都會創建一個新的數組副本，所以會增加存儲和時間的開銷。如果寫操作非常頻繁，性能會受到影響。
ConcurrentSkipListSet
ConcurrentSkipListSet是線程安全的有序的集合，適用于高并發的場景。
ConcurrentSkipListSet和TreeSet，它們雖然都是有序的集合。但是，第一，它們的線程安全機制不同，TreeSet是非線程安全的，而ConcurrentSkipListSet是線程安全的。第二，ConcurrentSkipListSet是通過ConcurrentSkipListMap實現的，而TreeSet是通過TreeMap實現的。
下面是四種數據結構在1000w數據量下進行插入操作，以及10w數據量的遍歷讀取的性能對比。（其中，由于CopyOnWriteArrayList插入性能較低，故只使用了10w數據量進行插入操作，但依然可見寫時復制帶來的性能消耗）
AtomicLong sum = new AtomicLong();
long start = 0;
long end = 0;
ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
List<Integer> list1 = Collections.synchronizedList(new ArrayList<>());
List<Integer> list2 = new CopyOnWriteArrayList<>();
ConcurrentSkipListSet<Integer> set = new ConcurrentSkipListSet<>();
start = new Date().getTime();
IntStream.rangeClosed(1, 10000000).parallel().forEach(queue::offer);// ConcurrentLinkedQueue
end = new Date().getTime();
System.out.println("ConcurrentLinkedQueue write cost time : " + (end - start) / 1000.0 + "秒");
start = new Date().getTime();
IntStream.rangeClosed(1, 10000000).parallel().forEach(list1::add);// synchronizedList
end = new Date().getTime();
System.out.println("synchronizedList write cost time : " + (end - start) / 1000.0 + "秒");
start = new Date().getTime();
IntStream.rangeClosed(1, 100000).parallel().forEach(list2::add);// CopyOnWriteArrayList
end = new Date().getTime();
System.out.println("CopyOnWriteArrayList write cost time : " + (end - start) / 1000.0 + "秒");
start = new Date().getTime();
IntStream.rangeClosed(1, 10000000).parallel().forEach(set::add);// ConcurrentSkipListSet
end = new Date().getTime();
System.out.println("ConcurrentSkipListSet write cost time : " + (end - start) / 1000.0 + "秒");
System.out.println("***************************");
start = new Date().getTime();
queue.stream().limit(100000).forEach(sum::addAndGet);// ConcurrentSkipListSet
end = new Date().getTime();
System.out.println("ConcurrentLinkedQueue read cost time : " + (end - start) / 1000.0 + "秒");
start = new Date().getTime();
queue.stream().limit(100000).forEach(sum::addAndGet);// ConcurrentSkipListSet
end = new Date().getTime();
System.out.println("synchronizedList read cost time : " + (end - start) / 1000.0 + "秒");
start = new Date().getTime();
queue.stream().limit(100000).forEach(sum::addAndGet);// ConcurrentSkipListSet
end = new Date().getTime();
System.out.println("CopyOnWriteArrayList read cost time : " + (end - start) / 1000.0 + "秒");
start = new Date().getTime();
queue.stream().limit(100000).forEach(sum::addAndGet);// ConcurrentSkipListSet
end = new Date().getTime();
System.out.println("ConcurrentSkipListSet read cost time : " + (end - start) / 1000.0 + "秒");
ConcurrentLinkedQueue write cost time : 2.339秒
synchronizedList write cost time : 4.125秒
CopyOnWriteArrayList write cost time : 4.828秒
ConcurrentSkipListSet write cost time : 0.214秒
***************************
ConcurrentLinkedQueue read cost time : 0.004秒
synchronizedList read cost time : 0.002秒
CopyOnWriteArrayList read cost time : 0.003秒
ConcurrentSkipListSet read cost time : 0.001秒
從上面的演示程序可以看到，基于跳表結構實現的 ConcurrentSkipListSet 具有最高的插入和遍歷讀取性能，所以，當我們的數據具有需要排序的需求時，我們可以使用該數據結構進行存儲。
而無界非阻塞隊列 ConcurrentLinkedQueue 具有第二高的插入性能，但遍歷讀取性能最低，故在多寫少讀的場景下我們可以選擇該數據結構，但由于其無界的特性，我們不應該無限制的進行插入操作，這樣會給內存帶來較大負擔，最好是我們對數據量有一個良好估計的情況下進行使用。
對于 CopyOnWriteArrayList ，我們可以看到它的插入性能和遍歷查詢性能懸殊較大，但正是因為犧牲了寫入性能，才能確保它在高并發下的安全性，故其只適合多讀少寫的場景。
最后，Collections.synchronizedList 的讀寫性能都是中間水平，那我們應該什么時候使用呢，當我們想要使用非線程安全的數組列表時（如ArrayList和LinkedList），我們就可以使用Collections.synchronizedList對其進行包裝，將其轉換為線程安全的列表。但還要注意的是，使用 Iterator 遍歷列表時，Collections.synchronizedList 可能發生錯誤。官方文檔給出的解決辦法是：我們在迭代器遍歷返回列表時，增加手動同步處理，即使用 synchronized 關鍵字鎖住這個 list。
需要注意的是，如果我們的數據是一個對象類型，且需要排序的字段有重復值，那我們就要慎重考慮 ConcurrentSkipListSet 了，（如數據庫查詢包含時間字段的場景），因為mysql5.7使用堆排序對排序性能進行了優化,故每次取的相同值的順序可能不一樣。而當我們使用跳表進行存儲時，在初始化時需要指定排序規則，即先對重復字段進行排序，再對不重復字段進行排序，顯然，這又是一個不穩定排序，兩次不穩定排序就可能導致分頁場景下，前后兩頁出現多個重復值的情況，這樣的結果顯然是不友好的。
浙公網安備 33010602011771號