HashMap源码分析——默认参数问题

关键的默认参数

//哈希表默认容量，即桶数
 	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    //默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

	//树型阈值，即将桶结构转成红黑树的节点阈值
    static final int TREEIFY_THRESHOLD = 8;

	//非树型阈值，将桶结构转回链表形式的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
	
           

为什么初始容量是16？

  这个应该是一个经验值吧，太小会容易频繁扩容，太大又浪费空间。

默认负载因子为什么是0.75？

  负载因子是扩容机制的一个度量值，当 哈希表的K-V键值对数量>当前容量×负载因子 会发生扩容。

从极端情况分析：

  1、令负载因子为1，则扩容只在条目数>当前容量的时候，才发生扩容，虽然所有的空间都利用完了，但是发生哈希冲突变得不可避免了，所以会降低查询的效率。

  2、当负载因子取值接近0，只用到比较少的空间就开始扩容，之后发生哈希冲突的概率也比较小，时间效率是得到提高，但是空间利用率降低了。

  所以，在负载因子是0.75的时候，在时间和空间上取得了良好的折中。如果设置更大的值，可以提高空间的利用率，但是会降低时间效率。

为什么设置树型阈值为8？

可以看源码的开头的一段注释：

* Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million
           

大意是：

  1、因为树节点的存储空间大约是普通节点记录的两倍，如果一开始就使用树节点存储太浪费空间，所以要选择一个合适的值才转树节点。当低于一定值转回普通节点。

  2、在理想情况，随机哈希下，哈希表的桶内节点分布遵循泊松分布，当负载因子是0.75，桶中节点达到8个的概率已经低于千万分之1了。

普通节点源码：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        //其余方法
}
           

树节点源码：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        //其余方法
}