字节一面 —— List 和 Map、Set 的区别
馬上就要到金三銀四佳季了，是找工作的好時候，小伙伴們一定要把握好時機(jī)，找到心儀的高薪工作。找工作就少不了面試，那我們從現(xiàn)在開始，多刷刷面試題，查缺補漏！！！
目錄
?常見的數(shù)據(jù)結(jié)構(gòu)?
?集合和數(shù)組的區(qū)別?
?List 和 Map、Set 的區(qū)別?
?List 和 Map、Set 的實現(xiàn)類?
?Hashmap的底層原理?
?Hashmap和hashtable ConcurrentHashMap區(qū)別?
?
?常見的數(shù)據(jù)結(jié)構(gòu)?
?
常用的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組，棧，隊列，鏈表，樹，散列，堆，圖
?
數(shù)組是最常用的數(shù)據(jù)結(jié)構(gòu)，數(shù)組的特點是長度固定，數(shù)組的大小固定后就無法擴(kuò)容了?，數(shù)組只能存儲一種類型的數(shù)據(jù)?，添加，刪除的操作慢，因為要移動其他的元素。
棧是一種基于先進(jìn)后出（FILO）的數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表。它按照先進(jìn)后出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。
隊列是一種基于先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入，在另一端進(jìn)行刪除操作的特殊線性表，它按照先進(jìn)先出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)，在讀取數(shù)據(jù)時先被讀取出來。
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，其物理結(jié)構(gòu)不能只表示數(shù)據(jù)元素的邏輯順序，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列的結(jié)節(jié)（鏈表中的每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。根據(jù)指針的指向，鏈表能形成不同的結(jié)構(gòu)，例如單鏈表，雙向鏈表，循環(huán)鏈表等。?
樹是我們計算機(jī)中非常重要的一種數(shù)據(jù)結(jié)構(gòu)，同時使用樹這種數(shù)據(jù)結(jié)構(gòu)，可以描述現(xiàn)實生活中的很多事物，例如家譜、單位的組織架構(gòu)等等。有二叉樹、平衡樹、紅黑樹、B樹、B+樹。
散列表，也叫哈希表，是根據(jù)關(guān)鍵碼和值 (key和value) 直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，通過key和value來映射到集合中的一個位置，這樣就可以很快找到集合中的對應(yīng)元素。
堆是計算機(jī)學(xué)科中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱，堆通?？梢员豢醋魇且豢猛耆鏄涞臄?shù)組對象。
圖的定義：圖是由一組頂點和一組能夠?qū)蓚€頂點相連的邊組成的
?集合和數(shù)組的區(qū)別?
?
區(qū)別：數(shù)組長度固定 ??集合長度可變
數(shù)組中存儲的是同一種數(shù)據(jù)類型的元素，可以存儲基本數(shù)據(jù)類型，也可以存儲引用數(shù)據(jù)類型；
集合存儲的都是對象，而且對象的數(shù)據(jù)類型可以不一致。在開發(fā)當(dāng)中一般當(dāng)對象較多的時候，使用集合來存儲對象。
?List 和 Map、Set 的區(qū)別?
?
List和Set是存儲單列數(shù)據(jù)的集合，Map是存儲鍵值對這樣的雙列數(shù)據(jù)的集合；
List中存儲的數(shù)據(jù)是有順序的，并且值允許重復(fù)；
Map中存儲的數(shù)據(jù)是無序的，它的鍵是不允許重復(fù)的，但是值是允許重復(fù)的；
Set中存儲的數(shù)據(jù)是無順序的，并且不允許重復(fù)，但元素在集合中的位置是由元素的hashcode決定，即位置是固定的（Set集合是根據(jù)hashcode來進(jìn)行數(shù)據(jù)存儲的，所以位置是固定的，但是這個位置不是用戶可以控制的，所以對于用戶來說set中的元素還是無序的）。
?List 和 Map、Set 的實現(xiàn)類?
?
(1)Connection接口:
List 有序,可重復(fù)
ArrayList
優(yōu)點: 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，查詢快，增刪慢。
缺點: 線程不安全，效率高
Vector
優(yōu)點: 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，查詢快，增刪慢。
缺點: 線程安全，效率低, 已給舍棄了
LinkedList
優(yōu)點: 底層數(shù)據(jù)結(jié)構(gòu)是鏈表，查詢慢，增刪快。
缺點: 線程不安全，效率高
Set?無序,唯一
HashSet
底層數(shù)據(jù)結(jié)構(gòu)是哈希表。(無序,唯一)
如何來保證元素唯一性?
依賴兩個方法：hashCode()和equals()
LinkedHashSet
底層數(shù)據(jù)結(jié)構(gòu)是鏈表和哈希表。(FIFO插入有序,唯一)
1.由鏈表保證元素有序
2.由哈希表保證元素唯一
TreeSet
底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹。(唯一，有序)
1. 如何保證元素排序的呢?
自然排序
比較器排序
2.如何保證元素唯一性的呢?
根據(jù)比較的返回值是否是0來決定
(2)Map接口有四個實現(xiàn)類：?
HashMap?
基于 hash 表的 Map 接口實現(xiàn)，非線程安全，高效，支持 null 值和 null?鍵，?線程不安全。
HashTable?
線程安全，低效，不支持 null 值和 null 鍵；?
LinkedHashMap?
線程不安全，是 HashMap 的一個子類，保存了記錄的插入順序；
TreeMap
能夠把它保存的記錄根據(jù)鍵排序，默認(rèn)是鍵值的升序排序，線程不安全。
?Hashmap的底層原理?
?
HashMap在JDK1.8之前的實現(xiàn)方式?數(shù)組+鏈表,
但是在JDK1.8后對HashMap進(jìn)行了底層優(yōu)化,改為了由?數(shù)組+鏈表或者數(shù)值+紅黑樹實現(xiàn),主要的目的是提高查找效率
默認(rèn)的負(fù)載因子大小為0.75，數(shù)組大小為16。也就是說，默認(rèn)情況下，那么當(dāng)HashMap中元素個數(shù)超過16*0.75=12的時候，就把數(shù)組的大小擴(kuò)展為2*16=32，即擴(kuò)大一倍。
map.put(k,v)實現(xiàn)原理
（1）首先將k,v封裝到Node對象當(dāng)中（節(jié)點）。
（2）先調(diào)用k的hashCode()方法得出哈希值，并通過哈希算法轉(zhuǎn)換成數(shù)組的下標(biāo)。
（3）下標(biāo)位置上如果沒有任何元素，就把Node添加到這個位置上。如果說下標(biāo)對應(yīng)的位置上有鏈表。此時，就會拿著k和鏈表上每個節(jié)點的k進(jìn)行equal。如果所有的equals方法返回都是false，那么這個新的節(jié)點將被添加到鏈表的末尾。如其中有一個equals返回了true，那么這個節(jié)點的value將會被覆蓋。
map.get(k)實現(xiàn)原理
(1)、先調(diào)用k的hashCode()方法得出哈希值，并通過哈希算法轉(zhuǎn)換成數(shù)組的下標(biāo)。
(2)、在通過數(shù)組下標(biāo)快速定位到某個位置上。重點理解如果這個位置上什么都沒有，則返回null。如果這個位置上有單向鏈表，那么它就會拿著參數(shù)K和單向鏈表上的每一個節(jié)點的K進(jìn)行equals，如果所有equals方法都返回false，則get方法返回null。如果其中一個節(jié)點的K和參數(shù)K進(jìn)行equals返回true，那么此時該節(jié)點的value就是我們要找的value了，get方法最終返回這個要找的value。
不同的對象算出來的數(shù)組下標(biāo)是相同的這樣就會產(chǎn)生hash沖突，當(dāng)單線鏈表達(dá)到一定長度后效率會非常低。
?Hashmap和hashtable ConcurrentHashMap區(qū)別?
?
1、HashMap 是非線程安全的，HashTable 是線程安全的。
2、HashMap 的鍵和值都允許有 null 值存在，而 HashTable 則不行。
3、因為線程安全的問題，HashMap 效率比 HashTable 的要高。
4、Hashtable 是同步的，而 HashMap 不是。因此，HashMap 更適合于單線
程環(huán)境，而 Hashtable 適合于多線程環(huán)境。一般現(xiàn)在不建議用 HashTable, ①
是 HashTable 是遺留類，內(nèi)部實現(xiàn)很多沒優(yōu)化和冗余。②即使在多線程環(huán)境下，
現(xiàn)在也有同步的 ConcurrentHashMap 替代，沒有必要因為是多線程而用
HashTable。
HashTable 使用的是 Synchronized 關(guān)鍵字修飾，ConcurrentHashMap 是JDK1.7使用了鎖分段技術(shù)來保證線程安全的。JDK1.8ConcurrentHashMap取消了Segment分段鎖，采用CAS和synchronized來保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)類似，數(shù)組+鏈表/紅黑二叉樹。
synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點，這樣只要hash不沖突，就不會產(chǎn)生并發(fā)，效率又提升N倍。
?
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎總結(jié)
以上是生活随笔為你收集整理的字节一面 —— List 和 Map、Set 的区别的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 鬼吹灯《昆仑神宫》官宣 潘粤明、张雨绮、
- 下一篇： 理想L9预定太火爆！服务器直接挤爆了