HashMap源码解析一

jiezi

6 年前


    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量 (必须是 2 的幂，用左移动)

  
    static final int MAXIMUM_CAPACITY = 1 << 30;// 最大容量，如果隐式指定更高的值，则使用该容量 (必须是 2 的幂且小于等于 1 << 30)

   
    static final float DEFAULT_LOAD_FACTOR = 0.75f;// 加载因子 (负载系数)(用来衡量 HashMap 满的程度)(默认 0.75f)

   
    static final int TREEIFY_THRESHOLD = 8;// 使用树而不是 bin 的列表的 bin 计数阈值。将元素添加到具有至少这么多节点的 bin 时，bin 被转换为树。该值必须大于 2 且应至少为 8 才能与树木移除中的假设相关联，以便在收缩时转换回普通箱。static final int UNTREEIFY_THRESHOLD = 6;// 用于在调整大小操作期间解除（拆分）bin 的 bin 计数阈值。应该小于 TREEIFY_THRESHOLD，并且最多 6 个与去除时的收缩检测网格。static final int MIN_TREEIFY_CAPACITY = 64;// 容器可以树化的最小容量。（否则，如果 bin 中的节点太多，则会调整表的大小。）应该至少为 4 * TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;// 哈希值
        final K key;// 存储键
        V value;// 存储值
        Node<K,V> next;// 下一个节点

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key;}// 返回键值
        public final V getValue()      { return value;}// 返回存储值
        public final String toString() { return key + "=" + value;}

        public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);// 键值的 hash 与上存储值的 hash，Objects.hashCode() 入参为 null 返回 0}

        public final V setValue(V newValue) {// 设置值并返回旧值
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {if (o == this)// 内存地址相同直接返回 true
                return true;
            if (o instanceof Map.Entry) {// 如果是 Entry 的子类
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))// 调用当前节点 key 值的 equal 方法和当前节点 value 值的 equal 方法，结果与
                    return true;
            }
            return false;
        }
    }

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key 的 hash 值和 key 的 hash 值的高 16 位做异或 (>>> 左边高位补 0)(任何数跟 0 异或都是其本身)(所以结果是：也就是高十六位 + 高十六位 ^ 低十六位)
    }

范例

hash(-10)

-10.hashCode:       1111111111111111_1111111111110110
-10.hashCode>>>16:  0000000000000000_1111111111111111 
return:             1111111111111111_0000000000001001

static Class<?> comparableClassFor(Object x) {if (x instanceof Comparable) {// 如果是比较器子类
            Class<?> c; Type[] ts, as; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;// 如果是 String 返回 String 类
            if ((ts = c.getGenericInterfaces()) != null) {// 如果实现了接口
                for (Type t : ts) {// 循环实现的接口
                    if ((t instanceof ParameterizedType) &&
                        ((p = (ParameterizedType) t).getRawType() == Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && 
                        as[0] == c
                        ) // type arg is c
                        return c;
                }
            }
        }
        return null;// 不是比价器子类
    }

@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

static final int tableSizeFor(int cap) {int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);//Integer.numberOfLeadingZeros 返回左边开会连续的 0 个数
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

Integer.numberOfLeadingZeros() 返回左边最高位开始 0 的个数

计算范例 tableSizeFor(5)

n = -1 >>> Integer.numberOfLeadingZeros(5-1)

-1:              11111111_11111111_11111111_11111111
5-1=4：00000000_00000000_00000000_00000100
Integer.numberOfLeadingZeros(5-1):29
-1>>>29:         00000000_00000000_00000000_00000111

n=7
n>0
n<MAXIMUM_CAPACITY
return: n+1
return: 7+1
return: 8



    transient Node<K,V>[] table;// 该表在首次使用时初始化

    
    transient Set<Map.Entry<K,V>> entrySet;// 保持缓存的 entrySet()  AbstractMap 字段用于 keySet() 和 values()
    
    
    transient int size;// 此映射中包含的键 - 值映射的数量

    transient int modCount;// 此 HashMap 已被结构修改的次数

   
    int threshold;// 下一次需要扩容时的大小（capacity * load factor）final float loadFactor;// 哈希表的加载因子

 public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他属性都是默认的 (DEFAULT_LOAD_FACTOR = 0.75f)
    }

public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);//(DEFAULT_LOAD_FACTOR = 0.75f)
    }

 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;
        this.threshold = tableSizeFor(initialCapacity);
    }

HashMap源码解析一

常量

基本哈希 bin 节点 Node

静态工具类（方法）

hash(Object key)

comparableClassFor 如果它的形式为“class C implements Comparable <C>”，则返回 x 的 Class，否则返回 null

compareComparables() 如果 x 匹配 kc（k 的筛选可比类），则返回 k.compareTo（x），否则返回 0。

tableSizeFor 返回给定目标容量的两个大小的幂。

变量

构造方法

HashMap()( 默认的负载因子是 0.75f)

HashMap(int initialCapacity)(自定义负载因子)

HashMap(int initialCapacity, float loadFactor)