字节一面 —— 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预定太火爆!服务器直接挤爆了