框架實現修改功能的原理_JAVA集合框架的特點及實現原理簡介

1.集合框架總體架構

7875b4946e7fd8781b26423a616a8275.png
2a0df4b817146ac05b5e1ac2d25d7117.png
  • 集合大致分為Set、List、Queue、Map四種體系,其中List,Set,Queue繼承自Collection接口，Map為獨立接口
  • Set的實現類有:HashSet，LinkedHashSet，TreeSet...
  • List下有ArrayList，Vector，LinkedList...
  • Map下有Hashtable，LinkedHashMap，HashMap，TreeMap...

list有序，可重復ArrayList:數組，查詢快，增刪慢。線程不安全. Vector:數組，查詢快，增刪慢。線程安全. LinkedList:鏈表，查詢慢，增刪快。線程不安全set無序(不嚴謹)，唯一HashSet:無序,唯一,哈希表實現,通過hashCode()和equals()保證唯一。 LinkedHashSet:繼承自hashset,底層是鏈表和哈希表。(FIFO插入有序,唯一) TreeSet:底層是紅黑樹。(唯一，有序)mapKV形式的鍵值對TreeMap:有序,不是線程安全的。 HashMap:無序,不是線程安全的,HashMap允許null值(key和value都允許) HashTable:無序,線程安全的,不允許null值。

2. Set

Set 接口繼承Collection，用于存儲不含重復元素的集合。

HashSet

底層是哈希表，當插入元素時，HashSet會調用該對象的hashCode()方法得到hashCode，然后根據hashCode決定該對象在哈希表中的存儲位置。 (這里有個問題，如果hashcode不是均勻分布的，而是集中在一個區域，極端情況下，hash表會變成鏈表)

HashSet去重原理：通過equals()方法比較，且其hashCode()方法返回值也相等。 (可以通過覆寫hashCode和equals方法改變其去重規則，進行自定義去重)

f49fd672b745d764f6ff099b933baff3.png

TreeSet

TreeSet底層是紅黑樹;加入元素時，必須加入同類型的對象，否則會發生ClassCastException異常，因為TreeSet會調用集合元素的compareTo()方法來比較元素之間的大小關系(自然排序)。

compareTo()方法的返回值決定了順序:

  • -1 表示放在紅黑樹的左邊,即逆序輸出;
  • 1 表示放在紅黑樹的右邊，即順序輸出;
  • 0 表示元素相同，僅存放第一個元素自然排序(treeset去重的原理);

其次，TreeSet也可以通過比較器排序。

LinkedHashSet

繼承自HashSet,底層是鏈表和哈希表。

  • 由鏈表保證元素有序(插入順序)。
  • 由哈希表保證元素唯一

TreeSet, LinkedHashSet and HashSet 的區別

  • 都實現Set接口,不包含重復元素
  • 都不是線程安全的，如果要使用線程安全可以Collections.synchronizedSet()
  • TreeSet的主要功能用于排序
  • LinkedHashSet的主要功能用于保證FIFO,即有序的集合(先進先出)
  • HashSet只是通用的存儲數據的集合
  • 插入速度: HashSet>LinkHashSet>TreeSet(內部實現排序)
  • HashSet不保證順序，LinkHashSet保證FIFO(先進先出)，TreeSet安裝內部實現排序，也可以自定義排序規則
  • HashSet和LinkHashSet允許null, (只能有一個null) 但TreeSet中插入null時會報NullPointerException

3. List

list的實現類有ArrayList,Vector,LinkedList...其中ArrayList和Vector很相似，均是以數組作為底層實現，不同之處在于Vector是線程安全的。

50c428d85d0166c15501785b4213274a.png

ArrayList

ArrayList基于數組實現,不是線程安全的,內部維護了一個可變長的對象數組,集合內所有元素存儲于這個數組中，并實現該數組長度的動態伸縮。

ArrayList使用數組拷貝來實現指定位置的插入和刪除。

LinkedList

LinkedList內部以鏈表的形式來保存元素，因此隨機訪問集合時性能較差，但插入,刪除元素時性能較好。

LinkedList不僅實現了List接口,還實現了Deque接口，可以被當成雙端隊列來使用，即可被當成“棧”來使用，也可以當成隊列使用。

ArrayList 和LinkedList比較

  • 兩者都是List接口的實現類,都不是線程安全。List的另外一個實現類vector是線程安全的。
  • ArrayList是基于動態數組的數據結構，而LinkedList是基于鏈表的數據結構。
  • 對于隨機訪問get和set(查詢操作)，ArrayList要優于LinkedList.(LinkedList要移動指針)
  • 對于增刪操作(add和remove)，LinkedList優于ArrayList。

4. Map

Map集合用于保存映射關系的數據，Map集合中保存了兩組值，一組是 key， 一組是 value。

Map的key不能重復。

key和value之間存在單向一對一的關系， 通過key，能找到唯一確定的value。

Map將key和value封裝至一個叫做Entry的對象中，Map中存儲的元素實際是Entry。只有在keySet()和values()方法被調用時，Map才會將keySet和values對象實例化。

6943a64ccc87a18479e77486ef28e1a9.png

HashMap

key 是通過hash表來存儲，value是通過鏈表來存儲。

HashMap將Entry對象存儲在一個數組中，并通過哈希表來實現對Entry的快速訪問。 (通過key的哈希值計算Entry在數組中的index，以此訪問value) (拉鏈法，解決hash碰撞)

HashTable

幾乎和HashMap一樣，都是通過數組存儲Entry，以key的哈希值計算Entry在數組中的index，用拉鏈法解決哈希沖突。二者最大的不同在于， Hashtable是線程安全的，其提供的方法幾乎都是同步的。

ConcurrentHashMap

ConcurrentHashMap是HashMap的線程安全版，提供比Hashtable更高效的并發性能。

Hashtable 在進行讀寫操作時會鎖住整個Entry數組，這就導致數據越多性能越差。

ConcurrentHashMap使用分離鎖的思路解決并發性能，其將 Entry數組拆分至16個Segment中，以哈希算法決定Entry應該存儲在哪個Segment。這樣就可以實現在寫操作時只對一個Segment 加鎖，大幅提升了并發寫的性能。

在進行讀操作時，ConcurrentHashMap在絕大部分情況下都不需要加鎖，其Entry中的value是volatile的，這保證了value被修改時的線程可見性，無需加鎖便能實現線程安全的讀操作。

ConcurrentHashMap它不能保證讀操作的絕對一致性。ConcurrentHashMap保證讀操作能獲取到已存在Entry的value的最新值，同時也能保證讀操作可獲取到已完成的寫操作的內容，但如果寫操作是在創建一個新的Entry，那么在寫操作沒有完成時，讀操作是有可能獲取不到這個Entry的。

HashMap和HashTable,ConcurrentHashMap的區別

  • 三者在數據存儲層面的機制原理基本一致
  • HashMap不是線程安全的
  • Hashtable是線程安全的，能保證絕對的數據一致性
  • ConcurrentHashMap 也是線程安全的，使用分離鎖和volatile等方法極大地提升了讀寫性能，同時也能保證在絕大部分情況下的數據一致性。但其不能保證絕對的數據一致性，在一個線程向Map中加入Entry的操作沒有完全完成之前，其他線程有可能讀不到新加入的Entry
  • HashTable不允許使用null作為key和value，如果放入null將引發NullPointerException異常，但HashMap可以使用null作為key或value(只能有一個key為null,可以多個value為null)。
  • 如果在遍歷的同時，修改HashTable的大小，容易應發異常。可以用代替，ConcurrentHashMap是HashMap的線程安全版，提供比Hashtable更高效的并發性能

end：如果你覺得本文對你有幫助的話，記得關注點贊轉發，你的支持就是我更新動力。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/282041.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/282041.shtml
英文地址，請注明出處：http://en.pswp.cn/news/282041.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

NPM報錯終極大法

NPM報錯終極大法

2019獨角獸企業重金招聘Python工程師標準>>> 所有的錯誤基本上都跟node的版本相關 直接刪除系統中的node 重新安裝 sudo rm -rf /usr/local/{bin/{node,npm},lib/node_modules/npm,lib/node,share/man/*/node.*} 重新安裝 $ n lts $ npm install -g npm $ n stable…
閱讀更多...
自己使用的一個.NET輕量開發結構

自己使用的一個.NET輕量開發結構

三個文件夾，第一個是放置前端部分，第二個是各種支持的類文件，第三個是單元測試文件。Core文件類庫放置的是與數據庫做交互的文件，以及一些第三方類庫，還有與數據庫連接的文件1.Lasy.Validator是一個基于Attribute驗證器…
閱讀更多...
英語影視臺詞---八、the shawshank redemption

英語影視臺詞---八、the shawshank redemption

英語影視臺詞---八、the shawshank redemption 一、總結 一句話總結：肖申克的救贖 1、Its funny. On the outside, I was an honest man. Straight as an arrow. I had to come to prison to be a crook.？ 這很有趣。 在外面，我是一個誠實的人…
閱讀更多...
10.python網絡編程（socket server 實現并發 part 2）

10.python網絡編程（socket server 實現并發 part 2）

一、基于tcp的socket通信的基本原理分析。基于tcp的socket通信，主要依靠兩個循環，分別是連接循環和通信循環。這個前面的文章有寫過，在這里就不再重復了。二、socketserver實現多并發的原理分析。1.server類：2.reques類。類繼承關…
閱讀更多...
如何在一小時內更新100篇文章？-Evernote Sync插件介紹

如何在一小時內更新100篇文章？-Evernote Sync插件介紹

上一篇“手把手教你制作微信小程序，開源、免費、快速搞定”，已經教會你如何快速制作一個小程序，但作為資訊類小程序，內容不可少，并且還需要及時更新。 但是，如果讓你復制粘貼，可能還需要上傳圖片…
閱讀更多...
linux awk

linux awk

grep 文本過濾器sed 流編輯器awk 報告生成器 格式化以后顯示awk [option] PATTERN {action} file1 file2awk -F"|" BEGIN{OFS":"} {print $1,$2,$3} test.txt #文本字符串用雙引號awk -F"|" BEGIN{OFS":"} {print $1,"jksong&quo…
閱讀更多...
iOS無線真機調試

iOS無線真機調試

為什么80%的碼農都做不了架構師？>>> Xcode從9開始 就支持無線真機調試，那么怎么操作呢？ 首先用數據線連接你的設備，接下來Xcode- Window-Devices and Simulators 點開之后看到你的設備 默認情況下Connect via networ…
閱讀更多...
碼棧開發手冊（一）---編碼方式開發（初級課程②）

碼棧開發手冊（一）---編碼方式開發（初級課程②）

本文轉自碼棧平臺
閱讀更多...
Mybatis中jdbcType和javaType的對應關系

Mybatis中jdbcType和javaType的對應關系

2019獨角獸企業重金招聘Python工程師標準>>> Mybatis中jdbcType和javaType的對應關系 1 JDBC Type Java Type 2 CHAR String 3 VARCHAR String 4 LONGVARCHAR String 5 NUMERIC java.math.…
閱讀更多...
java貪吃蛇

java貪吃蛇

使用雙向鏈表實現貪吃蛇程序 1.鏈表節點定義： package snake;public class SnakeNode {private int x;private int y;private SnakeNode next;private SnakeNode ahead;public SnakeNode() {}public SnakeNode(int x, int y) {super();this.x x;this.y y;}public …
閱讀更多...
【死磕 Spring】----- IOC 之解析 bean 標簽：解析自定義標簽

【死磕 Spring】----- IOC 之解析 bean 標簽：解析自定義標簽

前面四篇文章都是分析 Bean 默認標簽的解析過程，包括基本屬性、六個子元素（meta、lookup-method、replaced-method、constructor-arg、property、qualifier），涉及內容較多，拆分成了四篇文章，導致我們已經忘…
閱讀更多...
Codeigniter 4.0-dev 版源碼學習筆記之四——詳細路由過程

Codeigniter 4.0-dev 版源碼學習筆記之四——詳細路由過程

前言 我個人覺得在當前 MVC 流行的架構下，要想去了解一個框架，或者是一個基于此架構下的應用程序，最好的入手方式就是先看路由，雖然路由不是 MVC 里的任何一個，但是知道了路由的來龍去脈就知道了整個框架或者是應用的結…
閱讀更多...
固態硬盤和機械硬盤的比較和SQLSERVER在兩種硬盤上的性能差異

固態硬盤和機械硬盤的比較和SQLSERVER在兩種硬盤上的性能差異

聽說固態硬盤是高富帥的必備神器，本人為了提升工作效率和提高工作速度 這個月節衣縮食，終于也決定買了一塊三星固態硬盤120G容量 這個固態硬盤拿在手里輕飄飄的， 好像里面什么東西都沒有似的 廢話少說，先上圖 開機速度20秒左右 測…
閱讀更多...
大文件讀寫效率比較

大文件讀寫效率比較

之前做到一個大日志文件（size > 1G）解析的項目，在此記錄下對于大文本解析方式的效率比較。不同方式的性能差別很大，那個項目的日志解析時間能從原來的超過36小時優化到只需要2分鐘，awk功不可沒。 bash 比較 bash腳本…
閱讀更多...
python裝飾器執行順序

python裝飾器執行順序

2019獨角獸企業重金招聘Python工程師標準>>> 1、單個裝飾器執行 上來先看代碼： import timedef deco(func):functools.wraps(func)def _wrapper():startTime time.time()print "start"func()print "end"endTime time.time()msecs …
閱讀更多...
tomcat限制用域名訪問 禁止 ip訪問

tomcat限制用域名訪問 禁止 ip訪問

有時候會遇到服務器網站。只可以通過域名訪問。而不允許ip訪問。防止域名惡意解析，tomcat可以實現這個簡單功能。1，禁止ip訪問項目 2，只允許綁定域名訪問環境：tomcat7 外網地址：114.113.100.166 域名：bi…
閱讀更多...
Object關于屬性property的靜態方法

Object關于屬性property的靜態方法

Object.defineProperty Object.defineProperty(obj, prop, { value: undefined, enumerable: true, writable:true, get: function() {return value}, set: function(newValue) {value newValue;} }) 當時配置了set和get時，則不能配置value。 Object.getOwnPropert…
閱讀更多...
99. Recover Binary Search Tree

99. Recover Binary Search Tree

一、題目 1、審題 2、分析 給出一個二叉查找樹，其中有兩個元素的位置弄錯了，寫算法將其恢復。 二、解答 1、思路： 方法一、 通過中序遍歷可以確定一棵二叉查找樹由小到大的順序。 所以在此錯位的查找樹中查找到的節點中有 1 個比后續節點值大…
閱讀更多...
myeclipse+git pull項目報錯

myeclipse+git pull項目報錯

2019獨角獸企業重金招聘Python工程師標準>>> 1.在本地工程目錄(.git)找到config文件； 2.修改config文件內容為： [core] repositoryformatversion 0 filemode false logallrefupdates true [branch "master"] remote origin m…
閱讀更多...
luoguP4755 Beautiful Pair

luoguP4755 Beautiful Pair

https://www.luogu.org/problemnew/show/P4755 考慮分治，在 [l, r] 區間中用線段樹找到最大的一個點，處理經過它的可行數對的個數，統計個數可以離線樹狀數組處理 因為最多被分成 2n 個區間（像線段樹一樣），對…
閱讀更多...
最新文章

Copyright @ 2022~2023