當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

java集合大家族之Map

發布時間：2023/12/9 编程问答 32 豆豆

生活随笔收集整理的這篇文章主要介紹了 java集合大家族之Map 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

Map

Map也被稱為映射表（關聯數組），使得你可以用鍵來查找對象，鍵所關聯的對象被稱為值，因此你可以使用鍵來找值，用對象來查找對象。Map保存的鍵不重復，如果有相同的鍵被加入，那么原來的值將被加入的值覆蓋。鍵必須是唯一的，而值可以有重復。標準的java類庫中包含了Map的幾種基本實現，包括：HashMap、TreeMap、LinkedHashMap、WeakHashMap、ConcurrentHashMap、IdentityHashMap。它們都有同樣的基本接口Map，但是行為特征各不相同，這表現在效率、鍵值對的保存及呈現次序、對象的保存周期、映射表如何在多線程程序中工作和判斷“鍵”等價的策略等方面。

HashMap：和HashSet一樣，以散列的方式來存儲數據，提供了快速查找的能力（它取代了HashTable）。插入和查詢“鍵值對”的開銷是固定的。可以通過構造方法的容量和負載因子，以調整容器的性能。
LinkHashMap: 類似于HashMap，但是迭代遍歷它時，取得“鍵值對”的順序是其插入順序，或者是最近最少使用（LRU）的次序。查詢時只比HashMap慢一點；而在迭代訪問時反而更快，因為它使用了鏈表維護內部次序。
TreeMap：基于紅黑樹的實現。查看“鍵”或“鍵值對”時，它們會被排序（次序由Comparable或Comparator決定）。TreeMap的特點在于所得到的結果是經過排序的。TreeMap是唯一的帶有subMap()方法的Map,它可以返回一個子數。
WeakHashMap：弱鍵（weak key）映射，允許釋放映射表所指向的對象；這是為解決某類特殊問題而設計的。如果映射表之外沒有引用指向這個”鍵“，則該”鍵“可以被垃圾收集器（GC）回收。
ConcurrentHashMap：一種線程安全的Map，它不涉及同步加鎖。
IdentityHashMap：使用==代替equals()，對“鍵”進行比較的散列映射。專為解決某類特殊問題而設計的。

帶有Hash字段的映射類都是利用散列來存儲元素的，如果“鍵”被用于散列Map，那么它必須還具有恰當的hashCode方法；而TreeMap則是利用樹來存儲”鍵“的，該鍵必須實現Comparable接口。

HashMap如何進行快速查找：

HashMap專門對速度進行了優化，那么HashMap是如何在映射表中快速查找鍵對象呢，如果使用線性查找（for循環）那執行速度會相當地慢。因此HashMap使用了特殊的值散列碼，來取代對鍵的緩慢搜索。散列碼是通過將對象的某些信息進行轉換而生成的，散列碼是”相對唯一”的，是int類型。通過根類Object中的hashCode()方法就可以獲取散列碼，所以每個對象都能產生散列碼。HashMap就是使用對象的hashCode()進行快速查詢，此方法能夠顯著提高性能。因此散列是映射中存儲元素時最常用的方式。 散列的價值在于速度：散列使得查詢得以快速進行。

那么鍵值是如何利用散列進行快速查詢的呢？首先我們必須要知道存儲一組數據最快的數據結構是數組，我們可以通過數組下標就可以立即得到該數據，所以我可以通過數組來存儲鍵的信息。但是Map中保存鍵值的數量是不確定的，而數組的容量卻是固定的，這不就沖突了嗎？其實數組并不是保存鍵本身。而是通過鍵對象生成一個數字，將其作為數組的下標。這個數字就是散列碼。也是就是我們上面所說的，由hashCode()方法生成()。

每個對象的散列碼是”相對唯一”的，如果有1w個對象就差不多有1w個散列碼，難道我們就必須創建1w容量的數組？因為hashCode()返回的是int類型的值，所以我只要把散列值除以一個特定數字，結果的余數就是數組的下標，而這個特定數字就是數組容量的大小。如果把余數當作數組的下標，那么不同的鍵就就可能產生相同的下標。也就是說，可能產生沖突。因此，數組多大就不重要了，任何鍵總能在數組中找到它的位置。

于是查詢一個值的過程首先就是計算散列碼，然后使用散列碼查詢數組。而數組中的元素并不是存儲鍵對象本身，而是存儲是鏈表，鏈表中存儲的是所有余數相同的鍵對象。然后根據鏈表中的鍵對象使用equal()方法進行線性查詢。這部分的查詢自然會比較慢，但是，如果散列函數好的話，數組每個位置就只有較少的值。

利用hashCode值快速跳到數組某個位置，然后對該位置的鏈表進行較少的線性比較，這就是HashMap之所以快的原因，就如下表所示：

理解了散列的原理，我們就能夠實現一個簡單的散列Map了：

/** * 簡單的Map容器,繼承AbstractMap省去我們重寫很多通用的方法 * */ public class SimpleHashMap<K, V> extends AbstractMap<K, V> {/*** 實現Map.Entry接口，用于存儲鍵值對的節點*/class Node<K, V> implements Map.Entry<K, V> {private K key;private V value;public Node(K key, V value) {this.key = key;this.value = value;}@Overridepublic K getKey() {return key;}@Overridepublic V getValue() {return value;}@Overridepublic V setValue(V v) {V result = v;value = v;return result;}@Overridepublic int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}/*** 只有鍵和值一樣才相等*/@Overridepublic boolean equals(Object obj) {if (obj == this)return true;if (obj instanceof Map.Entry) {Map.Entry<K, V> e = (Map.Entry<K, V>) obj;//key和value都相等才返回trueif (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;}@Overridepublic String toString() {return key + "=" + value;}}/*** 使用2的次方作為哈希數組的大小*/static final int SIZE = 512;/*** 聲明了一個LinkedList類型的數組，LinkedList存放的是Node類型的鍵值對元素*/LinkedList<Node<K, V>>[] buckets = new LinkedList[SIZE];/*** 繼承Map接口，需要實現entrySet方法，用于返回所有的鍵值對集合。*/@Overridepublic Set<Entry<K, V>> entrySet() {Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();for (LinkedList<Node<K, V>> bucket : buckets) {if (bucket == null) continue;for (Node<K, V> mpair : bucket) {set.add(mpair);}}return set;}/*** 把鍵值對存入Map中*/@Overridepublic V put(K key, V value) {V oldValue = null;//用key的hashCode余數作為數組的下標int index = Math.abs(key.hashCode()) % SIZE;if (buckets[index] == null) {buckets[index] = new LinkedList<Node<K, V>>();}//獲取數組中LinkedList對象LinkedList<Node<K, V>> bucket = buckets[index];//創建鍵值對節點,存放鍵值對對象Node<K, V> pair = new Node<K, V>(key, value);boolean found = false;ListIterator<Node<K, V>> it = bucket.listIterator();//遍歷LinkedList中是否有相等的keywhile (it.hasNext()) {Node<K, V> iPair = it.next();if (iPair.getKey().equals(key)) {//有相等的key//取出老value用于返回oldValue = iPair.getValue();//取代原來的鍵值對對象it.set(pair);found = true;break;}}//如果LinkedList中沒有key于之相等，則把新的鍵值對對象加入。if (!found) {buckets[index].add(pair);}return oldValue;}/*** 根據key獲取value*/public V get(Object key) {//用key的hashCode余數作為數組的下標int index = Math.abs(key.hashCode()) % SIZE;if (buckets[index] == null) return null;//返回和key相等的value對象for (Node<K, V> iPair : buckets[index]) {if (iPair.getKey().equals(key)) {return iPair.getValue();}}return null;}public static void main(String[] args) {SimpleHashMap<String, String> m = new SimpleHashMap<>();m.put("A", "C");m.put("B", "C++");m.put("C", "Java");m.put("D", "C#");m.put("E", "Go");m.put("E", "Swift");System.out.println(m);System.out.println("-----------------");System.out.println(m.get("A"));System.out.println("-----------------");System.out.println(m.entrySet());}/*Output:{B=C++, A=C, C=Java, D=C#, E=Swift}-----------------C-----------------[B=C++, A=C, C=Java, D=C#, E=Swift]*/ }

散列表中數組的每個元素我們稱為”槽位”(slot) 也稱為“桶位”(bucket)，所以我們將表示實際散列表中的數組命令為bucket。桶的數量通常為2的整數次方。對現代處理器來說，除法與求余是最慢的操作。使用2的整數次方長度的散列表，可用掩碼代替除法。因為get()是使用最多的操作，求余數的%操作是其開銷最大的部分，而使用2的整數次方可以消除此開銷。

get()和put()方法都用相同的方式計算在buckets數組中的索引，如果此位置有LinkedList存在，就對其查詢。注意上面例子的實現并不意味著對性能進行了調優；它只是想要展示散列映射表執行的各種操作。你可以通過瀏覽HashMap的代碼，看到一個調優過程的實現。比如我們可以修改Node使其成為一種自包含的單向鏈表（每個Node都有指向下一個的Node的引用），從而不用對每個桶位都使用LinkedList。

下面是用自定義的單向鏈表代替LinkedList：

public class SimpleHashMap<K, V> extends AbstractMap<K, V> {/*** 用于存儲鍵值對的節點*/class Node<K, V> implements Map.Entry<K, V> {private K key;private V value;Node<K, V> next;//用于指向下一個節點public Node(K key, V value, Node<K, V> next) {this.key = key;this.value = value;this.next = next;}@Overridepublic K getKey() {return key;}@Overridepublic V getValue() {return value;}@Overridepublic V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}@Overridepublic int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}/*** 只有鍵和值一樣才相等*/@Overridepublic boolean equals(Object obj) {if (obj == this)return true;if (obj instanceof Map.Entry) {Map.Entry<K, V> e = (Map.Entry<K, V>) obj;//key和value都相等才返回trueif (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;}@Overridepublic String toString() {return key + "=" + value;}}/*** 使用2的整數次方作為數組的大小*/static final int SIZE = 512;/*** 聲明了一個Node節點的數組*/Node<K, V>[] buckets = new Node[SIZE];/*** 繼承Map接口，需要實現entrySet方法，用于返回所有的鍵值對集合。*/@Overridepublic Set<Entry<K, V>> entrySet() {Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();for (Node bucket : buckets) {for (Node<K, V> e = bucket; e != null; e = e.next) {set.add(e);}}return set;}/*** 把鍵值對存入Map中*/@Overridepublic V put(K key, V value) {//用key的hashCode余數作為數組的下標int index = Math.abs(key.hashCode()) % SIZE;for (Node<K, V> e = buckets[index]; e != null; e = e.next) {//桶內有Node節點，并且key值相等則進行替換if (key.equals(e.key)) {V oldValue = e.value;e.value = value;return oldValue;}}//如果桶內沒有Node節點或桶內有Node節點但是key值都不匹配//那么就創建一個新的Node節點，并插入鏈表的頭部buckets[index] = new Node<K, V>(key, value, buckets[index]);return null;}/*** 根據key獲取value*/public V get(Object key) {//用key的hashCode余數作為數組的下標int index = Math.abs(key.hashCode()) % SIZE;for (Node<K, V> e = buckets[index]; e != null; e = e.next) {K eKey = e.key;if (key.equals(eKey)) {return e.value;}}return null;}public static void main(String[] args) {SimpleHashMap<String, String> m = new SimpleHashMap<>();m.put("A", "C");m.put("B", "C++");m.put("C", "Java");m.put("D", "C#");m.put("E", "Go");m.put("E", "Swift");System.out.println(m);System.out.println("-----------------");System.out.println(m.get("A"));System.out.println("-----------------");System.out.println(m.entrySet());}/*Output:{B=C++, A=C, C=Java, D=C#, E=Swift}-----------------C-----------------[B=C++, A=C, C=Java, D=C#, E=Swift]*/ }

如何設計hashCode?

在明白了如何散列之后，如何編寫自己的hashCode()就有十分重要的意義。設計hashCode()時最重要的因數是：如何何時，對同一個對象調用hashCode()都應該生成同樣的值。如果在將一個對象用put()添加進去HashMap時產生一個hashCode()值,而用get()取出時卻產生了另一個hashCode()值，那就就無法重現取得該對象了。所以，如何你的hashCode()方法依賴于對象中易變的數據，就要當心了，因為此數據發送變化時，hashCode()就會產生一個不同的散列碼，相當于產生了一個不同的鍵。

此外，也不應該使用hashCode()依賴于具有唯一性的對象信息，尤其是使用this的值，因為這樣做無法生存一個新的鍵，使之與put()中原始的鍵值對中的鍵相同。默認Object的hashCode()的值映射的就是對象的地址。所以我們應該使用對象內有意義的識別信息。

以String為例，String有個特點只要字符串一樣，那么不管多少個String對象，它們的hashCode的值都是一樣的：

String s1=new String("Hello");String s2=new String("Hello");String s3=new String("Hello");System.out.println(s1.hashCode()+" "+s2.hashCode()+" "+s3.hashCode());

輸出的結果都為69609650，很明顯String的hashCode的值是基于String內容的，下面是String類重寫hashCode()的代碼：

public int hashCode() {int h = hash;if (h == 0 && value.length > 0) {char val[] = value;for (int i = 0; i < value.length; i++) {h = 31 * h + val[i];}hash = h;}return h;}

我們可以看出String的hashCode值就是基于每個字符產生的。

因此，想要使hashCode()實用，它必須速度快，并且必須有意義。也就是說，它必須基于對象的內容生成散列碼。散列碼不必是對一無二的（應該更關注生成速度，而不是唯一性），但是通過hashCode()和equals(),必須能夠完全確定對象的身份。散列碼的生成范圍并不重要，只要int即可。好的hashCode()應該產生分布均勻的散列碼。如果散列碼都集中在一塊，那么HashMap或者HashSet在某些區域的負載會很重，這樣就不如分布均勻的散列函數快。

在Effective Java Programming Language Guide這本書中，為怎樣一份像樣的hashCode()給出了基本的指導：

給int變量result賦予某個非零常量值，例如17

為對象內每個有意義的域f（即每個可以做equals()操作的域）計算出一個int散列嗎hashCode：

如果是數組類型則對每個元素應用上述規則

合并計算得到散列碼
result=37*result+hashCode；

返回result。

下面便是遵循這些指導的一個例子：

public class Animal {private String name;private int age;private char gender;public Animal(String name, int age, char gender) {this.name = name;this.age = age;this.gender = gender;}@Overridepublic String toString() {return "Animal{" +"name='" + name + '\'' +", age=" + age +", gender=" + gender +", hashCode=" + hashCode() +'}'+"\n";}@Overridepublic int hashCode() {int result = 17;result = 37 * result + name.hashCode();result = 37 * result + age;result = 37 * result + (int) gender;return result;}@Overridepublic boolean equals(Object o) {if (!(o instanceof Animal)) return false;Animal animal = (Animal) o;if (age != animal.age) return false;if (gender != animal.gender) return false;return name.equals(animal.name);}public static void main(String[] args) {Map<Animal, Integer> map = new HashMap<Animal, Integer>();for (int i = 0; i < 5; i++) {Animal animal = new Animal("Jack", i, '男');map.put(animal, i);}System.out.println(map);}/*Output:{Animal{name='Jack', age=4, gender=男, hashCode=-1144106977}=4, Animal{name='Jack', age=3, gender=男, hashCode=-1144107014}=3, Animal{name='Jack', age=0, gender=男, hashCode=-1144107125}=0, Animal{name='Jack', age=2, gender=男, hashCode=-1144107051}=2, Animal{name='Jack', age=1, gender=男, hashCode=-1144107088}=1}*/ }

上面的例子中hashCode和equals()都基于Animal中三個字段來生成結果的，只要發們其中一個發生改變，就會產生不同的結果。

HashMap的性能因子

我們可以通過手工調整HashMap來提高性能，從而滿足我們特點應用的需求。為了調整HashMap時讓你理解性能問題，需求了解以下的術語：

容量：表中的桶的數量（數組的長度）
初始容量：表在創建時所擁有的的桶位數。HashMap和HashSet創建時都可以指定初始容量。
尺寸：表中當前存儲的元素數量。
負載因子：尺寸/容量。

空表的負載因子是0，而半滿表的負載因子是0.5以此類推。負載輕（負載因子小）的表產生沖突的可能性小，因此對于插入和查找都是最理想的（但是會減慢使用迭代器進行遍歷的過程）。HashMap和HashSet都具有指定負載因子的構造器：

public HashMap(int capacity, float loadFactor) {this(capacity);if (loadFactor <= 0 || Float.isNaN(loadFactor)) {throw new IllegalArgumentException("Load factor: " + loadFactor);}/** Note that this implementation ignores loadFactor; it always uses* a load factor of 3/4. This simplifies the code and generally* improves performance.*/}

表示當負載情況達到該負載因子的水平時，容器將自動增加其容量（桶位數），HashMap中的實現方式是使容量（數組大小）變成之前的2倍，并重新將現有的對象分布到新的桶位中（這被稱為再散列）。

HashMap使用默認的負載因子是0.75，只有當表達到四分之三滿時，才進行散列：

static final float DEFAULT_LOAD_FACTOR = .75F;

這個因子在時間和空間代價之間達到了平衡。更高的負載因子可以降低表（數組）所需的空間，但是會增加查找代價，而查找操作是我們用得最多的操作（包括put()和put()）。而更低的負載因子就會提高表（數組）所需的空間，造成空間浪費，迭代速度變慢。所以負載因子應該設置成合理的值。

參考

《Thinking in Java》

總結

以上是生活随笔為你收集整理的java集合大家族之Map的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Hadoop3.0 WordCount测
下一篇： GB28181协议之录像回放