目錄
「鍵值」對映射的抽象介面。此映射不包括重複的鍵,一個鍵對應一個值。 " > 「鍵值」對映射的抽象介面。此映射不包括重複的鍵,一個鍵對應一個值。
二、內部雜湊: 雜湊映射技術" >二、內部雜湊: 雜湊映射技術
3.2、负载因子" >3.2、负载因子
最后" >最后
首頁 Java java教程 Java提高篇(三三)-----Map總結

Java提高篇(三三)-----Map總結

Feb 11, 2017 am 10:24 AM

        在前面LZ詳細介紹了HashMap、HashTable、TreeMap的實現方法,從資料結構、實現原理、源碼分析三個方面進行闡述,對這個三個類應該有了比較清晰的了解,下面LZ就Map做一個簡單的總結。

        推薦閱讀:

         

java增進篇(二五)—–HashTable

       

Java提高篇(二六)-----hashCode Map

一、Map概述

        先看Map的結構示意圖

「鍵值」對映射的抽象介面。此映射不包括重複的鍵,一個鍵對應一個值。

       

SortedMap:有序的鍵值對接口,繼承Map接口。

        NavigableMap:繼承SortedMap,具有了針對給定搜尋目標傳回給定的導覽方法的介面。

        AbstractMap:實現了Map中大部分的函數介面。它減少了「Map的實作類別」的重複編碼。

        Dictionary:任何可將鍵映射到對應值的類別的抽象父類。目前被Map介面取代。

        TreeMap:有序散列表,並實現SortedMap 介面,底層透過紅黑樹實現。

        HashMap:是基於「拉鍊法」所實現的散列表。底層採用「數組+鍊錶」實作。

        WeakHashMap:基於「拉鍊法」所實現的雜湊列表。

        HashTable:基於「拉鍊法」所實現的雜湊。

       

二、內部雜湊: 雜湊映射技術

        幾乎所有通用Map都使用雜湊映射技術。對於我們程式設計師來說我們必須要對其有所了解。

        哈希映射技術是一種非常簡單的元素映射到陣列的技術。由於雜湊映射採用的是數組結果,那麼必然存在一中用於確定任意鍵存取數組的索引機制,該機制能夠提供一個小於數組大小的整數,我們將該機制稱為雜湊函數。在Java中我們不必為尋找這樣的整數而大傷腦筋,因為每個物件都必定存在一個傳回整數值的hashCode方法,而我們需要做的就是將其轉換為整數,然後再將該值除以數組大小取餘即可。如下:

int hashValue = Maths.abs(obj.hashCode()) % size;
登入後複製

下面是HashMap、HashTable的:

----------HashMap------------
//计算hash值
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
//计算key的索引位置
static int indexFor(int h, int length) {
        return h & (length-1);
}
-----HashTable--------------
int index = (hash & 0x7FFFFFFF) % tab.length;     //确认该key的索引位置
登入後複製

 位置的索引代表了該節點在數組中的該節點。下圖為雜湊映射的基本原理圖:


         在該圖中1-4步驟是找到此元素在陣列中位置,5-8步驟是將該元素插入陣列中。在插入的過程中會遇到一點小挫折。在眾多肯能存在多個元素他們的hash值是一樣的,這樣就會得到相同的索引位置,也就說多個元素會映射到相同的位置,這個過程我們稱之為「衝突」。解決衝突的辦法是在索引位置處插入連結列表,並簡單地將元素新增至此連結列表。當然也不是簡單的插入,在HashMap中的處理過程如下:取得索引位置的鍊錶,如果該鍊錶為null,則將該元素直接插入,否則透過比較是否存在與該key相同的key,若存在則覆蓋原來key的value並傳回舊值,否則將該元素保存在鏈頭(最先保存的元素放在鏈尾)。以下是HashMap的put方法,該方法詳細展示了計算索引位置,將元素插入到適當的位置的全部過程:

public V put(K key, V value) {
        //当key为null,调用putForNullKey方法,保存null与table第一个位置中,这是HashMap允许为null的原因
        if (key == null)
            return putForNullKey(value);
        //计算key的hash值
        int hash = hash(key.hashCode());                 
        //计算key hash 值在 table 数组中的位置
        int i = indexFor(hash, table.length);            
        //从i出开始迭代 e,判断是否存在相同的key
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            Object k;
            //判断该条链上是否有hash值相同的(key相同)
            //若存在相同,则直接覆盖value,返回旧value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;    //旧值 = 新值
                e.value = value;
                e.recordAccess(this);
                return oldValue;     //返回旧值
            }
        }
        //修改次数增加1
        modCount++;
        //将key、value添加至i位置处
        addEntry(hash, key, value, i);
        return null;
    }
登入後複製

         HashMap
      如果我們查看其它的Map,發現其原理都差不多!

三、Map最佳化

         首先被映射,假設哈希映射的內部數組的大小只有1,所有的元素都將只有1,所有的元素都構成一個較大的位(從而一個長的大小(從而較大的大小)(從而較大地1,所有的元素都只有1,所有的元素都構成一個較大(從而一個長的)鍊錶。由於我們更新、訪問都要對這條鍊錶進行線性搜索,這樣勢必會降低效率。我們假設,如果存在一個非常大數組,每個位置鍊錶處都只有一個元素,在進行訪問時計算其 index 值就會獲得該對象,這樣做雖然會提高我們搜索的效率,但是它浪費了控制項。誠然,雖然這兩種方式都是極端的,但是它給我們提供了一種優化思路:使用一個較大的數組讓元素能夠均勻分佈。

在Map有兩個會影響到其效率,一是容器的初始化大小、二是負載因子。

3.1、調整實現大小

         在哈希映射表中,以內部數組中的每個位置稱為「儲存桶」(bucket),而可用桶數的儲存空間(即可用桶的數組”大小)稱作容量(capacity),我們為了讓Map物件能夠有效地處理任意數的元素,將Map設計成可以調整自身的大小。我們知道當Map中的元素達到一定量的時候就會調整容器本身的大小,但是這個調整大小的過程其開銷是非常大的。調整大小需要將原來所有的元素插入到新數組中。我們知道index = hash(key) % length。這樣可能會導致原先衝突的鍵不在衝突,不衝突的鍵現在衝突的,重新計算、調整、插入的過程開銷是非常大的,效率也比較低。所以,如果我們開始知道Map的預期大小值,將Map調整的足夠大,則可以大幅減少甚至不需要重新調整大小,這很有可能會提高速度。

下面是HashMap調整容器大小的過程,透過下面的程式碼我們可以看到其擴容過程的複雜性:

🎜🎜
void resize(int newCapacity) {
            Entry[] oldTable = table;    //原始容器
            int oldCapacity = oldTable.length;    //原始容器大小
            if (oldCapacity == MAXIMUM_CAPACITY) {     //是否超过最大值:1073741824
                threshold = Integer.MAX_VALUE;
                return;
            }

            //新的数组:大小为 oldCapacity * 2
            Entry[] newTable = new Entry[newCapacity];    
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
           /*
            * 重新计算阀值 =  newCapacity * loadFactor >  MAXIMUM_CAPACITY + 1 ? 
            *                         newCapacity * loadFactor :MAXIMUM_CAPACITY + 1
            */
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);   
        }
        
        //将元素插入到新数组中
        void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }
登入後複製

3.2、负载因子

         为了确认何时需要调整Map容器,Map使用了一个额外的参数并且粗略计算存储容器的密度。在Map调整大小之前,使用”负载因子”来指示Map将会承担的“负载量”,也就是它的负载程度,当容器中元素的数量达到了这个“负载量”,则Map将会进行扩容操作。负载因子、容量、Map大小之间的关系如下:负载因子 * 容量 > map大小  ----->调整Map大小。

         例如:如果负载因子大小为0.75(HashMap的默认值),默认容量为11,则 11 * 0.75 = 8.25 = 8,所以当我们容器中插入第八个元素的时候,Map就会调整大小。

        负载因子本身就是在控件和时间之间的折衷。当我使用较小的负载因子时,虽然降低了冲突的可能性,使得单个链表的长度减小了,加快了访问和更新的速度,但是它占用了更多的控件,使得数组中的大部分控件没有得到利用,元素分布比较稀疏,同时由于Map频繁的调整大小,可能会降低性能。但是如果负载因子过大,会使得元素分布比较紧凑,导致产生冲突的可能性加大,从而访问、更新速度较慢。所以我们一般推荐不更改负载因子的值,采用默认值0.75.

最后

        推荐阅读:

        java提高篇(二三)—–HashMap

        java提高篇(二五)—–HashTable

        Java提高篇(二六)-----hashCode

        Java提高篇(二七)—–TreeMap

 


以上就是Java提高篇(三三)-----Map总结的内容,更多相关内容请关注PHP中文网(www.php.cn)!


本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

突破或從Java 8流返回? 突破或從Java 8流返回? Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API,提供了一種強大且表達力豐富的處理數據集合的方式。然而,使用Stream時,一個常見問題是:如何從forEach操作中中斷或返回? 傳統循環允許提前中斷或返回,但Stream的forEach方法並不直接支持這種方式。本文將解釋原因,並探討在Stream處理系統中實現提前終止的替代方法。 延伸閱讀: Java Stream API改進 理解Stream forEach forEach方法是一個終端操作,它對Stream中的每個元素執行一個操作。它的設計意圖是處

PHP:網絡開發的關鍵語言 PHP:網絡開發的關鍵語言 Apr 13, 2025 am 12:08 AM

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

PHP與Python:了解差異 PHP與Python:了解差異 Apr 11, 2025 am 12:15 AM

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

Java程序查找膠囊的體積 Java程序查找膠囊的體積 Feb 07, 2025 am 11:37 AM

膠囊是一種三維幾何圖形,由一個圓柱體和兩端各一個半球體組成。膠囊的體積可以通過將圓柱體的體積和兩端半球體的體積相加來計算。本教程將討論如何使用不同的方法在Java中計算給定膠囊的體積。 膠囊體積公式 膠囊體積的公式如下: 膠囊體積 = 圓柱體體積 兩個半球體體積 其中, r: 半球體的半徑。 h: 圓柱體的高度(不包括半球體)。 例子 1 輸入 半徑 = 5 單位 高度 = 10 單位 輸出 體積 = 1570.8 立方單位 解釋 使用公式計算體積: 體積 = π × r2 × h (4

PHP與其他語言:比較 PHP與其他語言:比較 Apr 13, 2025 am 12:19 AM

PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

PHP與Python:核心功能 PHP與Python:核心功能 Apr 13, 2025 am 12:16 AM

PHP和Python各有優勢,適合不同場景。 1.PHP適用於web開發,提供內置web服務器和豐富函數庫。 2.Python適合數據科學和機器學習,語法簡潔且有強大標準庫。選擇時應根據項目需求決定。

創造未來:零基礎的 Java 編程 創造未來:零基礎的 Java 編程 Oct 13, 2024 pm 01:32 PM

Java是熱門程式語言,適合初學者和經驗豐富的開發者學習。本教學從基礎概念出發,逐步深入解說進階主題。安裝Java開發工具包後,可透過建立簡單的「Hello,World!」程式來實踐程式設計。理解程式碼後,使用命令提示字元編譯並執行程序,控制台上將輸出「Hello,World!」。學習Java開啟了程式設計之旅,隨著掌握程度加深,可創建更複雜的應用程式。

如何在Spring Tool Suite中運行第一個春季啟動應用程序? 如何在Spring Tool Suite中運行第一個春季啟動應用程序? Feb 07, 2025 pm 12:11 PM

Spring Boot簡化了可靠,可擴展和生產就緒的Java應用的創建,從而徹底改變了Java開發。 它的“慣例慣例”方法(春季生態系統固有的慣例),最小化手動設置

See all articles