Java中List、Set、Map的區(qū)別和實(shí)現(xiàn)方式

List

• List 是一個(gè)有序的集合，即元素按照插入的順序進(jìn)行排序，可以有重復(fù)的元素。
• 因?yàn)槭怯行虻?，所以可以根?jù)下標(biāo)來(lái)獲取元素或者遍歷整個(gè)集合內(nèi)的元素。
• 常用的實(shí)現(xiàn)類(lèi)包括 ArrayList 和 LinkedList。

ArrayList

• 底層是基于數(shù)組實(shí)現(xiàn)的，在內(nèi)部維護(hù)了一個(gè) Object[] 數(shù)組。
• 當(dāng)需要添加元素時(shí)，首先檢查數(shù)組是否已滿，如果未滿，就直接在后面添加元素，否則需要通過(guò)擴(kuò)容數(shù)組的方式來(lái)增加容量。
• 由于數(shù)組長(zhǎng)度固定且數(shù)組內(nèi)的元素是連續(xù)的，因此查詢某個(gè)元素的時(shí)間復(fù)雜度為 O(1)，而添加或刪除元素的時(shí)間復(fù)雜度為 O(n)（需要移動(dòng)后面的元素）。

LinkedList

• 底層是基于鏈表實(shí)現(xiàn)的，每個(gè)節(jié)點(diǎn)包含一個(gè)元素和指向下一個(gè)節(jié)點(diǎn)的引用。
• 當(dāng)需要添加(尾部添加O(1))或刪除(刪除頭結(jié)點(diǎn)或者使用 iterator 的 remove 方法 O(1))元素時(shí)，只需要修改相鄰節(jié)點(diǎn)之間的引用，不需要對(duì)其他元素進(jìn)行移動(dòng)。這使得 LinkedList 在添加或刪除元素方面比 ArrayList 更快。
• 由于沒(méi)有連續(xù)的內(nèi)存，并且需要遍歷整個(gè)鏈表才能找到指定元素，因此查詢某個(gè)元素的時(shí)間復(fù)雜度為 O(n)，而添加或刪除元素的時(shí)間復(fù)雜度為 O(1)。

Set

• Set 是一個(gè)不允許有重復(fù)元素的集合，元素沒(méi)有特定的順序。
• 可以用來(lái)判斷某個(gè)元素是否在集合￥￥現(xiàn)過(guò)。
• 常用的實(shí)現(xiàn)類(lèi)包括 HashSet 和 TreeSet。

HashSet

• 底層是基于 HashMap 來(lái)實(shí)現(xiàn)的，內(nèi)部維護(hù)了一個(gè) HashMap 實(shí)例作為其成員變量。
• 添加元素時(shí)，將元素作為 key 存儲(chǔ)在 HashMap 中，value 為一個(gè)固定的常量對(duì)象。
• 由于 HashMap 底層使用了哈希表，因此可以快速查找某個(gè)元素是否已存在集合中，時(shí)間復(fù)雜度為 O(1)。
• 不保證遍歷順序，也不保證插入順序。

TreeSet

• 底層是基于紅黑樹(shù)實(shí)現(xiàn)的，每個(gè)元素都必須實(shí)現(xiàn) Comparable 接口或向構(gòu)造函數(shù)傳遞一個(gè) Comparator 對(duì)象。
• 每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)元素，且每個(gè)節(jié)點(diǎn)具有以下性質(zhì)：
• 如果一個(gè)節(jié)點(diǎn)有左子節(jié)點(diǎn)，則左子節(jié)點(diǎn)上的所有元素都比該節(jié)點(diǎn)上的元素??；
• 如果一個(gè)節(jié)點(diǎn)有右子節(jié)點(diǎn)，則右子節(jié)點(diǎn)上的所有元素都比該節(jié)點(diǎn)上的元素大；
• 左右子樹(shù)自身都是一棵二叉搜索樹(shù)。
• 由于 TreeSet 底層采用了紅黑樹(shù)，因此平均情況下添加元素、刪除元素、查找元素的時(shí)間復(fù)雜度都為 O(logn)。
• 確保元素按升序排列，或者在創(chuàng)建時(shí)通過(guò)傳遞 Comparator 實(shí)例來(lái)自定義排序方式。

Map

• Map 是一個(gè)鍵值對(duì)映射的集合，允許鍵和值都可以為 null，但鍵不能重復(fù)，值可以重復(fù)。
• 可以用于存儲(chǔ)一些關(guān)聯(lián)性比較強(qiáng)的數(shù)據(jù)對(duì)象，例如電話簿、字典等。
• 常用的實(shí)現(xiàn)類(lèi)包括 HashMap 和 TreeMap。

HashMap

• 底層也是基于哈希表來(lái)實(shí)現(xiàn)的，內(nèi)部維護(hù)了一個(gè)數(shù)組，每個(gè)元素都是一個(gè)鏈表或樹(shù)的首節(jié)點(diǎn)，用于解決哈希沖突。
• 添加元素時(shí)，會(huì)根據(jù) key 的 hash 值進(jìn)行散列，然后找到對(duì)應(yīng)的數(shù)組位置，如果該位置上已經(jīng)存在元素，則以鏈表或樹(shù)結(jié)構(gòu)的形式將其插入。
• HashMap 可以快速查找某個(gè) key 對(duì)應(yīng)的 value 是否存在集合中，時(shí)間復(fù)雜度為 O(1)（如果哈希函數(shù)設(shè)計(jì)得好）。
• 遍歷順序和插入順序都不保證。

TreeMap

• 底層是基于紅黑樹(shù)實(shí)現(xiàn)的，每個(gè)鍵值對(duì)都被封裝成一個(gè) Entry 對(duì)象，按照鍵的自然順序或指定 Comparator 排序。
• TreeMap 中的所有元素都保證按照排序規(guī)則排列，在遍歷 TreeMap 時(shí)可以獲得有序的鍵值對(duì)列表。
• 添加、刪除、查找元素的時(shí)間復(fù)雜度都為 O(logn)，其中 n 表示元素個(gè)數(shù)。
• TreeMap 可以自定義排序方式，并且支持限制只允許包含實(shí)現(xiàn)了 Comparable 接口的鍵類(lèi)型。

總結(jié)

List

List是Java集合框架中最基本和最常用的一種數(shù)據(jù)結(jié)構(gòu)，它是有序集合，可以允許重復(fù)的元素。List提供了按照索引來(lái)插入、刪除和獲取指定位置上的元素等操作。

Java中List有很多實(shí)現(xiàn)類(lèi)，比較常用的有：

• ArrayList：基于數(shù)組實(shí)現(xiàn)，以及動(dòng)態(tài)擴(kuò)容。
• LinkedList：基于鏈表實(shí)現(xiàn)，適合于頻繁添加、刪除元素操作。

Set

Set也是Java集合框架中的一種數(shù)據(jù)結(jié)構(gòu)，它是由不同元素組合而成的無(wú)序集合，不允許有重復(fù)元素。Set的主要目的是為了消除重復(fù)元素。

Java中Set的實(shí)現(xiàn)類(lèi)有：

• HashSet：基于哈希表實(shí)現(xiàn)，可快速判斷對(duì)象的唯一性。
• TreeSet：基于紅黑樹(shù)實(shí)現(xiàn)，可以對(duì)元素排序并保證元素唯一性。
• LinkedHashSet：基于哈希表和鏈表實(shí)現(xiàn)，保留插入時(shí)順序并保證元素唯一性。

Map

Map也是Java集合框架中最常用的一種數(shù)據(jù)結(jié)構(gòu)，它是由鍵值對(duì)組成的集合，每個(gè)鍵只能出現(xiàn)一次，而且每個(gè)鍵只能映射到一個(gè)值。

Java中Map有很多實(shí)現(xiàn)類(lèi)，比較常用的有：

• HashMap：基于哈希表實(shí)現(xiàn)，以鍵值對(duì)的形式進(jìn)行存儲(chǔ)和訪問(wèn)。
• TreeMap：基于紅黑樹(shù)實(shí)現(xiàn)，可以對(duì)鍵進(jìn)行排序并保證鍵的唯一性。
• LinkedHashMap：基于哈希表和鏈表實(shí)現(xiàn)，按照插入順序維護(hù)元素的次序。

到此這篇關(guān)于Java中List、Set、Map的區(qū)別和實(shí)現(xiàn)方式的文章就介紹到這了,更多相關(guān)java list set map區(qū)別內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論