本文主要針對開發(fā)中常用的數(shù)據(jù)結(jié)構(gòu)做個總結(jié)玄糟，主要還是源碼原理相關(guān)的內(nèi)容巴比，尤其是面試需要復(fù)習的同學可以多研究一下闷哆。
線性表
ArrayList塔沃、LinkedList
ArrayList
基于動態(tài)數(shù)組實現(xiàn)的锰提，初始化的時候沒有指定大小的話，默認容量是10芳悲，添加元素的時候會判斷是否需要對數(shù)組擴容立肘，每次擴容大小為1.5倍，如果擴容1.5倍不夠就用目標的size作為擴容后的容量,擴容是通過數(shù)組的拷貝實現(xiàn)的名扛，這是一個非常耗性能的操作谅年，所以如果可以確定大概的數(shù)據(jù)量，可以直接指定list大小肮韧。由于list是基于數(shù)組實現(xiàn)的融蹂，數(shù)組的特點是在堆內(nèi)存中用連續(xù)的內(nèi)存空間來存儲，所以訪問／查找效率比較高弄企，而在列表中間添加／刪除元素的話超燃，需要數(shù)組拷貝來完成，所以添加／刪除效率會比較低拘领，如果是在末尾操作的話意乓，效率沒什么影響，因為不需要數(shù)組拷貝约素，時間復(fù)雜度為O(1)届良。
ArrayList的時間復(fù)雜度 - Java那些事兒專欄
【你碰到過嗎】如果面試官問你ArrayList和LinkedList有什么區(qū)別笆凌？
數(shù)據(jù)結(jié)構(gòu)——數(shù)組及簡介時間復(fù)雜度
LinkedList
通過一個雙向鏈表來實現(xiàn)，大概結(jié)構(gòu)如下：
雙向鏈表的數(shù)據(jù)存儲單元是節(jié)點（前驅(qū)節(jié)點士葫、后繼節(jié)點乞而、本節(jié)點數(shù)據(jù)），它不需要像數(shù)組那樣知道數(shù)據(jù)大小慢显，在內(nèi)存存儲上不需要連續(xù)的內(nèi)存空間爪模，雙向鏈表通過指針來指向前后數(shù)據(jù)；它插入／刪除數(shù)據(jù)是靠改變指針指向來實現(xiàn)荚藻。鏈表結(jié)構(gòu)決定了它沒有大小限制屋灌，也不會有什么初始化值和擴容。
插入／刪除效率
LinkedList中定義了頭部和尾部2個Node鞋喇，如果插入／刪除的位置是頭部／尾部的話声滥，時間復(fù)雜度是O(1)眉撵；如果插入／刪除位置是在中間的話侦香，它會先做一次二分法查找，判斷索引是在前半段還是在后半段纽疟，從短的那頭開始遍歷罐韩，找到之后，新建一個節(jié)點污朽，建立新的前置節(jié)點和后置節(jié)點的關(guān)系散吵，時間復(fù)雜度最大是O (n/2)；
訪問效率
也是同樣的查找方法蟆肆，時間復(fù)雜度也是最大是O (n/2)矾睦。
Deque
LinkedList實現(xiàn)了Deque接口，這個接口同時實現(xiàn)了棧和隊列的功能炎功，所以枚冗，LinkedList還可以當作棧或者隊列來使用蛇损。
Java LinkedList的實現(xiàn)原理圖文詳解
Java集合系列之三：LinkedList底層原理
ArrayList 和LinkedList簡單對比
- ArrayList是基于動態(tài)數(shù)組實現(xiàn)的赁温，而LinkedList是雙向鏈表；
- 堆內(nèi)存存儲上淤齐，ArrayList連續(xù)的內(nèi)存空間股囊，LinkedList不需要；
- ArrayList隨機訪問比較快更啄，因為可以通過
首地址+偏移量直接計算出我想訪問的第x個元素在內(nèi)存中的位置,用時間復(fù)雜度來表示的話是O(1),而LinkedList是o（n／2）稚疹； - 插入／刪除來看，ArrayList效率不如LinkedList祭务，因為前者要做數(shù)組擴容和拷貝（耗性能）贫堰，后者只是相關(guān)節(jié)點前后指針的移動穆壕；
- 二者都是線程不安全
LinkedList真的比ArrayList添加／刪除快嗎？如何判斷二者的使用場景其屏？
注：這里的快和慢是相對的喇勋。并不是LinkedList的插入和刪除就一定比ArrayList快。明白其快慢的本質(zhì)：ArrayList快在定位偎行，慢在數(shù)組復(fù)制川背。LinkedList慢在定位，快在指針修改蛤袒。
Java基礎(chǔ)篇(四):ArrayList和LinkedList內(nèi)部實現(xiàn)熄云、區(qū)別、使用場景
線程安全的 CopyOnWriteArrayList
從源碼分析可以看出ArrayList不是線程安全的妙真，要變成線程安全方法很多缴允，比如說替換成Vector，再或者是使用 Collections珍德，將 ArrayList 包裝成一個線程安全的類练般。不過這兩種方法也有很大的缺點，那就是他們使用的都是獨占鎖锈候，獨占式鎖在同一時刻只有一個線程能夠獲取薄料，效率太低。于是CopyOnWriteArrayList 應(yīng)用而生了泵琳。
(1) 摄职、獨占鎖效率低：采用讀寫分離思想解決
讀操作不加鎖，所有線程都不會阻塞获列。寫操作加鎖谷市，線程會阻塞。
(2) 击孩、寫線程獲取到鎖迫悠，其他線程包括讀線程阻塞
但是這時候又出現(xiàn)了另外一個問題了：寫線程獲取到鎖之后，其他的讀線程會陷入阻塞溯壶。
(3)及皂、解決思路：CopyOnWrite思想
當我們往一個容器添加元素的時候，不直接往當前容器添加且改，而是先將當前容器進行 Copy验烧，復(fù)制出一個新的容器，然后新的容器里添加元素又跛，添加完元素之后碍拆，再將原容器的引用指向新的容器。簡單來說就是更新數(shù)據(jù)的時候做一次數(shù)組拷貝，對拷貝的新對象操作完了感混，再讓原來的容器對象指向這個新對象端幼。
(4)、優(yōu)點
不會存在讀數(shù)據(jù)阻塞線程的情況弧满，適合多線程中讀多寫少的場景
(5)婆跑、缺點
- 數(shù)據(jù)不一致的問題。如果寫線程還沒來得及寫會內(nèi)存庭呜，其他的線程就會讀到了臟數(shù)據(jù)
- 內(nèi)存消耗大滑进。由于在寫的時候會做數(shù)組拷貝，當2個數(shù)組內(nèi)容都比較多的時候募谎，內(nèi)存占用就比較高扶关。
CopyOnWriteArrayList的核心思想是利用高并發(fā)往往是讀多寫少的特性，對讀操作不加鎖数冬，對寫操作节槐，先復(fù)制一份新的集合，在新的集合上面修改拐纱，然后將新集合賦值給舊的引用铜异，并通過volatile 保證其可見性，當然寫操作的鎖是必不可少的了戳玫。
Java8 CopyOnWriteArrayList 源碼分析
Copy-On-Write容器與CopyOnWriteArrayList理解
多線程進階（三）-- JUC中CopyOnWriteArrayList()解析及為什么要復(fù)制
java并發(fā)(4)深入理解volatile
窺探真相：volatile 可見性實現(xiàn)原理
java高并發(fā)熙掺，volatil關(guān)鍵字未斑，CAS原理咕宿，AQS原理
華為架構(gòu)師兩小時講解面試重災(zāi)區(qū)——CAS底層原理分析
棧、隊列
Stack
注意蜡秽，這里說的棧是指java.util.Stack府阀。棧是線性表的一種，底層是通過數(shù)組來實現(xiàn)的芽突，它只能在棧頂操作數(shù)據(jù)试浙，數(shù)據(jù)的進出方式是先進后出（FILO）。繼承于Vector寞蚌，是線程安全的田巴。
Queue
注意，這里說的棧是指java.util. Queue挟秤。隊列也是線性表的一種壹哺，它是從隊尾插入數(shù)據(jù)，從隊列頭部取數(shù)據(jù)艘刚，數(shù)據(jù)進出方式先進先出（FIFO）管宵。Queue是一個接口，所以隊列的實現(xiàn)由其他實現(xiàn)類完成，比如LinkedList箩朴，是線程不安全的岗喉。
Deque
雙端隊列，繼承于java.util.Queue炸庞，也是一個接口钱床，同時具備中棧和隊列的特點，它可以從兩端分別進入插入埠居，刪除操作诞丽。我們熟知的LinkedList就實現(xiàn)了Deque。
HashMap拐格、LinkedHashMap僧免、ConcurrentHashMap
HashMap
數(shù)據(jù)結(jié)構(gòu)是：數(shù)組+鏈表（jdk1.8引入了紅黑樹）的形式來存放鍵值對的。首先對key做hash()運算來確定元素在數(shù)組中的位置捏浊，但是不同的key做hash運算得到的值可能是一樣的懂衩，如果不同的key計算之后得到的索引相同，那么在這個位置會創(chuàng)建一個單向鏈表來存儲相同索引的元素金踪，在jdk1.8中浊洞，如果這個鏈表的元素超過8個，會引入紅黑樹來提升效率胡岔，說HashMap是兼具數(shù)組訪問快和鏈表添加／刪除快的優(yōu)點法希，由于HashMap 是根據(jù)key的hash值在數(shù)組上隨機分布的，所以hashmap是無序的靶瘸。
hashmap之所以要設(shè)置長度必須為2的n次方苫亦，是因為這樣可以減少碰撞，使元素分散的更均勻怨咪。
int index= hash & (length- 1)
具體來說屋剑，當length=2^n，那么length-1轉(zhuǎn)化為2進制數(shù)诗眨，低位的每一位都是1唉匾，這樣在做與運算的時候，index就能分散到更多的位置匠楚，否則的話就有一些位置永遠都不會存儲元素巍膘。當然如果用取模運算就不必有這個限制，hash % (length- 1)芋簿，但是這樣呢運算效率很低峡懈。
hashmap的加載因子為什么是0.75f？
因為過小的話益咬，會造成擴容頻繁逮诲；過大的話會產(chǎn)生更多碰撞
搞懂 Java equals 和 hashCode 方法
HashMap擾動函數(shù)解讀
JDK 源碼中 HashMap 的 hash 方法原理是什么帜平？
搞懂 Java HashMap 源碼
崩潰了,一個HashMap跟面試官扯了半個小時
HashMap的長度為什么必須是2的N次方
LinkedHashMap
LinkedHashMap繼承于HashMap，它是在HashMap的基礎(chǔ)上通過雙向鏈表維護元素節(jié)點間的順序梅鹦，默認是按插入順序排序裆甩，原理是把新加入的元素放在雙向列表的尾部；如果是訪問順序排序的話齐唆，訪問元素的時候會把元素放在鏈表尾部嗤栓，這樣就可以維護訪問順序，最常見的應(yīng)用就是LRU算法箍邮。
面試必備：LinkedHashMap源碼解析（JDK8）
搞懂 Java LinkedHashMap 源碼
LinkedHashMap為什么是有序的茉帅？
ConcurrentHashMap
ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。一個ConcurrentHashMap里包含一個Segment數(shù)組锭弊，Segment的結(jié)構(gòu)和HashMap類似堪澎，是一種數(shù)組和鏈表結(jié)構(gòu)， 一個Segment里包含一個HashEntry數(shù)組味滞，每個HashEntry是一個鏈表結(jié)構(gòu)的元素樱蛤，每個Segment守護者一個HashEntry數(shù)組里的元素,當對HashEntry數(shù)組的數(shù)據(jù)進行修改時，必須首先獲得它對應(yīng)的Segment鎖剑鞍。所以ConcurrentHashMap是線程安全的洪橘，且在性能上不輸HashMap榆芦。
ConcurrentHashMap基于JDK1.8源碼剖析
Java集合-ConcurrentHashMap工作原理和實現(xiàn)JDK8
Java（Android）數(shù)據(jù)結(jié)構(gòu)匯總（四）-- Map（上）
HashMap? ConcurrentHashMap? 相信看完這篇沒人能難住你！
Set
首先Set是一個接口壤追，它的實現(xiàn)類主要有HashSet枚钓、TreeSet款票，它的特點是：不允許存儲的元素重復(fù)杂抽。
HashSet
HashSet內(nèi)部是使用HashMap來實現(xiàn)的元素存儲自点，特點：無序、不允許元素重復(fù)田度。利用了hashmap的key不會重復(fù)的特性來實現(xiàn)元素的唯一性妒御。
TreeSet
使用的TreeMap來實現(xiàn)的元素存儲解愤。同樣是以存儲的元素作為TreeMap的key镇饺，所以元素也是不能重復(fù)的。另外因為TreeMap的key是有序的送讲，所以TreeSet是一個有序的集合奸笤。
Java（Android）數(shù)據(jù)結(jié)構(gòu)匯總（二）-- Set（上）
樹形結(jié)構(gòu)Tree
深度優(yōu)先遍歷：
對每一個可能的分支路徑深入到不能再深入為止，而且每個結(jié)點只能訪問一次哼鬓。而二叉樹的深度優(yōu)先遍歷分為先序遍歷监右，中序遍歷和后續(xù)遍歷。
先序遍歷：先訪問根异希，在訪問左子樹健盒，最后訪問右子樹，總結(jié)就是“根左右”；
中序遍歷：先訪問左子樹扣癣，再訪問根惰帽，最后訪問右子樹，總結(jié)就是“左根右”父虑；
后序遍歷：先訪問左子樹该酗，再訪問右子樹，最后訪問根士嚎，總結(jié)就是“左右根”呜魄；
通常采用遞歸的方式實現(xiàn)遍歷，非遞歸方式需要結(jié)合棧（后進先出）的特點實現(xiàn)莱衩。
廣度優(yōu)先遍歷：
又叫層次遍歷爵嗅，從上往下對每一層依次訪問，在每一層中笨蚁，從左往右（也可以從右往左）訪問結(jié)點操骡，訪問完一層就進入下一層，直到?jīng)]有結(jié)點可以訪問為止赚窃。
廣度優(yōu)先遍歷的非遞歸的通用做法是采用隊列（先入先出）册招。
二叉查找樹
二叉查找樹（Binary Search Tree），或者是一顆空樹勒极，或者是具有下列性質(zhì)的二叉樹：
- 1是掰、若它的左子樹不空，則其左子樹上的所有結(jié)點的值均小于它根結(jié)點的值辱匿；
- 2键痛、若它的右子樹不空，則其右子樹上的所有結(jié)點的值均大于它根結(jié)點的值匾七；
- 3絮短、它的左、右子樹也分別為二叉查找樹昨忆。
樹形結(jié)構(gòu)就是利用二叉查找樹這種特性來實現(xiàn)快速查詢丁频，效率上和線性表的二分查找差不多。
深入淺出Java Tree
什么是平衡二叉樹（AVL）
圖解二叉樹和二分搜索樹（Java代碼實現(xiàn))
30 張圖帶你徹底理解紅黑樹
JAVA學習-紅黑樹詳解
B站視頻 數(shù)據(jù)結(jié)構(gòu)-浙江大學
