java HashMap，javahashmap

java HashMap，javahashmap

HashMap 的性能因子

1. 容量：表示桶位的數量。

2. 初始容量: 表在創建是所擁有的桶位數。

•   如果你知道將要在HashMap存儲多少項，創建一個初始容量合適的HashMap將可以避免自動再散列的開銷

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默認大小

3. 尺寸： 表中當前存儲的項數。

4. 負載因子：尺寸/容量。 負載因子小的表沖突的可能性小，插入和查找的速度也相對較快（但會減慢使用迭代器進行遍歷的過程）。HashMap和HashSet都具有允許你指定負載因子的構造器，表示當負載情況達到負載因子的水平時，容器將自動增加容量。實現方法是使容量加倍，並將現有對象分配到新的桶位集中。

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap構造器

創建HashMap對象時，無論調用哪個構造器，最終都會調用

HashMap(int initialCapacity, float loadFactor), initialCapacity為初始容量， loadFactor為負載因子

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)  // MAXIMUM_CAPACITY為最大容量
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity); // tableSizeFor(initialCapacity) 會返回 x, x 滿足 x = 2^n 且 x >= initialCapacity)
    }

來看看tableSizeFor的實現(個人絕對想不到這麼高大上的方法)

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;  //這裡是因為考慮到cap為2的整數次冪的情況

        //1. 假設此時n的二進制最高位1在第i位（最低位為第0位）

        n |= n >>> 1;

        //2. 此時n的二進制第i, i-1位都為1

        n |= n >>> 2;

        //3. 此時n的二進制第i, i-1,  i-2, i-3位都為1

        n |= n >>> 4; 

        //4. 此時n的二進制第i, i-1,  i-2, i-3, i-4, i-5, i-6, i-7位都為1(當然，嚴謹點應該再假設i>7)

        n |= n >>> 8;
        //5.---------
        n |= n >>> 16;
        //6.---------
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }