ArrayList實現(xiàn)原理要點概括
參考文獻:
http://zhangshixi.iteye.com/blog/674856l
https://www.cnblogs.com/leesf456/p/5308358.html
- ArrayList是List接口的可變數(shù)組非同步實現(xiàn),并允許包括null在內(nèi)的所有元素扶关。
- 底層使用數(shù)組實現(xiàn)
- 該集合是可變長度數(shù)組节槐,數(shù)組擴容時铜异,會將老數(shù)組中的元素重新拷貝一份到新的數(shù)組中揍庄,每次數(shù)組容量增長大約是其容量的1.5倍东抹,這種操作的代價很高缭黔。
- 采用了Fail-Fast機制试浙,面對并發(fā)的修改時田巴,迭代器很快就會完全失敗壹哺,而不是冒著在將來某個不確定時間發(fā)生任意不確定行為的風險
- remove方法會讓下標到數(shù)組末尾的元素向前移動一個單位管宵,并把最后一位的值置空,方便GC
LinkedList實現(xiàn)原理要點概括
參考文獻:
1.http://www.cnblogs.com/ITtangtang/p/3948610.htmll
2.https://www.cnblogs.com/leesf456/p/5308843.html
- LinkedList是List接口的雙向鏈表非同步實現(xiàn)岗喉,并允許包括null在內(nèi)的所有元素。
- 底層的數(shù)據(jù)結(jié)構(gòu)是基于雙向鏈表的炸庞,該數(shù)據(jù)結(jié)構(gòu)我們稱為節(jié)點
- 雙向鏈表節(jié)點對應(yīng)的類Node的實例钱床,Node中包含成員變量:prev,next埠居,item查牌。其中,prev是該節(jié)點的上一個節(jié)點滥壕,next是該節(jié)點的下一個節(jié)點,item是該節(jié)點所包含的值绎橘。
- 它的查找是分兩半查找胁孙,先判斷index是在鏈表的哪一半,然后再去對應(yīng)區(qū)域查找称鳞,這樣最多只要遍歷鏈表的一半節(jié)點即可找到
HashMap實現(xiàn)原理要點概括
參考文獻:http://zhangshixi.iteye.com/blog/672697
參考文獻:http://blog.csdn.net/lizhongkaide/article/details/50595719
- HashMap是基于哈希表的Map接口的非同步實現(xiàn)涮较,允許使用null值和null鍵,但不保證映射的順序胡岔。
- 底層使用數(shù)組實現(xiàn)法希,數(shù)組中每一項是個單向鏈表,即數(shù)組和鏈表的結(jié)合體靶瘸;當鏈表長度大于一定閾值時苫亦,鏈表轉(zhuǎn)換為紅黑樹,這樣減少鏈表查詢時間怨咪。
- HashMap在底層將key-value當成一個整體進行處理屋剑,這個整體就是一個Node對象。HashMap底層采用一個Node[]數(shù)組來保存所有的key-value對诗眨,當需要存儲一個Node對象時唉匾,會根據(jù)key的hash算法來決定其在數(shù)組中的存儲位置,在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置匠楚;當需要取出一個Node時巍膘,也會根據(jù)key的hash算法找到其在數(shù)組中的存儲位置,再根據(jù)equals方法從該位置上的鏈表中取出該Node芋簿。
- HashMap進行數(shù)組擴容需要重新計算擴容后每個元素在數(shù)組中的位置峡懈,很耗性能
- 采用了Fail-Fast機制,通過一個modCount值記錄修改次數(shù)与斤,對HashMap內(nèi)容的修改都將增加這個值肪康。迭代器初始化過程中會將這個值賦給迭代器的expectedModCount荚恶,在迭代過程中,判斷modCount跟expectedModCount是否相等磷支,如果不相等就表示已經(jīng)有其他線程修改了Map谒撼,馬上拋出異常
Hashtable實現(xiàn)原理要點概括
參考文獻:http://blog.csdn.net/zheng0518/article/details/42199477
- Hashtable是基于哈希表的Map接口的同步實現(xiàn),不允許使用null值和null鍵
- ** 底層使用數(shù)組實現(xiàn)雾狈,數(shù)組中每一項是個單鏈表廓潜,即數(shù)組和鏈表的結(jié)合體**
- Hashtable在底層將key-value當成一個整體進行處理,這個整體就是一個Entry對象箍邮。Hashtable底層采用一個Entry[]數(shù)組來保存所有的key-value對茉帅,當需要存儲一個Entry對象時,會根據(jù)key的hash算法來決定其在數(shù)組中的存儲位置锭弊,在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置堪澎;當需要取出一個Entry時,也會根據(jù)key的hash算法找到其在數(shù)組中的存儲位置味滞,再根據(jù)equals方法從該位置上的鏈表中取出該Entry樱蛤。
- synchronized是針對整張Hash表的,即每次鎖住整張表讓線程獨占
ConcurrentHashMap實現(xiàn)原理要點概括
參考文獻:http://blog.csdn.net/zheng0518/article/details/42199477
- ConcurrentHashMap允許多個修改操作并發(fā)進行剑鞍,其關(guān)鍵在于使用了鎖分離技術(shù)昨凡。
- 它使用了多個鎖來控制對hash表的不同段進行的修改,每個段其實就是一個小的hashtable蚁署,它們有自己的鎖便脊。只要多個并發(fā)發(fā)生在不同的段上,它們就可以并發(fā)進行光戈。
- ConcurrentHashMap在底層將key-value當成一個整體進行處理哪痰,這個整體就是一個Entry對象。Hashtable底層采用一個Entry[]數(shù)組來保存所有的key-value對久妆,當需要存儲一個Entry對象時晌杰,會根據(jù)key的hash算法來決定其在數(shù)組中的存儲位置,在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置筷弦;當需要取出一個Entry時肋演,也會根據(jù)key的hash算法找到其在數(shù)組中的存儲位置,再根據(jù)equals方法從該位置上的鏈表中取出該Entry烂琴。
- 與HashMap不同的是爹殊,ConcurrentHashMap使用多個子Hash表,也就是段(Segment)
- ConcurrentHashMap完全允許多個讀操作并發(fā)進行奸绷,讀操作并不需要加鎖边灭。如果使用傳統(tǒng)的技術(shù),如HashMap中的實現(xiàn)健盒,如果允許可以在hash鏈的中間添加或刪除元素绒瘦,讀操作不加鎖將得到不一致的數(shù)據(jù)。ConcurrentHashMap實現(xiàn)技術(shù)是保證HashEntry幾乎是不可變的扣癣。
HashSet實現(xiàn)原理要點概括
參考文獻:http://zhangshixi.iteye.com/blog/673143l
- HashSet由哈希表(實際上是一個HashMap實例)支持惰帽,不保證set的迭代順序,并允許使用null元素父虑。
- 基于HashMap實現(xiàn)该酗,API也是對HashMap的行為進行了封裝,可參考HashMap
LinkedHashMap實現(xiàn)原理要點概括
參考文獻:http://zhangshixi.iteye.com/blog/673789l
- LinkedHashMap繼承于HashMap士嚎,底層使用哈希表和雙向鏈表來保存所有元素呜魄,并且它是非同步,允許使用null值和null鍵莱衩。
- 基本操作與父類HashMap相似爵嗅,通過重寫HashMap相關(guān)方法,重新定義了數(shù)組中保存的元素Entry笨蚁,來實現(xiàn)自己的鏈接列表特性睹晒。該Entry除了保存當前對象的引用外,還保存了其上一個元素before和下一個元素after的引用括细,從而構(gòu)成了雙向鏈接列表伪很。
LinkedHashSet實現(xiàn)原理要點概括
參考文獻:http://zhangshixi.iteye.com/blog/673319l
- 對于LinkedHashSet而言,它繼承與HashSet奋单、又基于LinkedHashMap來實現(xiàn)的锉试。LinkedHashSet底層使用LinkedHashMap來保存所有元素,它繼承與HashSet览濒,其所有的方法操作上又與HashSet相同呆盖。
什么是Java集合API
Java集合框架API是用來表示和操作集合的統(tǒng)一框架,它包含接口匾七、實現(xiàn)類絮短、以及幫助程序員完成一些編程的算法。簡言之昨忆,API在上層完成以下幾件事:
● 編程更加省力丁频,提高城程序速度和代碼質(zhì)量
● 非關(guān)聯(lián)的API提高互操作性
● 節(jié)省學習使用新API成本
● 節(jié)省設(shè)計新API的時間
● 鼓勵、促進軟件重用
具體來說邑贴,有6個集合接口席里,最基本的是Collection接口,由三個接口Set拢驾、List奖磁、SortedSet繼承,另外兩個接口是Map繁疤、SortedMap,這兩個接口不繼承Collection咖为,表示映射而不是真正的集合秕狰。
Collection接口:存儲一組不唯一,無序的對象
List接口:存儲一組不唯一躁染,有序的對象
Set接口:存儲一組唯一鸣哀,無序的對象
Map接口:存儲一組鍵值對象,提高鍵(key)到值(value)的映射
為何Map接口不繼承Collection接口吞彤?
雖然Map接口和它的實現(xiàn)也是集合框架的一部分我衬。但Map不是集合。集合也不是Map饰恕。
因此挠羔,Map繼承Collection毫無意義,反之亦然埋嵌。
假設(shè)Map繼承Collection接口破加,那么元素去哪兒?Map包括key-value對莉恼,它提供抽取key或value列表集合的方法拌喉,可是它不適合“一組對象”規(guī)范
2.HashMap和Hashtable之間的區(qū)別?
在JDK1.6俐银,JDK1.7中尿背,HashMap采用位桶+鏈表實現(xiàn),即使用鏈表處理沖突捶惜,同一hash值的鏈表都存儲在一個鏈表里田藐。但是當位于一個桶中的元素較多,即hash值相等的元素較多時吱七,通過key值依次查找的效率較低汽久。而JDK1.8中,HashMap采用位桶+鏈表+紅黑樹實現(xiàn)踊餐,當鏈表長度超過閾值(8)時景醇,將鏈表轉(zhuǎn)換為紅黑樹,這樣大大減少了查找時間吝岭。
1.兩者最主要的區(qū)別在于Hashtable是線程安全三痰,而HashMap則非線程安全
Hashtable的實現(xiàn)方法里面都添加了synchronized關(guān)鍵字來確保線程同步,因此相對而言HashMap性能會高一些窜管,我們平時使用時若無特殊需求建議使用HashMap散劫,在多線程環(huán)境下若使用HashMap需要使用Collections.synchronizedMap()方法來獲取一個線程安全的集合。
2.HashMap可以使用null作為key幕帆,而Hashtable則不允許null作為key
雖說HashMap支持null值作為key获搏,不過建議還是盡量避免這樣使用,因為一旦不小心使用了失乾,若因此引發(fā)一些問題常熙,排查起來很是費事
3.HashMap是對Map接口的實現(xiàn)纬乍,HashTable實現(xiàn)了Map接口和Dictionary抽象類
HashMap的初始容量為16,Hashtable初始容量為11症概,兩者的填充因子默認都是0.75
4.HashMap擴容時是當前容量翻倍即:capacity2蕾额,Hashtable擴容時是容量翻倍+1即:capacity2+1
5.兩者計算hash的方法不同
Hashtable計算hash是直接使用key的hashcode對table數(shù)組的長度直接進行取模
Iterator、ListIterator 和 Enumeration的區(qū)別彼城?
Enumeration接口在Java1.2版本開始有,所以Enumeration是合法規(guī)范的接口
Enumeration使用elements()方法
Iterator對所有Java集合類都有實現(xiàn)
Iterator使用iterator方法
Iterator只能往一個方向前進
ListIterator僅僅對List類型的類實現(xiàn)了
ListIterator使用listIterator()方法
fail-fast 與 fail-safe 之間的區(qū)別退个?
Fail fast快速地報告任何的failure募壕。無論何時任何一個問題都會引發(fā) fail fast系統(tǒng)fails
在Java Fail fast 迭代器中,迭代objects集合有時會出現(xiàn)并發(fā)修改異常语盈,出現(xiàn)這種情況有2個原因
如果一個線程正在迭代一個集合舱馅,而另一個線程同時試圖修改這個集合
在調(diào)用remove()方法后,如何我們還試圖去修改集合object
Java 中 Set 與 List 有什么不同?
Set是一個不允許重復元素存在的集合
Set沒有索引
Set僅僅允許一個null值
Set有類:HashSet刀荒、LinkedHashMap代嗤、TreeSet
List有索引
List允許N個null值
List可以按插入順序顯示
List有類:Vector、ArrayList缠借、LinkedList
arraylist 與 vector 的區(qū)別?
Vector 在Java的第一個版本就引入了干毅,也就是說vector是一個合法規(guī)范的類
ArrayList在Java1.2版本引入的,是Java 集合框架的組成部分
Vector是同步的
ArrayList是不同步的
什么類實現(xiàn)了List接口泼返?
ArrayList
LinkedList
Vector
什么類實現(xiàn)了Set接口硝逢?
HashSet
LinkedHashSet
TreeSet
如何保證一個集合線程安全?
Vector, Hashtable, Properties 和 Stack 都是同步的類绅喉,所以它們都線程安全的渠鸽,可以被使用在多線程環(huán)境中
使用Collections.synchronizedList(list)) 方法,可以保證list類是線程安全的
使用java.util.Collections.synchronizedSet()方法可以保證set類是線程安全的
是否可以往 TreeSet 或者 HashSet 中添加 null
可以往 hashset 中添加一個 null
TreeSet 也允許一個 null值
Iterator符合哪個設(shè)計模式柴罐?
Iterator 設(shè)計模式
如何對Object的list排序徽缚?
對objects數(shù)組進行排序,我們可以用Arrays.sort()方法
如果要對objects的集合進行排序革屠,需要使用Collections.sort()方法
HashSet 實現(xiàn)了哪個數(shù)據(jù)結(jié)構(gòu)凿试?
HashSet 內(nèi)部實現(xiàn)了hashmap
為什么 Collection 不能繼承 Cloneable 和 Serializable?
Collection接口指定一組對象屠阻,對象即為它的元素红省。怎樣維護這些元素由Collection的詳細實現(xiàn)決定。
比如国觉。一些如List的Collection實現(xiàn)同意反復的元素吧恃。而其他的如Set就不同意。非常多Collection實現(xiàn)有一個公有的clone方法麻诀。
然而痕寓。把它放到集合的全部實現(xiàn)中也是沒有意義的傲醉。這是由于Collection是一個抽象表現(xiàn)。重要的是實現(xiàn)呻率。
當與詳細實現(xiàn)打交道的時候硬毕,克隆或序列化的語義和含義才發(fā)揮作用。所以礼仗,詳細實現(xiàn)應(yīng)該決定怎樣對它進行克隆或序列化吐咳,或它能否夠被克隆或序列化。
在全部的實現(xiàn)中授權(quán)克隆和序列化元践,終于導致更少的靈活性和很多其他的限制韭脊。特定的實現(xiàn)應(yīng)該決定它能否夠被克隆和序列化。
hashCode() 和 equals() 方法的重要性单旁?如何在Java中使用它們沪羔?
hashCode() 和 equals() 方法定義在”object”類中
如果equals() 方法在比較2個對象時返回true,那么hashCode()的返回值必須得一樣
什么是 Properties 類象浑?
Properties 是Hashtable的子類蔫饰。它被用于維護值的list,其中它們的鍵愉豺、值都是String類型
如何將一個字符串轉(zhuǎn)換為arraylist?
使用 arrayList.toArray() 方法
Java 集合類框架的基本接口有哪些篓吁?
Java 集合類提供了一套設(shè)計良好的支持對一組對象進行操作的接口和類。Java 集合類里面最基本的接口有:
Collection:代表一組對象粒氧,每一個對象都是它的子元素越除。
Set:不包含重復元素的 Collection。
List:有順序的 collection外盯,并且可以包含重復元素摘盆。
Map:可以把鍵(key)映射到值(value)的對象,鍵不能重復饱苟。
為什么集合類沒有實現(xiàn) Cloneable 和 Serializable 接口孩擂?
集合類接口指定了一組叫做元素的對象。集合類接口的每一種具體的實現(xiàn)類都可以選擇以它自己的方式對元素進行保存和排序箱熬。有的集合類允許重復的鍵类垦,有些不允許。
什么是迭代器(Iterator)城须?
Iterator 接口提供了很多對集合元素進行迭代的方法蚤认。每一個集合類都包含了可以返回迭代器實例的 迭代方法。迭代器可以在迭代的過程中刪除底層集合的元素糕伐。
克隆(cloning)或者是序列化(serialization)的語義和含義是跟具體的實現(xiàn)相關(guān)的砰琢。因此,應(yīng)該由集合類的具體實現(xiàn)來決定如何被克隆或者是序列化。
Iterator 和 ListIterator 的區(qū)別是什么陪汽?
下面列出了他們的區(qū)別:
Iterator 可用來遍歷 Set 和 List 集合训唱,但是 ListIterator 只能用來遍歷 List。
Iterator 對集合只能是前向遍歷挚冤,ListIterator 既可以前向也可以后向况增。
ListIterator 實現(xiàn)了 Iterator 接口,并包含其他的功能训挡,比如:增加元素澳骤,替換元素,獲取前一個和后一個元素的索引舍哄,等等宴凉。
快速失敗(fail-fast)和安全失敗(fail-safe)的區(qū)別是什么?
Iterator 的安全失敗是基于對底層集合做拷貝表悬,因此,它不受源集合上修改的影響丧靡。java.util包下面的所有的集合類都是快速失敗的蟆沫,而 java.util.concurrent 包下面的所有的類都是安全 失敗的∥轮危快速失敗的迭代器會拋出 ConcurrentModificationException 異常饭庞,而安全失敗的迭 代器永遠不會拋出這樣的異常。
Java 中的 HashMap 的工作原理是什么熬荆?
Java 中的 HashMap 是以鍵值對(key-value)的形式存儲元素的舟山。HashMap 需要一個 hash 函數(shù),它使用 hashCode()和 equals()方法來向集合/從集合添加和檢索元素卤恳。當調(diào)用 put()方法的時候累盗,HashMap 會計算 key 的 hash 值,然后把鍵值對存儲在集合中合適的索引上突琳。如果 key已經(jīng)存在了若债,value 會被更新成新值。HashMap 的一些重要的特性是它的容量(capacity)拆融,負載因子(load factor)和擴容極限(threshold resizing)蠢琳。
hashCode()和 equals()方法的重要性體現(xiàn)在什么地方?
Java 中的 HashMap 使用 hashCode()和 equals()方法來確定鍵值對的索引镜豹,當根據(jù)鍵獲取值
以這兩個方法的實現(xiàn)對 HashMap 的精確性和正確性是至關(guān)重要的
HashMap 和 Hashtable 有什么區(qū)別傲须?
HashMap 和 Hashtable 都實現(xiàn)了 Map 接口,因此很多特性非常相似趟脂。但是泰讽,他們有以下不同點:
HashMap 允許鍵和值是 null,而 Hashtable 不允許鍵或者值是 null。
Hashtable 是同步的菇绵,而 HashMap 不是肄渗。因此,HashMap 更適合于單線程環(huán)境咬最,而 Hashtable適合于多線程環(huán)境翎嫡。
HashMap 提供了可供應(yīng)用迭代的鍵的集合,因此永乌,HashMap 是快速失敗的惑申。另一方面,Hashtable 提供了對鍵的列舉(Enumeration)翅雏。
一般認為 Hashtable 是一個遺留的類圈驼。
數(shù)組(Array)和列表(ArrayList)有什么區(qū)別?什么時候應(yīng)該使用 Array 而不是ArrayList 望几?
下面列出了 Array 和 ArrayList 的不同點:
Array 可以包含基本類型和對象類型绩脆,ArrayList 只能包含對象類型。
Array 大小是固定的橄抹,ArrayList 的大小是動態(tài)變化的靴迫。
ArrayList 提供了更多的方法和特性,比如:addAll()楼誓,removeAll()玉锌,iterator()等等。
對于基本類型數(shù)據(jù)疟羹,集合使用自動裝箱來減少編碼工作量主守。但是,當處理固定大小的基本數(shù)據(jù)類型的時候榄融,這種方式相對比較慢参淫。
ArrayList 和 LinkedList 有什么區(qū)別?
ArrayList 和 LinkedList 都實現(xiàn)了 List 接口剃袍,他們有以下的不同點:
ArrayList 基于索引的數(shù)據(jù)接口黄刚,它的底層是數(shù)組。它可以以 O(1)時間復雜度對元素進行隨機訪問民效。與此對應(yīng)憔维,LinkedList是以元素列表的形式存儲它的數(shù)據(jù),每一個元素都和它的前 一個和后一個元素鏈接在一起畏邢,在這種情況下业扒,查找某個元素的時間復雜度是 O(n)。
相對于 ArrayList 舒萎,LinkedList 的插入程储,添加,刪除操作速度更快,因為當元素被添加到集合任 意位置的時候章鲤,不需要像數(shù)組那樣重新計算大小或者是更新索引摊灭。
LinkedList 比 ArrayList 更占內(nèi)存,因為 LinkedList 為每一個節(jié)點存儲了兩個引用败徊,一個指向前一個元素帚呼,一個指向下一個元素。也可以參考 ArrayList vs. LinkedList 皱蹦。
Comparable 和 Comparator 接口是干什么的煤杀?列出它們的區(qū)別。
參考鏈接: https://www.cnblogs.com/Kevin-mao/p/5912775.html
Java 提供了只包含一個 compareTo()方法的 Comparable 接口沪哺。這個方法可以個給兩個對象排序沈自。具體來說,它返回負數(shù)辜妓,0枯途,正數(shù)來表明輸入對象小于,等于籍滴,大于已經(jīng)存在的對象柔袁。
Java 提供了包含 compare()和 equals()兩個方法的 Comparator 接口。compare()方法用來給兩個輸入?yún)?shù)排序异逐,返回負數(shù),0插掂,正數(shù)表明第一個參數(shù)是小于灰瞻,等于,大于第二個參數(shù)辅甥。equals()方法需要一個對象作為參數(shù)酝润,它用來決定輸入?yún)?shù)是否和 comparator 相等。只有當輸入?yún)?shù)也是一個 comparator 并且輸入?yún)?shù)和當前 comparator 的排序結(jié)果是相同的時候璃弄,這個方法才返回 true 要销。
怎樣使Hashmap同步?
HashMap可以通過Map m = Collections.synchronizedMap(hashMap)來達到同步的效果夏块。
什么時候使用Hashtable疏咐,什么時候使用HashMap
基本的不同點是Hashtable同步HashMap不是的,所以無論什么時候有多個線程訪問相同實例的可能時脐供,就應(yīng)該使用Hashtable浑塞,反之使用HashMap。非線程安全的數(shù)據(jù)結(jié)構(gòu)能帶來更好的性能政己。
如果在將來有一種可能—你需要按順序獲得鍵值對的方案時酌壕,HashMap是一個很好的選擇,因為有HashMap的一個子類LinkedHashMap。所以如果你想可預測的按順序迭代(默認按插入的順序)卵牍,你可以很方便用LinkedHashMap替換HashMap果港。反觀要是使用的Hashtable就沒那么簡單了。同時如果有多個線程訪問HashMap糊昙,Collections.synchronizedMap()可以代替辛掠,總的來說HashMap更靈活。
為什么Vector類認為是廢棄的或者是非官方地不推薦使用溅蛉?或者說為什么我們應(yīng)該一直使用ArrayList而不是Vector
你應(yīng)該使用ArrayList而不是Vector是因為默認情況下你是非同步訪問的公浪,Vector同步了每個方法,你幾乎從不要那樣做船侧,通常有想要同步的是整個操作序列欠气。同步單個的操作也不安全(如果你迭代一個Vector,你還是要加鎖,以避免其它線程在同一時刻改變集合).而且效率更慢镜撩。當然同樣有鎖的開銷即使你不需要预柒,這是個很糟糕的方法在默認情況下同步訪問。你可以一直使用Collections.sychronizedList來裝飾一個集合袁梗。
事實上Vector結(jié)合了“可變數(shù)組”的集合和同步每個操作的實現(xiàn)宜鸯。這是另外一個設(shè)計上的缺陷。Vector還有些遺留的方法在枚舉和元素獲取的方法遮怜,這些方法不同于List接口淋袖,如果這些方法在代碼中程序員更趨向于想用它。盡管枚舉速度更快锯梁,但是他們不能檢查如果集合在迭代的時候修改了即碗,這樣將導致問題。盡管以上諸多原因陌凳,oracle也從沒宣稱過要廢棄Vector.