国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

HashMap源碼解析(一)

cikenerd / 1924人閱讀

摘要:否則,如果中的節點太多,則會調整表的大小。應該至少為,以避免調整大小和樹化閾值之間的沖突。

常量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默認初始容量 (必須是2的冪,用左移動)

  
    static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量,如果隱式指定更高的值,則使用該容量(必須是2的冪且小于等于1 << 30)

   
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//加載因子(負載系數)(用來衡量HashMap滿的程度)(默認0.75f)

   
    static final int TREEIFY_THRESHOLD = 8;//(鏈表轉樹的閾值)

    
    static final int UNTREEIFY_THRESHOLD = 6;//(樹轉鏈表的閾值)

 
    static final int MIN_TREEIFY_CAPACITY = 64;//容器可以樹化的最小容量。 (否則,如果bin中的節點太多,則會調整表的大小。)應該至少為4 * TREEIFY_THRESHOLD,以避免調整大小和樹化閾值之間的沖突。
基本哈希bin節點Node
static class Node implements Map.Entry {
        final int hash;//哈希值
        final K key;//存儲鍵
        V value;//存儲值
        Node next;//下一個節點

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }//返回鍵值
        public final V getValue()      { return value; }//返回存儲值
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);//鍵值的hash與上存儲值的hash,Objects.hashCode()入參為null返回0
        }

        public final V setValue(V newValue) {//設置值并返回舊值
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)//內存地址相同直接返回true
                return true;
            if (o instanceof Map.Entry) {//如果是Entry 的子類
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))//調用當前節點key值的equal方法和當前節點value值的equal方法,結果與
                    return true;
            }
            return false;
        }
    }
靜態工具類(方法) hash(Object key)
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key的hash值和key的hash值的高16位做異或(>>>左邊高位補0)(任何數跟0異或都是其本身)(所以結果是:也就是高十六位+高十六位^低十六位)
    }

范例

hash(-10)

-10.hashCode:       1111111111111111_1111111111110110
-10.hashCode>>>16:  0000000000000000_1111111111111111 
return:             1111111111111111_0000000000001001
comparableClassFor 如果它的形式為“class C implements Comparable ”,則返回x的Class,否則返回null
static Class comparableClassFor(Object x) {
        if (x instanceof Comparable) {//如果是比較器子類
            Class c; Type[] ts, as; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;//如果是String返回String類
            if ((ts = c.getGenericInterfaces()) != null) {//如果實現了接口
                for (Type t : ts) {//循環實現的接口
                    if (
                        (t instanceof ParameterizedType) &&
                        ((p = (ParameterizedType) t).getRawType() == Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && 
                        as[0] == c
                        ) // type arg is c
                        return c;
                }
            }
        }
        return null;//不是比價器子類
    }
compareComparables() 如果x匹配kc(k的篩選可比類),則返回k.compareTo(x),否則返回0。
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }
tableSizeFor 返回給定目標容量的兩個大小的冪(返回能裝下傳入參數的大小,且為2的次方)
static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);//Integer.numberOfLeadingZeros返回左邊開會連續的0個數
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

Integer.numberOfLeadingZeros()返回左邊最高位開始0的個數

計算范例 tableSizeFor(5)

n = -1 >>> Integer.numberOfLeadingZeros(5-1)

-1:              11111111_11111111_11111111_11111111
5-1=4:          00000000_00000000_00000000_00000100
Integer.numberOfLeadingZeros(5-1):29
-1>>>29:         00000000_00000000_00000000_00000111

n=7
n>0
n
變量

    transient Node[] table;//哈希桶數組(該表在首次使用時初始化)

    
    transient Set> entrySet;//保持緩存的entrySet()  AbstractMap字段用于keySet()和values()
    
    
    transient int size;//此映射中包含的鍵 - 值映射的數量

    transient int modCount;//此HashMap已被結構修改的次數

   
    int threshold;//下一次需要擴容時的大?。╟apacity * load factor)(初值為0)

   
    final float loadFactor;//哈希表的加載因子
構造方法 HashMap()(默認的負載因子是0.75f)
 public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他屬性都是默認的(DEFAULT_LOAD_FACTOR = 0.75f)
    }
HashMap(int initialCapacity)(自定義容量)(通過tableSizeFor來計算2的次方的容量大小)
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);//(DEFAULT_LOAD_FACTOR = 0.75f)
    }
HashMap(int initialCapacity, float loadFactor)
 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)//容量小于0,拋出異常
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)//容量大于最大容量1 << 30
            initialCapacity = MAXIMUM_CAPACITY;//則使用最大容量
        if (loadFactor <= 0 || Float.isNaN(loadFactor))//如果負載因子小于0或者不是數字,拋出異常
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;//賦值負載因子
        this.threshold = tableSizeFor(initialCapacity);//計算容量,為2的冪
    }
HashMap(Map m)根據一個map構造一個map
 public HashMap(Map m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;//默認的負載因子
        putMapEntries(m, false);
    }
 putMapEntries(Map m, boolean evict)實現Map.putAll和Map構造函數
 final void putMapEntries(Map m, boolean evict) {
        int s = m.size();//獲取m映射數量
        if (s > 0) {//長度大于0
        
            if (table == null) { //表是空的(沒有數據)
                float ft = ((float)s / loadFactor) + 1.0F;//按照默認負載因子比例計算出的大小+1
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);//小于最大容量就使用ft計算,大于最大容量使用最大容量計算
                if (t > threshold)//如果超過擴容閾值,那么就重新計算擴容閾值
                    threshold = tableSizeFor(t);//重新計算擴容閾值(2的冪)
            }
            else if (s > threshold)//如果表不是空的,且大小大于擴容閾值
                resize();//進行擴容
            for (Map.Entry e : m.entrySet()) {//循環插入
                K key = e.getKey();//獲取key
                V value = e.getValue();//獲取value
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
resize()擴容
final Node[] resize() {
        Node[] oldTab = table;//舊的表
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//不為空的話賦值為舊表數據量
        int oldThr = threshold;//獲取擴容的閾值
        int newCap, newThr = 0;
        
        
        if (oldCap > 0) {//如果舊表不為空
        
        
            if (oldCap >= MAXIMUM_CAPACITY) {//如果舊表數據量大于最大容量
                threshold = Integer.MAX_VALUE;//擴容閾值設置成0x7fffffff(1111111111111111111111111111111)
                return oldTab;//返回舊的數據表
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY&&oldCap >= DEFAULT_INITIAL_CAPACITY)//否則,兩倍大小小于最大容量,且舊的空間大于初始化空間
                newThr = oldThr << 1; // 新的閾值為舊的閾值兩倍
        }
        
        
        else if (oldThr > 0) //舊表為空,且舊表閾值>0 
            newCap = oldThr;//初始容量被置于閾值
        else {   //舊表為空,且舊表閾值<0           
            newCap = DEFAULT_INITIAL_CAPACITY;//默認的空間
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//默認的閾值
        }//if (oldCap > 0)結束
        
        
        if (newThr == 0) {//如果新的閾值等于0
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        
        threshold = newThr;//重新賦值閾值
        @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {//有舊的數據
        
            for (int j = 0; j < oldCap; ++j) {// 把每個哈希桶里的值都移動到新的哈希桶中
            
                Node e;
                if ((e = oldTab[j]) != null) {//哈希桶位不為空
                
                    oldTab[j] = null;//原位置空
                    if (e.next == null)//如果這個桶位只有這一個元素(沒有next)
                        newTab[e.hash & (newCap - 1)] = e;//用新的長度取模,數據放置位置
                    else if (e instanceof TreeNode)//如果是紅黑樹
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { //如果是鏈表
                    
                        Node loHead = null, loTail = null;//低位頭尾
                        Node hiHead = null, hiTail = null;//高位頭尾
                        Node next;
                        
                        do {
                        
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                            
                        } while ((e = next) != null);//循環直至鏈表沒有下一個節點
                        
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                        
                    }//(e.next == null)的else結尾
                    
                }//if ((e = oldTab[j]) != null)結尾
                
            }// for (int j = 0; j < oldCap; ++j)結尾
            
            
        }//if (oldTab != null)結尾
        
        return newTab;
    }
putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) 放置值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//如果桶是空的,或者桶的長度是0
            n = (tab = resize()).length;//擴容
        if ((p = tab[i = (n - 1) & hash]) == null)//取模桶位是空的
            tab[i] = newNode(hash, key, value, null);//直接賦值
        else {//存在長鏈或紅黑樹
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//和鏈表的第一個值同值,進行覆蓋
                e = p;
            else if (p instanceof TreeNode)//紅黑樹
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {//binCount為下標指針循環鏈表
                    if ((e = p.next) == null) {//循環到鏈表的末尾(next為空)
                        p.next = newNode(hash, key, value, null);//把插入的節點作為鏈表的末尾的下一個節點
                        if (binCount >= TREEIFY_THRESHOLD - 1) //如果達到樹化的閾值,那么轉化為樹
                            treeifyBin(tab, hash);
                        break;//結束循環
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))//插入的節點和鏈表某一個節點相同,直接跳出
                        break;
                    p = e;//循環指針p移到下一位
                }
            }
            if (e != null) { //已存在映射,覆蓋
                V oldValue = e.value;//獲取舊值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;//賦值
                afterNodeAccess(e);//后期回調操作
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)//是否達到擴容閾值
            resize();
        afterNodeInsertion(evict);//后期回調操作
        return null;
    }

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/74959.html

相關文章

  • java源碼

    摘要:集合源碼解析回歸基礎,集合源碼解析系列,持續更新和源碼分析與是兩個常用的操作字符串的類。這里我們從源碼看下不同狀態都是怎么處理的。 Java 集合深入理解:ArrayList 回歸基礎,Java 集合深入理解系列,持續更新~ JVM 源碼分析之 System.currentTimeMillis 及 nanoTime 原理詳解 JVM 源碼分析之 System.currentTimeMi...

    Freeman 評論0 收藏0
  • jdk1.8中HashMap源碼解析

    摘要:當鏈表長度即將超過閥值,會把鏈表轉化為紅黑樹。然后再判斷是鏈表還是紅黑樹如果值相同,并且相同表示數組中第一個元素即為相同的將數組中第一個元素賦值給如果當前元素類型為表示為紅黑樹,返回待存放的。 前提:學習HashMap的底層代碼之前,首先要對數據結構要個大致的了解。其中重點了解數組,鏈表,樹的概念和用法。 一.圖示分析HashMap的結構 (1)圖示為JDK1.8之前的HashMap結...

    李文鵬 評論0 收藏0
  • 系列文章目錄

    摘要:為了避免一篇文章的篇幅過長,于是一些比較大的主題就都分成幾篇來講了,這篇文章是筆者所有文章的目錄,將會持續更新,以給大家一個查看系列文章的入口。 前言 大家好,筆者是今年才開始寫博客的,寫作的初衷主要是想記錄和分享自己的學習經歷。因為寫作的時候發現,為了弄懂一個知識,不得不先去了解另外一些知識,這樣以來,為了說明一個問題,就要把一系列知識都了解一遍,寫出來的文章就特別長。 為了避免一篇...

    lijy91 評論0 收藏0
  • 系列文章目錄

    摘要:為了避免一篇文章的篇幅過長,于是一些比較大的主題就都分成幾篇來講了,這篇文章是筆者所有文章的目錄,將會持續更新,以給大家一個查看系列文章的入口。 前言 大家好,筆者是今年才開始寫博客的,寫作的初衷主要是想記錄和分享自己的學習經歷。因為寫作的時候發現,為了弄懂一個知識,不得不先去了解另外一些知識,這樣以來,為了說明一個問題,就要把一系列知識都了解一遍,寫出來的文章就特別長。 為了避免一篇...

    Yumenokanata 評論0 收藏0
  • Java集合之LinkedHashMap源碼解析

    摘要:底層基于拉鏈式的散列結構,并在中引入紅黑樹優化過長鏈表的問題。在其之上,通過維護一條雙向鏈表,實現了散列數據結構的有序遍歷。 原文地址 LinkedHashMap LinkedHashMap繼承自HashMap實現了Map接口?;緦崿F同HashMap一樣,不同之處在于LinkedHashMap保證了迭代的有序性。其內部維護了一個雙向鏈表,解決了 HashMap不能隨時保持遍歷順序和插...

    QiShare 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<