多用多學(xué)之Java中的Set,List,Map詳解
很長(zhǎng)時(shí)間以來(lái)一直代碼中用的比較多的數(shù)據(jù)列表主要是List,而且都是ArrayList,感覺(jué)有這個(gè)玩意就夠了。ArrayList是用于實(shí)現(xiàn)動(dòng)態(tài)數(shù)組的包裝工具類(lèi),這樣寫(xiě)代碼的時(shí)候就可以拉進(jìn)拉出,迭代遍歷,蠻方便的。
也不知道從什么時(shí)候開(kāi)始慢慢的代碼中就經(jīng)常會(huì)出現(xiàn)HashMap和HashSet之類(lèi)的工具類(lèi)。應(yīng)該說(shuō)HashMap比較多一些,而且還是面試經(jīng)典題,平時(shí)也會(huì)多看看。開(kāi)始用的時(shí)候簡(jiǎn)單理解就是個(gè)鍵值對(duì)應(yīng)表,使用鍵來(lái)找數(shù)據(jù)比較方便。隨后深入了解后發(fā)現(xiàn)
這玩意還有點(diǎn)小奧秘,特別是新版本的JDK對(duì)HashMap的改成樹(shù)后,代碼都有點(diǎn)小復(fù)雜咯。
Set開(kāi)始用的較少,只是無(wú)意中在一個(gè)代碼中發(fā)現(xiàn)一個(gè)TreeSet,發(fā)現(xiàn)這個(gè)類(lèi)可以自帶順利,感覺(jué)蠻有點(diǎn)意思,才慢慢的發(fā)現(xiàn)這也是個(gè)好工具啊。
代碼寫(xiě)的多了就感覺(jué)到基礎(chǔ)的重要性,所以在此寫(xiě)一篇小文簡(jiǎn)單的整理一下對(duì)集合的一些知識(shí)。
好了,簡(jiǎn)單的整理一下:
•List:即是列表,支持?jǐn)?shù)組、鏈表的功能,一般都是線性的
•Map:即是映射表,存儲(chǔ)的是鍵與值的對(duì)應(yīng)關(guān)系
•Set:即是集合的意思,主要是用于排重?cái)?shù)據(jù)及排序
先來(lái)看看List
List是用于存放線性數(shù)據(jù)的一種窗口,比如:用于數(shù)組的ArrayList和用于鏈表的LinkedList。
ArrayList
這是一個(gè)數(shù)組列表,不過(guò)提供了自動(dòng)擴(kuò)容的功能,實(shí)現(xiàn)List接口,外部操作都是通過(guò)接口申明的方法訪問(wèn),這樣即安全又方便。
ArrayList的關(guān)鍵就是自動(dòng)擴(kuò)容,在對(duì)象初始化時(shí)可以設(shè)定初始容量,也可以按默認(rèn)的容量。如果對(duì)數(shù)組大小沒(méi)有特別明確可以不指定初始大小,如果明確的話可以指定一個(gè)大小,這樣減少動(dòng)態(tài)擴(kuò)容時(shí)產(chǎn)生的卡頓。說(shuō)到這就要說(shuō)一下擴(kuò)容是怎么實(shí)現(xiàn)的了,看下面的代碼:
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
grow是在ArrayList在添加元素或者一些容易檢查時(shí)會(huì)觸發(fā)的一個(gè)方法。主要過(guò)程:
1、得到數(shù)組的長(zhǎng)度,并對(duì)其進(jìn)行右移,這樣就相當(dāng)于oldCapacity/2,得到新的長(zhǎng)度
2、如果這個(gè)長(zhǎng)度小于最小容量那么直接就用最小容易
3、如果大于了最大容易則取一個(gè)最大值,這里會(huì)調(diào)用一個(gè)hugeCapacity方法,主要是比較minCapacity與MAX_ARRAY_SIZE的,如果minCapacity大于MAX_ARRAY_SIZE則取Integer.MAX_VALUE,否則就取MAX_ARRAY_SIZE,有意思的是MAX_ARRAY_SIZE取的是Integer.MAX_VALUE - 8;并不知道這樣做的意義是什么
4、最后就是調(diào)用一個(gè)復(fù)制方法將現(xiàn)有數(shù)復(fù)制到一個(gè)新的數(shù)組中。
因?yàn)橛羞@個(gè)復(fù)制過(guò)程,如果數(shù)組比較大,那么老是觸發(fā)擴(kuò)容當(dāng)然就會(huì)出現(xiàn)卡頓的情況。所以如果一開(kāi)始就知道最大值而且很容易增長(zhǎng)到這個(gè)值,那么開(kāi)始初始化時(shí)就指定大小會(huì)有一定的作用。
LinkedList
這是針對(duì)鏈表的工具類(lèi),鏈表的優(yōu)秀是添加刪除啥的比較快,但是查找會(huì)慢一些。
至于代碼好像也沒(méi)什么特別的,就是一串指針鏈接起來(lái),當(dāng)然Java中就使用對(duì)象來(lái)代替,建立一個(gè)Node的對(duì)象,Node本身指向了前一個(gè)Node和后一個(gè)Node,這就是鏈表的結(jié)構(gòu):
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
然后用兩個(gè)Node指向頭和尾就完成了,下面的代碼:
/** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;
看一個(gè)add操作:
/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
過(guò)往就是:
1、獲取到最后的Node并放在l中
2、創(chuàng)建一個(gè)新的Node,將數(shù)據(jù)取到這個(gè)Node中,創(chuàng)建過(guò)程會(huì)將新Node的prev指向l,這樣就接上了鏈
3、然后將last指向這個(gè)新Node
4、然判斷l(xiāng)是否null,如果是null說(shuō)明是空鏈表,新node就是第一個(gè)元素,這樣first也要指向newNode
5、如果不為空則將l的next指向newNode
6、累加計(jì)數(shù)器
刪除操作也是這種Node的前后Node指向移動(dòng)操作。
再來(lái)看看Map
Map是鍵與值做一個(gè)映射表的應(yīng)用,主要的實(shí)現(xiàn)類(lèi):HashMap,HashTable,TreeMap
HashMap和HashTable
使用hash算法進(jìn)行鍵值映射的就是HashMap啦,HashTable是帶有同步的線程安全的類(lèi),它們兩主要的區(qū)別就是這個(gè)。原理也類(lèi)似,都是通過(guò)桶+鏈來(lái)組合實(shí)現(xiàn)。桶是用來(lái)存Key的,而由于Hash碰撞的原因值需要用一個(gè)鏈表來(lái)存儲(chǔ)。
•桶的意義在于高效,通過(guò)Hash計(jì)算可以一步定位
•鏈表的意義在于存取重復(fù)hash的數(shù)據(jù)
具體的原理以前寫(xiě)過(guò)一篇《學(xué)習(xí)筆記:Hashtable和HashMap》
只不過(guò)看JDK1.8的HashMap換了存儲(chǔ)結(jié)構(gòu),采用紅黑樹(shù)的結(jié)構(gòu),這樣可能是解決鏈表查找效率問(wèn)題吧?具體沒(méi)有細(xì)研究。
TreeMap
看過(guò)TreeMap的代碼后發(fā)現(xiàn)還是使用的樹(shù)結(jié)構(gòu),紅黑樹(shù)。由于紅黑樹(shù)是有序的,所以自然帶排序功能。當(dāng)然也可通過(guò)comparator來(lái)指定比較方法來(lái)實(shí)現(xiàn)特定的排序。
因?yàn)椴捎昧藰?shù)結(jié)構(gòu)存儲(chǔ)那么添加和刪除數(shù)據(jù)時(shí)會(huì)麻煩一些,看一下put的代碼:
public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }
1、先是檢查根節(jié)點(diǎn)是否存在,不存在說(shuō)明是第一條數(shù)據(jù),直接作為樹(shù)的根
2、判斷是否存在比較器,如果存在則使用比較器進(jìn)行查找數(shù)據(jù)的存放位置,如果比較器返回結(jié)果小于0取左,大于0取右,否則直接替換當(dāng)前節(jié)點(diǎn)的值
3、如果不存在比較器則key直接與節(jié)點(diǎn)的key比較,比較和前面方法一樣
4、接下來(lái)就是在找到的parent上創(chuàng)建一個(gè)子節(jié)點(diǎn),并放入左或者右子節(jié)點(diǎn)中
5、fixAfterInsertion是對(duì)節(jié)點(diǎn)進(jìn)行著色
6、累加器處理
在remove操作時(shí)也會(huì)有點(diǎn)麻煩,除了刪除數(shù)據(jù)外,還要重新平衡一下紅黑樹(shù)。
另外,TreeMap實(shí)現(xiàn)了NavigableMap<K,V>接口,所以也提供了對(duì)數(shù)據(jù)集合的一些返回操作。
最后看看Set
Set主要是兩類(lèi)應(yīng)用:HashSet和TreeSet。
HashSet
字面意思很明確,使用了Hash的集合。這種集合的特點(diǎn)就是使用Hash算法存數(shù)據(jù),所以數(shù)據(jù)不重復(fù),存取都相對(duì)較快。怎么做到的呢?
public boolean add(E e) { return map.put(e, PRESENT)==null; }
原來(lái)是存在一個(gè)map對(duì)象中,再看map是個(gè)啥?
private transient HashMap<E,Object> map;
是個(gè)HashMap,了解HashMap的就明白,這樣的數(shù)據(jù)是不會(huì)重復(fù)的。因?yàn)榇嫒霑r(shí)是鼗對(duì)象本身作為Key來(lái)存的,所以在HashMap中只會(huì)存在一份。
了解了這點(diǎn)其他的東西就非常明白了。
TreeSet
這個(gè)集合是用于對(duì)集合進(jìn)行排序的,也就是除了帶有排重的能力外,還可以自帶排序功能。只不過(guò)看了TreeSet的代碼發(fā)現(xiàn),其就是在TreeMap的基礎(chǔ)實(shí)現(xiàn)的。更準(zhǔn)確的說(shuō)應(yīng)該是NavigableMap的派生類(lèi)。默認(rèn)不指定map情況下TreeSet是以TreeMap為基礎(chǔ)的。
public TreeSet() { this(new TreeMap<E,Object>()); }
所以,這里可能更關(guān)注的是TreeSet是如何排重呢?看一下add的方法吧:
public boolean add(E e) { return m.put(e, PRESENT)==null; }
和HashSet有點(diǎn)類(lèi)似,都是基于Map的特性來(lái)實(shí)現(xiàn)排重。確實(shí)簡(jiǎn)單而且有效。
以上就是小編為大家?guī)?lái)的多用多學(xué)之Java中的Set,List,Map詳解全部?jī)?nèi)容了,希望大家多多支持腳本之家~
相關(guān)文章
Spring MVC--攔截器實(shí)現(xiàn)和用戶(hù)登陸例子
本文主要介紹了Spring MVC--攔截器實(shí)現(xiàn)和用戶(hù)登陸例子,具有很好的參考價(jià)值,下面跟著小編一起來(lái)看下吧2017-03-03深入了解Java核心類(lèi)庫(kù)--String類(lèi)
這篇文章主要為大家詳細(xì)介紹了java String類(lèi)定義與使用的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能給你帶來(lái)幫助2021-07-07詳解springmvc之json數(shù)據(jù)交互controller方法返回值為簡(jiǎn)單類(lèi)型
這篇文章主要介紹了springmvc之json數(shù)據(jù)交互controller方法返回值為簡(jiǎn)單類(lèi)型,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2017-05-05SpringAOP+RabbitMQ+WebSocket實(shí)戰(zhàn)詳解
這篇文章主要介紹了SpringAOP+RabbitMQ+WebSocket實(shí)戰(zhàn)詳解,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-11-11java理論基礎(chǔ)Stream?reduce實(shí)現(xiàn)集合元素歸約
這篇文章主要為大家介紹了java理論基礎(chǔ)Stream?reduce實(shí)現(xiàn)集合元素歸約示例詳解有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步2022-03-03用Java編程輸出萬(wàn)年歷的功能實(shí)現(xiàn)
這篇文章主要介紹了用Java編程輸出萬(wàn)年歷的功能實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05