Java基礎(chǔ)學(xué)習(xí)總結(jié)

1、java基礎(chǔ)學(xué)習(xí)總結(jié)數(shù)據(jù)結(jié)構(gòu)是以某種形式將數(shù)據(jù)組織在一起的集合，它不僅存儲(chǔ)數(shù)據(jù)， 還支持訪問(wèn)和處理數(shù)據(jù)的操作o java提供了幾個(gè)能有效地組織和操作 數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)通常稱為java集合框架。在平常的 學(xué)習(xí)開(kāi)發(fā)中，靈活熟練地使用這些集合框架，可以很明顯地提高我們 的開(kāi)發(fā)效率，當(dāng)然僅僅會(huì)用還是不夠的，理解其中的設(shè)計(jì)思想與原理 才能更好地提高我們的開(kāi)發(fā)水平。下面是自己對(duì)java集合框架方面 的學(xué)習(xí)總結(jié)。一、概述二、collection 接口1 .list2.set3.queue三、map接口l. hashmap實(shí)現(xiàn)原理2其它map實(shí)現(xiàn)類四、其它集合類五、總結(jié)一、概述在java 2 z前

2、，java是沒(méi)有完整的集合框架的。它只有一些簡(jiǎn)單的可 以自擴(kuò)展的容器類，比如vector, stack, hashtable等。這些容器類在使用的過(guò)程中由于效率問(wèn)題飽受詬病，因此在java2中，java設(shè)計(jì) 者們進(jìn)行了大刀闊斧的整改，重新設(shè)計(jì)，于是就有了現(xiàn)在的集合框架。 需要注意的是，之前的那些容器類庫(kù)并沒(méi)有被弄用而是進(jìn)行了保留， 主要是為了向下兼容的目的，但我們?cè)谄綍r(shí)使用中還是應(yīng)該盡量少 用。:iterator maproducesicollodion <produces一 mapabslradmap.setqueuei sortedmap ;r abstraclcollectiwi

3、； “飛宗i;abslracllisl:一ab$tcads«t isortedsethashmaptretmapident fly hashmapunkedhashmaphashsettreeseiumcemshsetvecto<4stackweakhashmap |hasht3blecomparable <comparatorjabsfractsequentolbstj1代j| linkedlim |j die集合框架從上面的集合框架圖可以看到，java集合框架主要包括兩種類型的容器，一種是集合(collection),存儲(chǔ)一個(gè)元素集合，另一種是圖(map), 存儲(chǔ)鍵/

4、值對(duì)映射ocollection接口又有3種子類型,list>set和queue, 再下面是一些抽象類，最后是具體實(shí)現(xiàn)類，常用的有arraylist、 linkedlist> hashset> linkedhashset> hashmap> linkedhashmap 等 等。二、collection 接口collection接口是處理對(duì)象集合的根接口，其中定義了很多對(duì)元素進(jìn) 彳亍操作的方法，abstractcollection是提供collection部分實(shí)現(xiàn)的抽象 類。下圖展示了 collection接口中的全部方法。q sizefl: im0 a isempt

5、yo boc 2仃o * contoms(otect) hglrc jterdjoro ' zc0 a toarrayq object e 1 tcarr«y(td) t> 1 dd(e) bcokano a remove(objert) hoco a contoinsalt(c©uection <?) booh- 1 ddaji(colle<uon<? extendi e>) buc0 人 removeajicollection<?>) >aolrinq : removelftpredicate<? super

6、 e>): b 心r” ' reuinaji<cllection <? >)匕；o ' dearq vc d0' <rquat$(object) bcgbz ' hashcodeo e0= spirteratorq orator - e *e : streamo stre m e : pralwstremo 心亡5»n - £：collectionjg 口結(jié)構(gòu)其中，有幾個(gè)比較常用的方法，比如方法add()添加一個(gè)元素到集合 中，addall()將指定集合中的所有元素添加到集合中，contains()方法 檢測(cè)集合

7、中是否包含指定的元素，toarray()方法返冋一個(gè)表示集合的 數(shù)組。collection接口有三個(gè)子接口，下血詳細(xì)介紹。1 .listlist接口擴(kuò)展自collection,它可以定義一個(gè)允許重復(fù)的有序集合, 從list接口中的方法來(lái)看，list接口主要是增加了面向位置的操作, 允許在指定位置上操作元素，同吋增加了一個(gè)能夠雙向遍歷線性表的 新列表迭代器listiteratoro abstractlist類提供了 list接口的部分實(shí)現(xiàn), abstractsequentiallist擴(kuò)展口 abstractlist,主要是提供對(duì)鏈表的支持。 下面介紹list接口的兩個(gè)重要的具體實(shí)現(xiàn)類，也是我們

8、可能最常用的 類,arraylist 和 linkedlistoarraylist通過(guò)閱讀arraylist的源碼，我們可以很清楚地看到里面的邏輯，它 是用數(shù)組存儲(chǔ)元素的，這個(gè)數(shù)組可以動(dòng)態(tài)創(chuàng)建，如果元素個(gè)數(shù)超過(guò)了 數(shù)組的容量，那么就創(chuàng)建一個(gè)更大的新數(shù)組，并將當(dāng)前數(shù)組中的所有 元素都復(fù)制到新數(shù)組中。假設(shè)第一次是集合沒(méi)有任何元素，下面以插 入一個(gè)元素為例看看源碼的實(shí)現(xiàn)。1、方法add(e e)向集合屮添加指定元素。public boolean add(e e) ensurecapacityinternal(size + 1);/ increments modcount!elementdatasiz

9、e+ = e;return true;2、此方法主要是確定將要?jiǎng)?chuàng)建的數(shù)組大小。private void ensurecapacityinternal(int mincapacity) if(elementdata=defaulrcapacity_empty_elementdata) mincapacity = math.max(default_capacity, mincapacity);ensureexplicitcapacity(mincapacity);private void ensureexplicitcapacity(int mincapacity) modcount+;if (m

10、incapacity elementdata.length > 0)grow(mincapacity);3、最后是創(chuàng)建數(shù)組，可以明顯的看到先是確定了添加元素后的大小z后將元素復(fù)制到新數(shù)組屮oprivate void grow(int mincapacity) / overflow-conscious codeint oldcapacity 二 elementdata.length;int newcapacity = oldcapacity + (oldcapacity » 1);if (newcapacity - mincapacity < 0)newcapacity =

11、 mincapacity;訐(newcapacity max_array_size > 0)newcapacity = hugecapacity (mincapacity);/ mincapacity is usually close to size, so this is a win:elementdata 二 arrays.copyof(elementdata, newcapacity);linkedlist同樣，我們打開(kāi)linkedlist的源文件，不難看到linkedlist是在一個(gè) 鏈表中存儲(chǔ)元素。在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們知道鏈表和數(shù)組的最大區(qū)別在于它們對(duì) 元素的存儲(chǔ)方式的不

12、同導(dǎo)致它們?cè)趯?duì)數(shù)據(jù)進(jìn)行不同操作時(shí)的效率不 同，同樣，arraylist與linkedlist也是如此 實(shí)際使用中我們需要根 據(jù)特定的需求選用合適的類，如果除了在末尾外不能在其他位置插入 或者刪除元素，那么arraylist效率更高，如果需要經(jīng)常插入或者刪 除元素，就選擇linkedlisto2.setset接口擴(kuò)展自collection,它與list的不同之處在于，規(guī)定set的實(shí) 例不包含重復(fù)的元素。在一個(gè)規(guī)則集內(nèi)，一定不存在兩個(gè)相等的元素。 abstractset是一個(gè)實(shí)現(xiàn)set接口的抽象類，set接口有三個(gè)具體實(shí)現(xiàn) 類,分別是散列集hashset、鏈?zhǔn)缴⒋?j集linkedhashset和

13、樹(shù)形集 treeset o散列集hashset散列集hashset是一個(gè)用于實(shí)現(xiàn)set接口的具體類，可以使用它的無(wú) 參構(gòu)造方法來(lái)創(chuàng)建空的散列集，也可以由一個(gè)現(xiàn)有的集合創(chuàng)建散列 集。在散列集中，有兩個(gè)名詞需要關(guān)注，初始容量和客座率?？妥?是確定在增加規(guī)則集之前，該規(guī)則集的飽滿程度，當(dāng)元素個(gè)數(shù)超過(guò)了 容量與客座率的乘積時(shí)，容量就會(huì)自動(dòng)翻倍。下面看一個(gè)hashset的例子。/* author jackaltsc*/public class testhashset public static void main(string args) set<string> set = new has

14、hset<>();set.addc，lllllh);set.add(n22222n);set.add(n33333n);set.add(n44444h);set.add(n22222h);system.out.println(set.size();for (string e : set) system.out.println(e);從輸出結(jié)果我們可以看到，規(guī)則集里最后有4個(gè)元素，而且在輸出吋 元索還是無(wú)序的。鏈?zhǔn)缴⒘屑痩inkedhashsetlinkedhashset是用一個(gè)鏈表實(shí)現(xiàn)來(lái)擴(kuò)展hashset類，它支持對(duì)規(guī)則 集內(nèi)的元素排序。hashset中的元素是沒(méi)有被排序的，而 l

15、inkedhashset中的元索叮以按照它們插入規(guī)則集的順序提取。樹(shù)形集treesettreeset 擴(kuò)展口 abstractset,并實(shí)現(xiàn)了 navigableset, abstractset 擴(kuò)展 自abstractcollection,樹(shù)形集是一個(gè)有序的set,其底層是一顆樹(shù)， 這樣就能從set里面提取一個(gè)有序序列了。在實(shí)例化treeset時(shí)，我 們可以給treeset指定一個(gè)比較器comparator來(lái)指定樹(shù)形集中的元素 順序。樹(shù)形集中提供了很多便捷的方法。下面是一個(gè)treeset的例子。/* author jackaltsc*/public class testset public

16、static void main(string args) treeset<integer> set = new treeset<>();set.add(llll);set.add(2222);set.add(3333);set.add(4444);set.add(5555);system.out.println(set.first(); / 輸出第一個(gè)元素system.out.println(set.lower(3333); 小于 3333 的最大元素system.out.println(set.higher(2222); 大于 2222 的最大元素system.ou

17、t.println(set.floor(3333); /不大于 3333 的最大元素system.out.println(set.ceiling(3333); /不小于 3333 的最大元 素system.out.println(set.pollfirst(); 刪除第一個(gè)元素system.out.println(set.polllast(); 刪除最后一個(gè)元素system.out.println(set);3.queue隊(duì)列是一種先進(jìn)先岀的數(shù)據(jù)結(jié)構(gòu)，元素在隊(duì)列末尾添加，在隊(duì)列頭部 刪除。queue接口擴(kuò)展自collection,并提供插入、提取、檢驗(yàn)等操 作。v o queoe<e&g

18、t; a «w(e) bootf ana ' offer(e>: boolwn4 temoveo e0 a pairo ： e4 demento e a peeko equeue接口結(jié)構(gòu)上圖中，方法offer表示向隊(duì)列添加一個(gè)元素，poll()與remove()方法 都是移除隊(duì)列頭部的元素，兩者的區(qū)別在于如果隊(duì)列為空，那么poll() 返回的是null,而remove()會(huì)拋出一個(gè)異常。方法element()與peek() 主要是獲取頭部元素，不刪除。接口 deque,是一個(gè)擴(kuò)展自queue的雙端隊(duì)列，它支持在兩端插入和 刪除元素，因?yàn)閘inkedlist類實(shí)現(xiàn)了 de

19、que接口，所以通常我們可以 使用linkedlist來(lái)創(chuàng)建一個(gè)隊(duì)列。priorityqueue類實(shí)現(xiàn)了一個(gè)優(yōu)先隊(duì) 列，優(yōu)先隊(duì)列中元素被賦予優(yōu)先級(jí)，擁有高優(yōu)先級(jí)的先被刪除。* author jackaltsc*/public class testqueue public static void main(string args) queue<string> queue = new linkedlist<>(); queue.offer(h aaaa*'); queue.offer(nbbbbn); queue.offer(nccccn); queue.offer

20、(hddddn);while (queue.size() > 0) system.out.println(queue.remove() + ,u');三、map接口map,圖，是一種存儲(chǔ)鍵值對(duì)映射的容器類，在map中鍵可以是任 意類型的對(duì)象，但不能有重復(fù)的鍵，每個(gè)鍵都對(duì)應(yīng)一個(gè)值，真正存儲(chǔ) 在圖中的是鍵值構(gòu)成的條口。下血是接口 map的類結(jié)構(gòu)。v o map<< v>9 1 «e0 : ir.tq 4 iiemptyo ookan0 人 contain$key(object) : bocd、n8" conuinsvalue(obect>

21、cdoa gekobject) v®a puuk.v):vo remove(ofafectq * puta(l(m«p<? extends < ? extends v>): void o" derq voidq 1 keyseto set<k>o4 valueso collrctioc v -o" emrys«01 sei <eftvyrk, v> > o : entry* v>q 1 equ«l$(oct) b'-olriari a kashcodeo <r-o *

22、 getordefault(object v)o fore4<h(bicomumer<? super k. ? super v>) -o-jq replmeail(8；funct>on<? super 匕？ super v. ? e«eds v>) ho putlfabsenuk. v) : rmove(obect. object) b 二二-m 3 replaced. v, v): boolwo replace<k. v)o - computel(abent(k furxtio<i<? wper 良? extends v>

23、)9 : computeifprnent(i< bifunction<? uper 匕? super v. ? extends v>) computefk bifunct>on<? super 匕? super v, ? extends v>)o 3 merge(k. v. bifunctionc? super v. ? super v. ? extends v>):接口 map的結(jié)構(gòu)從上面這張圖中我們可以看到接口 map提供了很多查詢、更新和獲 取存儲(chǔ)的鍵值對(duì)的方法,更新包括方法clear()>put()>putall()>remo

24、ve() 等等，查詢方法包括containskey> containsvalue等等。map接口常 用的有三個(gè)具體實(shí)現(xiàn)類，分別是hashmap、linkedhashmap、treemap。l.hashmaphashmap是基于哈希表的map接口的非同步實(shí)現(xiàn)，繼承口 abstractmap, abstractmap是部分實(shí)現(xiàn)map接口的抽象類。在平時(shí)的 開(kāi)發(fā)中，hashmap的使用還是比較多的。我們知道arraylist主要是 用數(shù)組來(lái)存儲(chǔ)元素的，linkedlist是用鏈表來(lái)存儲(chǔ)的，那么hashmap 的實(shí)現(xiàn)原理是什么呢？先看下面這張圖：tabledhashmap原理.jpg在之前的版本

25、中，hashmap采用數(shù)組+鏈表實(shí)現(xiàn)，即使用鏈表處理沖 突，同一 hash值的鏈表都存儲(chǔ)在一個(gè)鏈表里。但是當(dāng)鏈表屮的元素 較多，即hash值相等的元素較多時(shí)，通過(guò)key值依次查找的效率較 低。to jdk1.8中，hashmap采用數(shù)組+鏈表+紅黑樹(shù)實(shí)現(xiàn)，當(dāng)鏈表長(zhǎng) 度超過(guò)閾值（8）時(shí)，將鏈表轉(zhuǎn)換為紅黑樹(shù)，這樣大大減少了查找時(shí) 間。卜'面主要通過(guò)源碼介紹一下它的實(shí)現(xiàn)原理。hashmap存儲(chǔ)元索的數(shù)組transient node<k,v> table;數(shù)組的元索類型是 nodevk,v>, node<k,v>繼承自 map.entry<k,v>,

26、表示鍵值對(duì)映射。static class node<k,v> implements map.entry<k,v> final int hash;final k key;v value;node<k,v> next;構(gòu)造函數(shù)(hash值鍵值下一個(gè)節(jié)點(diǎn))node(int hash, k key, v value, node<k,v> next) this.hash = hash;this.key = key;this.value = value;this.next = next;public final k getkeyo return key; p

27、ublic final v getvalue() return value; public final string tostringo return key + 1-n + value; public final int hashcode() return oashcode(key)objects.hashcode(value);public final v setvalue(v newvalue) v oldvalue = value;value = newvalue;return oldvalue;public final boolean equals(object o) if (o 二

28、二 this)return true;if (o instanceof map.entry) map.entry<?,?> e = (map.entry<?,?>)o;if (objects.equals(key, e.getkeyo) &&objects.equals(value, e.getvalue()return true;return false;接卜'來(lái)我們看b* hashmap的put操作。final v putval(int hash, k key, v value, boolean onlylfabsent,boolean ev

29、ict) node<k,v> tab; node<k,v> p; int n, i;if (tab = table) = null | (n = tab.length) = 0)n = (tab = resize().length; 如果沒(méi)有初始化則初始化tableif (p = tabi = (n 1) & hash) = null)這里(n-l)&hash是根據(jù)hash值得到這個(gè)元素在數(shù)組 中的位置(即下標(biāo))tabi = newnode(hash, key, value, null);如果數(shù)組該位置上沒(méi)有元素，就直接將該元素放到此數(shù)組 中的該位置上e

30、lse node<k,v> e; k k;第一節(jié)節(jié)點(diǎn)hash值同，且key值與插入key札i同if (p.hash = hash &&(k = p.key) = key | (key != null && key.equals(k)e 二 p;else if (p instanceof treenode)屬于紅黑樹(shù)處理沖突e = (treenode<k,v>)p).puttreeval(this, tab, hash,key, value);else /鏈表處理沖突for (int bincount = 0; +bincount) if

31、(e = p.next) = null) p.next = newnode(hash, key, value, null);if (bincount >= treeify_threshold新增節(jié)點(diǎn)后如果節(jié)點(diǎn)個(gè)數(shù)到達(dá)閾值，則 將鏈表轉(zhuǎn)換為紅黑樹(shù)treeifybin(tab, hash);break;if (e.hash = hash &&(k 二 e.key) = key | (key != null && key.equals(k)break;p = e;更新hash值和key值均相同的節(jié)點(diǎn)value值if (e != null) / existing

32、mapping for keyv oldvalue 二 e.value;訐(! only if absent | oldvalue = null)e.value 二 value;afternodeaccess(e);return oldvalue;+modcount;if (+size > threshold) resize();afternodelnsertion(evict); return null;接下來(lái)我們看下hashmap的get操作。final node<k,v> getnode(int hash, object key) node<k,v> tab

33、; node<k,v> first, e; int n; k k;訐(tab = table) != null && (n = tab.length) > 0 &&(first 二 tab(n - 1) & hash) != null) if (first.hash = hash && / always check first node(k = first.key) = key | (key != null && key.equals(k)return first;if (e = first.next)

34、!= null) 如果第一個(gè)節(jié)點(diǎn)是treenode,說(shuō)明采用的是數(shù)組+ 紅黑樹(shù)結(jié)構(gòu)處理沖突遍歷紅黑樹(shù)，得到節(jié)點(diǎn)值if (first instanceof treenode)return(treenode<k,v>)first).gettreenode(hash, key);do if (e.hash = hash &&(k = e.key) = key | (key != null &&key.equals(k)return e; while (e = e.next) != null);return null;到這里hashmap的大致實(shí)現(xiàn)原理應(yīng)該很

35、清楚了，有幾個(gè)需要關(guān)注的 重點(diǎn)是：hashmap存儲(chǔ)元素的方式以及根據(jù)hash值確定映射在數(shù)組 中的位置還有jdk 1.8 z后加入的紅黑樹(shù)的。在hashmap中要找到某個(gè)元素，需要根據(jù)key的hash值來(lái)求得對(duì)應(yīng) 數(shù)組屮的位置。對(duì)于任意給定的對(duì)象，只要它的hashcode()返冋值和 同，那么程序調(diào)用hash(int h)方法所計(jì)算得到的hash碼值總是相同的。 我們首先想到的就是把hash值對(duì)數(shù)組長(zhǎng)度取模運(yùn)算，這樣一來(lái)，元 索的分布相對(duì)來(lái)說(shuō)是比較均勻的。但是，“?！边\(yùn)算的消耗還是比較 大的，在hashmap中，(n - 1) & hash用于計(jì)算對(duì)象應(yīng)該保存在table 數(shù)組的哪個(gè)

36、索引處。hashmap底層數(shù)組的長(zhǎng)度總是2的n次方，當(dāng)數(shù) 組長(zhǎng)度為2的n次幕的時(shí)候，(n1) & hash算得的index相同的幾率 較小，數(shù)據(jù)在數(shù)組上分布就比較均勻，也就是說(shuō)碰撞的幾率小，相對(duì) 的，查詢的時(shí)候就不用遍歷某個(gè)位置上的鏈表，這樣查詢效率也就較 ?»u /。2. linkedhashmaplinkedhashmap繼承自hashmap,它主要是用鏈表實(shí)現(xiàn)來(lái)擴(kuò)展 hashmap類，hashmap中條目是沒(méi)有順序的，但是在linkedhashmap 中元素既可以按照它們插入圖的順序排序，也可以按它們最后一次被 訪問(wèn)的順序排序。3. treemaptreemap基丁紅黑

37、樹(shù)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，鍵值口j以使用comparable或 comparator 接口來(lái)排序。treemap 繼承口 abstractmap,同時(shí)實(shí)現(xiàn)了 接口 navigablemap,而接口 navigablemap 則繼承自 sortedmap o sortedmap是map的子接口，使用它可以確保圖中的條是排好序的。在實(shí)際使用中，如果更新圖時(shí)不需要保持圖中元索的順序，就使用hashmap,如果需要保持圖中元素的插入順序或者訪問(wèn)順序，就使用 linkedhashmap,如果需耍使圖按照鍵值排序，就使用treemapo四、其它集合類上面主要對(duì)java集合框架作了詳細(xì)的介紹，包括collection和map 兩個(gè)接口及它們的抽象類和常用的具體實(shí)現(xiàn)類，下面主要介紹一下其 它幾個(gè)特殊的集合類，vec