Java 數(shù)據(jù)結(jié)構(gòu)之 Map 學習總結(jié)
今天總結(jié)學習一下鍵值映射關(guān)系Map。
先了解下Map
Map 是一種把鍵對象和值對象映射的集合，它的每一個元素都包含一對鍵對象和值對象。 Map沒有繼承于Collection接口 從Map集合中檢索元素時，只要給出鍵對象，就會返回對應(yīng)的值對象。
Map是一個接口，實例化Map可以采用下面的方式：
HashMap//Map基于散列表的實現(xiàn)。插入和查詢“鍵值對”的開銷是固定的?？梢酝ㄟ^構(gòu)造器設(shè)置容量capacity和負載因子load factor，以調(diào)整容器的性能。
LinkedHashMap//類似于HashMap，但是迭代遍歷它時，取得“鍵值對”的順序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap慢一點。而在迭代訪問時發(fā)而更快，因為它使用鏈表維護內(nèi)部次序。
TreeMap//底層是二叉樹數(shù)據(jù)結(jié)構(gòu)，線程不同步，可用于給Map集合中的鍵進行排序。
HashTable//HashMap是Hashtable的輕量級實現(xiàn)，非線程安全的實現(xiàn)他們都實現(xiàn)了map接口，主要區(qū)別是HashMap鍵值可以為空null,效率可以高于Hashtable。
ConcurrentHashMap//ConcurrentHashMap通常只被看做并發(fā)效率更高的Map，用來替換其他線程安全的Map容器，比如Hashtable和Collections.synchronizedMap。
WeakHashMap//弱鍵(weak key)Map，Map中使用的對象也被允許釋放: 這是為解決特殊問題設(shè)計的。如果沒有map之外的引用指向某個“鍵”，則此“鍵”可以被垃圾收集器回收。
IdentifyHashMap//使用==代替equals()對“鍵”作比較的hash map
ArrayMap//ArrayMap是一個映射的數(shù)據(jù)結(jié)構(gòu)，它設(shè)計上更多的是考慮內(nèi)存的優(yōu)化，內(nèi)部是使用兩個數(shù)組進行數(shù)據(jù)存儲，一個數(shù)組記錄key的hash值，另外一個數(shù)組記錄Value值，它和SparseArray一樣，也會對key使用二分法進行從小到大排序，在添加、刪除、查找數(shù)據(jù)的時候都是先使用二分查找法得到相應(yīng)的index，然后通過index來進行添加、查找、刪除等操作，所以，應(yīng)用場景和SparseArray的一樣，如果在數(shù)據(jù)量比較大的情況下，那么它的性能將退化至少50%。
SparseArray//SparseArray比HashMap更省內(nèi)存，在某些條件下性能更好，主要是因為它避免了對key的自動裝箱（int轉(zhuǎn)為Integer類型），它內(nèi)部則是通過兩個數(shù)組來進行數(shù)據(jù)存儲的，一個存儲key，另外一個存儲value，為了優(yōu)化性能，它內(nèi)部對數(shù)據(jù)還采取了壓縮的方式來表示稀疏數(shù)組的數(shù)據(jù)，從而節(jié)約內(nèi)存空間。
Map的基本操作：
Object?put(Object?key,?Object?value)：?向集合中加入元素
Object?remove(Object?key)：?刪除與KEY相關(guān)的元素
void?putAll(Map?t)：??將來自特定映像的所有元素添加給該映像
void?clear()：從映像中刪除所有映射
Map使用
這里以最常用的HashMap為例
添加數(shù)據(jù)
Map hashMap =newHashMap<>();
for(inti =0; i < maxCount; i++) {??
? ?? hashMap.put(i,String.valueOf(i));
}
遍歷entrySet方式
long start = System.currentTimeMillis();
for(Map.Entry entry : hashMap.entrySet()) {? ? ?
? ? ? ? Integer key=entry.getKey();
??????? String value=entry.getValue();? ? ?
? ? ??? System.out.println("key: "+ key +"value: "+value);?
? }??
long end = System.currentTimeMillis();?
? System.out.println("for-each方式 cost time : "+ (end - start));
entrySet迭代器遍歷方式
long start1 = System.currentTimeMillis();
Iterator> entries = hashMap.entrySet().iterator();
while(entries.hasNext()) {
???? Map.Entry entry = entries.next();?
? ?? Integer key=entry.getKey();
??? Stringvalue=entry.getValue();? ?
? ? System.out.println("key: "+ key +"value: "+value);
???? }
?long end1 = System.currentTimeMillis();
System.out.println("entrySet iterator迭代器 cost time : "+ (end1 - start1));
鍵找值遍歷
long end1 = System.currentTimeMillis();
?? System.out.println("iterator迭代器 cost time : "+ (end1 - start1));
??? long start2 = System.currentTimeMillis();
?? for (Integerkey: hashMap.keySet()) {? ?
? ? String value= hashMap.get(key);? ?
??? System.out.println("key: "+key+"value: "+value);
}
?? long end2 = System.currentTimeMillis();
? System.out.println("鍵找值遍歷 cost time : "+ (end2 - start2));
keySet迭代器遍歷
long start3 = System.currentTimeMillis();
Iterator iterator=hashMap.keySet().iterator();
while(iterator.hasNext()) {? ? ??
???? Integerkey=iterator.next();? ? ?
? ?? Stringvalue=hashMap.get(key);? ? ?
? ? System.out.println("key: "+key+"value: "+value);? ?
}
long end3 = System.currentTimeMillis();
System.out.println("keySet iterator迭代器 cost time : "+ (end3 - start3));
上述四種情況執(zhí)行結(jié)果如下：
總結(jié)：
主要重新熟悉一下Map這種數(shù)據(jù)結(jié)構(gòu)，以及更好的在以后的編程中選擇更合適的方式來進行key-value存儲。
