Hashmap

定義

Hashmap是map接口的常用實(shí)現(xiàn)類。
Hashmap中put方法的源碼如下：

    public V put(K key, V value)   
    {   
     // 如果 key 為 null，調(diào)用 putForNullKey 方法進(jìn)行處理  
     if (key == null)   
         return putForNullKey(value);   
     // 根據(jù) key 的 keyCode 計(jì)算 Hash 值  
     int hash = hash(key.hashCode());   
     // 搜索指定 hash 值在對(duì)應(yīng) table 中的索引  
         int i = indexFor(hash, table.length);  
     // 如果 i 索引處的 Entry 不為 null，通過(guò)循環(huán)不斷遍歷 e 元素的下一個(gè)元素  
     for (Entry<K,V> e = table[i]; e != null; e = e.next)   
     {   
         Object k;   
         // 找到指定 key 與需要放入的 key 相等（hash 值相同  
         // 通過(guò) equals 比較放回 true）  
         if (e.hash == hash && ((k = e.key) == key   
             || key.equals(k)))   
         {   
             V oldValue = e.value;   
             e.value = value;   
             e.recordAccess(this);   
             return oldValue;   
         }   
     }   
     // 如果 i 索引處的 Entry 為 null，表明此處還沒(méi)有 Entry   
     modCount++;   
     // 將 key、value 添加到 i 索引處  
     addEntry(hash, key, value, i);   
     return null;   
    }

上面程序中用到了一個(gè)重要的內(nèi)部接口：Map.Entry，每個(gè) Map.Entry 其實(shí)就是一個(gè) key-value 對(duì)。從上面程序中可以看出：當(dāng)系統(tǒng)決定存儲(chǔ) HashMap 中的 key-value 對(duì)時(shí)，完全沒(méi)有考慮 Entry 中的 value，僅僅只是根據(jù) key 來(lái)計(jì)算并決定每個(gè) Entry 的存儲(chǔ)位置。這也說(shuō)明了前面的結(jié)論：我們完全可以把 Map 集合中的 value 當(dāng)成 key 的附屬，當(dāng)系統(tǒng)決定了 key 的存儲(chǔ)位置之后，value 隨之保存在那里即可。

所以，若Hashmap在插入key時(shí)，
HashMap會(huì)先用key的hash值來(lái)檢查是否發(fā)生了hash碰撞，也就是對(duì)應(yīng)的位置是否為空。如果原本已經(jīng)存在對(duì)應(yīng)的key，則直接改變對(duì)應(yīng)的value，并返回舊的value，而在判斷key是否存在的時(shí)候是先比較key的hashCode，再比較相等或equals的。

Hashmap的構(gòu)造

HashMap 包含如下幾個(gè)構(gòu)造器：
* HashMap()：構(gòu)建一個(gè)初始容量為 16，負(fù)載因子為 0.75 的 HashMap。
* HashMap(int initialCapacity)：構(gòu)建一個(gè)初始容量為 initialCapacity，負(fù)載因子為 0.75 的 HashMap。
* HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負(fù)載因子創(chuàng)建一個(gè) HashMap。

對(duì)于 HashMap 及其子類而言，它們采用 Hash 算法來(lái)決定集合中元素的存儲(chǔ)位置。當(dāng)系統(tǒng)開(kāi)始初始化 HashMap 時(shí)，系統(tǒng)會(huì)創(chuàng)建一個(gè)長(zhǎng)度為 capacity 的 Entry 數(shù)組，這個(gè)數(shù)組里可以存儲(chǔ)元素的位置被稱為“桶（bucket）”，每個(gè) bucket 都有其指定索引，系統(tǒng)可以根據(jù)其索引快速訪問(wèn)該 bucket 里存儲(chǔ)的元素。

無(wú)論何時(shí)，HashMap 的每個(gè)“桶”只存儲(chǔ)一個(gè)元素（也就是一個(gè) Entry），由于 Entry 對(duì)象可以包含一個(gè)引用變量（就是 Entry 構(gòu)造器的的最后一個(gè)參數(shù)）用于指向下一個(gè) Entry，因此可能出現(xiàn)的情況是：HashMap 的 bucket 中只有一個(gè) Entry，但這個(gè) Entry 指向另一個(gè) Entry ——這就形成了一個(gè) Entry 鏈。如圖 1 所示：


Hashmap的讀取

當(dāng) HashMap 的每個(gè) bucket 里存儲(chǔ)的 Entry 只是單個(gè) Entry ——也就是沒(méi)有通過(guò)指針產(chǎn)生 Entry 鏈時(shí)，此時(shí)的 HashMap 具有最好的性能：當(dāng)程序通過(guò) key 取出對(duì)應(yīng) value 時(shí)，系統(tǒng)只要先計(jì)算出該 key 的 hashCode() 返回值，在根據(jù)該 hashCode 返回值找出該 key 在 table 數(shù)組中的索引，然后取出該索引處的 Entry，最后返回該 key 對(duì)應(yīng)的 value 即可?？?HashMap 類的 get(K key) 方法代碼：

    public V get(Object key)   
    {   
     // 如果 key 是 null，調(diào)用 getForNullKey 取出對(duì)應(yīng)的 value   
     if (key == null)   
         return getForNullKey();   
     // 根據(jù)該 key 的 hashCode 值計(jì)算它的 hash 碼  
     int hash = hash(key.hashCode());   
     // 直接取出 table 數(shù)組中指定索引處的值，  
     for (Entry<K,V> e = table[indexFor(hash, table.length)];   
         e != null;   
         // 搜索該 Entry 鏈的下一個(gè) Entr   
         e = e.next)         // ①  
     {   
         Object k;   
         // 如果該 Entry 的 key 與被搜索 key 相同  
         if (e.hash == hash && ((k = e.key) == key   
             || key.equals(k)))   
             return e.value;   
     }   
     return null;   
    }

從上面代碼中可以看出，如果 HashMap 的每個(gè) bucket 里只有一個(gè) Entry 時(shí)，HashMap 可以根據(jù)索引、快速地取出該 bucket 里的 Entry；在發(fā)生“Hash 沖突”的情況下，單個(gè) bucket 里存儲(chǔ)的不是一個(gè) Entry，而是一個(gè) Entry 鏈，系統(tǒng)只能必須按順序遍歷每個(gè) Entry，直到找到想搜索的 Entry 為止——如果恰好要搜索的 Entry 位于該 Entry 鏈的最末端（該 Entry 是最早放入該 bucket 中），那系統(tǒng)必須循環(huán)到最后才能找到該元素。
由此，我們可以在創(chuàng)建 HashMap 時(shí)根據(jù)實(shí)際需要適當(dāng)?shù)卣{(diào)整 load factor 的值；如果程序比較關(guān)心空間開(kāi)銷、內(nèi)存比較緊張，可以適當(dāng)?shù)卦黾迂?fù)載因子；如果程序比較關(guān)心時(shí)間開(kāi)銷，內(nèi)存比較寬裕則可以適當(dāng)?shù)臏p少負(fù)載因子。

Hashmap的遍歷

public class HashMapDemo {  
  
    public static void main(String[] args) {  
          
        HashMap<String, String> hashMap = new HashMap<String, String>();  
        hashMap.put("cn", "中國(guó)");  
        hashMap.put("jp", "日本");  
        hashMap.put("fr", "法國(guó)");  
          
        System.out.println(hashMap);  
        System.out.println("cn:" + hashMap.get("cn"));  
        System.out.println(hashMap.containsKey("cn"));  
        System.out.println(hashMap.keySet());  
        System.out.println(hashMap.isEmpty());  
          
        hashMap.remove("cn");  
        System.out.println(hashMap.containsKey("cn"));  
          
        //采用Iterator遍歷HashMap  
        Iterator it = hashMap.keySet().iterator();  
        while(it.hasNext()) {  
            String key = (String)it.next();  
            System.out.println("key:" + key);  
            System.out.println("value:" + hashMap.get(key));  
        }  
          
        //遍歷HashMap的另一個(gè)方法  
        Set<Entry<String, String>> sets = hashMap.entrySet();  
        for(Entry<String, String> entry : sets) {  
            System.out.print(entry.getKey() + ", ");  
            System.out.println(entry.getValue());  
        }  
    }  
}

Maphash中的一些方法

Maphash.keySet獲得map的鍵集合

Maphash中的紅黑樹(shù)（待）

JDK 1.8 以前 HashMap 的實(shí)現(xiàn)是 數(shù)組+鏈表，即使哈希函數(shù)取得再好，也很難達(dá)到元素百分百均勻分布。

當(dāng) HashMap 中有大量的元素都存放到同一個(gè)桶中時(shí)，這個(gè)桶下有一條長(zhǎng)長(zhǎng)的鏈表，這個(gè)時(shí)候 HashMap 就相當(dāng)于一個(gè)單鏈表，假如單鏈表有 n 個(gè)元素，遍歷的時(shí)間復(fù)雜度就是 O(n)，完全失去了它的優(yōu)勢(shì)。
針對(duì)這種情況，JDK 1.8 中引入了 紅黑樹(shù)（查找時(shí)間復(fù)雜度為 O(logn)）來(lái)優(yōu)化這個(gè)問(wèn)題。

shixinzhang

練習(xí)

leetcode no.599
使用哈希索引找最小索引

public class no599 {
    public static String[] findRestaurant(String[] list1, String[] list2) {
        List<String> buffer = null;
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < list1.length; i++){
            map1.put(list1[i], i);
        }
        for (int i = 0; i < list2.length; i++){
            map2.put(list2[i], i);
        }

        for (int i = 0; i < list1.length; i++){
            if(map2.containsKey(list1[i])){
                int sum = map1.get(list1[i]) + map2.get(list1[i]);
                if(sum < min){
                    min = sum;
                    buffer = new ArrayList<String>();
                    buffer.add(list1[i]);
                }
                else if(sum == min)
                    buffer.add(list1[i]);
            }
        }
        return buffer.toArray(new String[buffer.size()]);
    }

    public static void main(String[] args){
        String[] a = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
        String[] b = {"KFC", "Shogun", "Burger King"};
        System.out.println(Arrays.toString(findRestaurant(a, b)));
    }
}

no.594

public class no594 {
    public static int findLHS(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
//            if(!map.containsKey(nums[i]))
//                map.put(nums[i], 1);
//            else {
            int value = map.getOrDefault(nums[i], 0);
            value++;
            map.put(nums[i], value);
        }
        int length = 0;
        for (int num: map.keySet()){
            if(map.containsKey(num + 1))
                length = Math.max(length, map.get(num) + map.get(num + 1));
        }

        return length;
    }

    public static void main(String[] args){
        int[] nums = {1,3,2,2,5,2,3,7};
        System.out.println(findLHS(nums));
    }
}

http://www.cnblogs.com/chenssy/p/3521565.html

HashSet和HashMap的區(qū)別

  1. HashMap實(shí)現(xiàn)了Map接口 HashSet實(shí)現(xiàn)了Set接口
  2. HashMap儲(chǔ)存鍵值對(duì) HashSet僅僅存儲(chǔ)對(duì)象
  3. 使用put()方法將元素放入map中 使用add()方法將元素放入set中
  4. HashMap中使用鍵對(duì)象來(lái)計(jì)算hashcode值 HashSet使用成員對(duì)象來(lái)計(jì)算hashcode值，對(duì)于兩個(gè)對(duì)象來(lái)說(shuō)hashcode可能相同，所以equals()方法用來(lái)判斷對(duì)象的相等性，如果兩個(gè)對(duì)象不同的話，那么返回false
  5. HashMap比較快，因?yàn)槭鞘褂梦ㄒ坏逆I來(lái)獲取對(duì)象 HashSet較HashMap來(lái)說(shuō)比較慢
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 實(shí)際上，HashSet 和 HashMap 之間有很多相似之處，對(duì)于 HashSet 而言，系統(tǒng)采用 Hash 算...
    曹振華閱讀 2,566評(píng)論 1贊 37
  • 幾天前，一個(gè)正在瘋狂碼代碼的午后，釘釘上一個(gè)小伙伴問(wèn)我：“你知道HashMap是在什么時(shí)候做bucket的初始化的...
    miaoLoveCode閱讀 5,678評(píng)論 3贊 28
  • 寫(xiě)在開(kāi)始之前： Java為數(shù)據(jù)結(jié)構(gòu)中的映射定義了一個(gè)接口java.util.Map，此接口主要有四個(gè)常用的實(shí)現(xiàn)類，...
    VictorLiang閱讀 556評(píng)論 0贊 0
  • 過(guò)去的時(shí)代是門(mén)當(dāng)戶對(duì)。 現(xiàn)在的時(shí)代，其實(shí)也是門(mén)當(dāng)戶對(duì)，不過(guò)是性格和思想上的門(mén)當(dāng)戶對(duì)。 你要嫁給一個(gè)人，首先你要和他...
    貓黍閱讀 460評(píng)論 0贊 1
  • 6年前，有個(gè)樓主來(lái)八卦發(fā)帖，說(shuō)她倒追了七年的男生，終于和她在一起了。 故事從樓主上高中開(kāi)始，她參加完軍訓(xùn)回來(lái)，一眼...
    李鈴鐺閱讀 1,903評(píng)論 2贊 21

友情鏈接更多精彩內(nèi)容