java·數據結構·hashMap

特點

• 線程不安全
• HashMap、和Hashtable、SynchronizedMap區別：
  • HashMap 線程不安全，可以有null的key值或value值。
  • hashtable 線程安全，不能有null的key值或value值。
  • ConcurrentHashMap 線程安全，不能有null的key值或value值。刪除操作比較費時。
  • SynchronizedMap 線程安全，可以有null的key值或value值。
    • 可以通過Collections.synchronizedMap(new HashMap<String, Object>())方式創建
  • 性能:HashMap>ConcurrentHashMap>SynchronizedMap>Hashtable

構造方法

相關參數

• initialCapacity：初始最大容量，預設1<<4（2^4）,內部實際使用的變數是threshold(預設容量) ，實際最大容量並沒有存放。
• loadFactor:載入因數(預設容量=初始最大容量*載入因數)，預設0.75
• threshold:預設容量，內部變數，根據initialCapacity生成。執行構造方法時，將輸入的initialCapacity轉為不小於當前數的最小的2^k的值，作為threshold。在第一次構建table時（第一次put(實際上時putVal方法)，執行resize()方法），table的大小設置為threshold，然後讓threshold = threshold * loadFactor；後續每一次resize，都是table的大小 = table的大小 * 2；threshold = threshold * 2；
• 預設關係：threshold = initialCapacity * loadFactor(達到最大容量時不滿足該等式)

平衡與折衷

• 載入因數：hash表中元素的填滿程度，載入因數越大，空間利用率越高，衝突機會越高(查詢成本越高)

代碼解析

• public HashMap(int initialCapacity, float loadFactor)

public HashMap(int initialCapacity, float loadFactor) {
        /**初始最大容量為非負整數*/
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        /**
        * static final int MAXIMUM_CAPACITY = 1 << 30;
        * 當 initialCapacity 大於最大容量(2^30,約10.74億)時,強制設置為容量為最大容量。
        */
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        /**
        * 載入因數為大於0的浮點數
        * public static boolean isNaN(float v) {
        *   return (v != v);
        * }
        * Float.isNaN(loadFactor):NaN（not-a-number），例如. float v = 0.0f/0.0f;
        */
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        /**賦值容量因數*/
        this.loadFactor = loadFactor;
        /**
        * 轉換輸入的初始最大容量為2^k,賦值給threshold作為實際最大容量
        * 這樣做的意義待分析
        */
        this.threshold = tableSizeFor(initialCapacity);
    }

/**
* 獲取不小於當前數的最小的2^k的值.
* 例如：31->32,65->128
*/
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

• public HashMap(int initialCapacity)

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

• public HashMap()

/**
* 在resize()方法中設置threshold的值
* newCap = DEFAULT_INITIAL_CAPACITY;
* newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
*/
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

• public HashMap(Map<? extends K, ? extends V> m)
  • Map<String,Object> map = new HashMap<>(); Map.putAll(mapEntries);
    =>(完全等價於)
    Map<String,Object> map = new HashMap<>(mapEntries);
    （LinkedHashMap 繼承於HashMap，該場景不一定完全等價，區別在於afterNodeInsertion方法，待梳理）

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    /**
    * 當傳入的map映射中存有對象時，進行插入邏輯
    */
    if (s > 0) {
        /**
        * table == null ，這時threshold = 0，需要進行設置threshold的值,tableSizeFor方法作用可見上文。
        */
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        /**
        * 如果傳入的映射中對象個數大於當前預設容量，容量擴大1倍
        * (put方法中已經有resize邏輯，該操作的意義待分析)
        */
        else if (s > threshold)
            resize();
        /**
        * 迴圈遍歷每一個對象進行插入操作，和put方法完全一樣
        */
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

put

相關參數

• 暫未梳理

hashcode

• hashcode(Object)只和物理地址有關，和對象的內容沒有關係。

class Student {
    String name;
    String[] likes;
    public Student(String name){
        this.name = name;
    }
    public Student(String name,String[] likes){
        this.name = name;
        this.likes = likes;
    }
}
System.out.println(new Student("a").equals(new Student("a")));//false
Student aa = new Student("a");
System.out.println(aa.hashCode());//1410986873
aa.name = "bcdefg";
System.out.println(aa.hashCode());//1410986873
aa.name = "a";
System.out.println(aa.hashCode());//1410986873

Student bb = new Student("a",new String[] {"愛好1","愛好2"});
System.out.println(bb.hashCode());//2110245805
bb.likes = new String[] {"愛好1","愛好4"};
System.out.println(bb.hashCode());//2110245805

HashMap<String, Object> hashMap2 = new HashMap<String, Object>(1 << 4);
for(int i=0;i<13;i++) {
    hashMap2.put(String.valueOf(i), 1);
}
System.out.println(hashMap2.hashCode());//5228

HashMap<String, Object> hashMap3 = new HashMap<String, Object>(1 << 4);
for(int i=0;i<13;i++) {
    hashMap3.put(String.valueOf(i), 1);
}
System.out.println(hashMap3.hashCode());//5228
System.out.println(((Object)hashMap2).equals(hashMap3));//true

• hashMap.hashcode對hashcode方法進行了重寫，和key、value的hashcode有關係

public int hashCode() {
    int h = 0;
    Iterator<Entry<K,V>> i = entrySet().iterator();
    while (i.hasNext())
        h += i.next().hashCode();
    return h;
}

static class Node<K,V> implements Map.Entry<K,V> {
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
}
public final class Objects {
    public static int hashCode(Object o) {
        return o != null ? o.hashCode() : 0;
    }
}
public class Object {
    /**
    * 生成一個int類型的整型
    * 1.同一個對象（未發生變化）只能生成一個hashcode，如果equals(Object的equals方法)，那麼hashcode一定相等。
    * 2.不同對象可能會生成一個hashcode
    * 3.Object的hashCode方法只和物理地址有關，和對象的內容沒有關係。
    */
    public native int hashCode();
}

代碼解析

• static final int hash(Object key)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• final Node<K,V>[] resize()

/**
* 初始化或者給table容量加倍
*/
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    /**
    * 舊的最大容量，初始化時為0
    */
    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;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
             //非處初始化操作，oldCap>=16時，thr已經很規範了，直接二倍即可。
            newThr = oldThr << 1; // double threshold
    }
    /**初始化執行的操作*/
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    /**理論上永遠也走不到該條件*/
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //初始化操作時newThr == 0,非處初始化操作，但oldCap<16時，通過cap和factor生成thr。
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    /**
    * 代碼到這裡的時候，結構已經擴增完成了，得到了最終的threshold和table結構
    */
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    /**
    * 將oldTab的值拷貝到newTab中
    */
    //table非null,性能優化
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            /**
            * 為什麼在for迴圈內new對象，是否性能更高？
            */
            Node<K,V> e;
            //內容非null,性能優化
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    //通過e的hash值和當前最大容量來確定一個唯一的hash值？簡單推測
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //紅黑樹？待梳理
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve orde
                    //對鏈表結構的處理
                    //低位組low
                    Node<K,V> loHead = null, loTail = null;
                    //高位組high
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        /**
                        * key為null,e.hash=0
                        * 初始化時oldcap = 0
                        */
                        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;
                    }
                }
            }
        }
    }
    return newTab;
}

• public V put(K key, V value)

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> 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<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

小結：

• java位運算相關知識待歸納。 (位運算的目的是提高效率)
  • 1 << k(2^k)
  • ^是異或運算符，異或的規則是轉換成二進位比較，相同為0，不同為1.
  • int c=a ^ b ; a=c ^ b;b=c ^ a;
  • a&b 的操作的結果：a、b中對應位同時為1，則對應結果位也為1
• double和float區別待歸納。
• LinkedHashMap、HashMap、treemap、treenodes關係
• 為什麼n初始化構造map時，轉換輸入的初始最大容量為2^k,賦值給threshold作為實際最大容量。