HashMap学习笔记(一)构造方法及重要属性

HashMap中重要的成员变量

/**
     * The default initial capacity - MUST be a power of two.
     */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	//当无参构造创建 HashMap 时,不创建哈希桶;等到使用 put 方法向 hashMap 中插入 kv 时,
	//调用 resize 方法,按需创建哈希桶,默认初始容量为 16

/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
static final int MAXIMUM_CAPACITY = 1 << 30;

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

/**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
static final int TREEIFY_THRESHOLD = 8;
//当链表长度大于 8 时,判断是否需要将链表转换为红黑树 (treeifyBin)
/**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
static final int UNTREEIFY_THRESHOLD = 6;
//当红黑树节点小于 6 时,将红黑树转换回链表
/**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
static final int MIN_TREEIFY_CAPACITY = 64;
//当链表长度大于 8 时,判断哈希桶长度(length)是否大于 64 ,如果不大于则扩容哈希桶,将所有 kv rehash,如果大于则将链表转换为红黑树

/**
 * The number of key-value mappings contained in this map.
 */
transient int size; //大小,hashMap中存放的kv个数

/**
 * The number of times this HashMap has been structurally modified
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 * the HashMap fail-fast.  (See ConcurrentModificationException).
 */
transient int modCount; //hashMap结构被修改次数

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold; //阈值 = capacaty * loadFactor

/**
 * The load factor for the hash table.
 *
 * @serial
 */
final float loadFactor; //负载因子,默认为0.75(一般不建议修改loadFactor的值)
//当存储的kv个数 = threshold = loadFactor * capacity 时,哈希桶进行2倍扩容


为什么要有负载因子?

loadFactor 与 hashMap 的扩容机制息息相关,loadFactor 表示了HashMap 满的程度,它决定了 hashMap 何时扩容。如果等到 HashMap 满了再扩容,那么在接近满的状态时插入新的 kv 时, 会造成很严重的哈希碰撞,大大降低了插入的效率,同时也会降低查询的效率(链表长度过长 / 红黑树深度过深?)。如果在 HashMap 未满时扩容,那么何时进行扩容,是最重要的问题,太早扩容浪费空间,太晚扩容浪费时间(rehash),所以 hashMap 源码将 loadFactor 设置为0.75.

loadFactor 为什么是0.75?

https://blog.csdn.net/qq_45401061/article/details/104479262

HashMap 有参构造

public HashMap(int initialCapacity, float loadFactor) {
    //自定义初始容量以及负载因子
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    // 根据初始化容量,计算出 KV 个数的阈值
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    //自定义哈希桶初始容量,默认负载因子为0.75
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    //无参构造,不创建哈希桶(按需创建),默认负载因子为0.75
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * Constructs a new <tt>HashMap</tt> with the same mappings as the
 * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 * default load factor (0.75) and an initial capacity sufficient to
 * hold the mappings in the specified <tt>Map</tt>.
 *
 * @param   m the map whose mappings are to be placed in this map
 * @throws  NullPointerException if the specified map is null
 */
public HashMap(Map<? extends K, ? extends V> m) {
    //有参构造,下面详解
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
/**
 * 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 ^1)
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

// | 按位或,& 按位与,^ 按位异或
// |= 先按位或再赋值

EG: tableSizeFor(2) = 4 tableSizeFor(25) = 32

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            //判断插入的 map 中 kv 个数是否大于0
            if (table == null) { // pre-size
                //如果原 map 为空,则计算加入新 map 后的预计大小
                float ft = ((float)s / loadFactor) + 1.0F;
                //判断预计大小是否大于 hashMap 最大容量,大于则将 map 大小设置为 MAXIMUM_CAPACITY
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                //如果预计大小大于阈值,则阈值重新赋值,扩大到大于等于当前尺寸的最小2的幂次方
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                //如果原 map 不为空,如果插入的 map 大小大于阈值,则2倍扩容哈希桶
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                //在 putVal 过程中,也有可能会使哈希桶扩容
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
上一篇:HashMap的初始容量大小和长度扩展。hash算法


下一篇:HashSet源码分析