[数据结构与算法]HashMap底层分析(一)

1、HashMap的底层。

jdk1.7：数组 + 链表

jdk1.8：数组 + 链表 + 红黑树

2、关于HashMap的无参构造方法。

(1).HashMap的无参构造方法采用延迟加载的方式来进行数组初始化的，默认长度是16，扩容因子为12

static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor(因数、系数) (0.75).
*/
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

这里并没有初始化数组，而是在put()方法的时候来完成数组的初始化的

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

transient Node<K,V>[] table;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //定义一个数组，Node<K,V>[] tab;
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //判断当前数组是null，或者长度等于0
        if ((tab = table) == null || (n = tab.length) == 0){
            
            //resize()就是初始化方法
            tab = resize()
            n=tab.length;
        }         
    }

在这一行，Node<K,V>[] tab开始初始化。resize()中的部分代码

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

newCap = DEFAULT_INITIAL_CAPACITY;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

(2).初始化方法：resize()

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;   //transient Node<K,V>[] table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;   //oldCap:0
        int oldThr = threshold;   //oldThr:0
        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)
                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;   //newCap:16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);   //newThr:12
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;   //threshold:12
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];   //初始化一个容量为16的Node<K,V>的数组
        table = newTab;
        if (oldTab != null) {
        ......
        }
        return newTab;
    }

(3).threshold

threshold：扩容因子

• 如果使用的是HashMap的无参构造器：

 Node<K,V>[] 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;
                return oldTab;
            }
            //
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }

总结：

//扩容因子第一次
threshold = (newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY));//0.75 * 16 = 12
//数组容量第一次
newCap = DEFAULT_INITIAL_CAPACITY;//16   
    
//扩容因子第二次
threshold = (newThr = oldThr << 1);  //12 * 2 = 24
//数组容量第一次
newCap = oldCap << 1; //16 * 2 = 32

作用：数组是否扩容是通过threshold扩容因子来进行判断，但是是按照数组容量的两倍来进行扩容的！

• 如果使用的是有参构造器HashMap(int initialCapacity, float loadFactor)

this.threshold = tableSizeFor(initialCapacity);  //扩容因子 = 扩容后的容量

3、关于HashMap的有参构造方法。

//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

有参构造器

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);  //非法数据异常
        
        //如果初始化容量大于最大容量，则改变为最大容量2^30
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
    
        //如果装载因子小于等于0 或 装载因子为NaN ，则报错
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
    
        //通过这个方法可以实现提前设置一个较为稳定的容量，从而避免频繁扩容导致的性能下降
        this.threshold = tableSizeFor(initialCapacity);
    }

–>关于Float.isNaN(flaoat v)

public static boolean isNaN(float v) {
        return (v != v);
    }
 /*  
每个NaN都会分配一个单独的地址来放, 所以导致NaN==NaN的时候比较内存地址一定会返回false,也就是当且仅当v是NaN时NaN!=NaN一定是true
    
虽然Float.NaN==Float.NaN 结果为false,但Float.NaN与Float.NaN的equal()结果相等的
虽然0.0f==-0.0f结果为true，但0.0f 与 -0.0f的equals()结果是不等的;*/

扩容方法：tablesizefor()

当初始化HashMap时，如果指定了初始化容量initialCapacity，由于哈希桶的数量必须时2的n次幂，因此要把initialCapacity转化为

比它大的最小2的n次幂。

如传入的initialCapacity=3，数组实际容量为4；传入的initialCapacity=5，数组实际容量为8；传入的initialCapacity=15，数组实际容量为16；

     /**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }