HashMap实现原理

    hashcode的取值范围为

    -2^31 到 2^31-1

    static final int DEFAULT_INITIAL_CAPACITY= 1 << 4; // aka 16
    初始化容量为16

    static final int _MAXIMUM_CAPACITY     = 1 << 30;

    最大容量那个太大了

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    默认负载因子

    static final int TREEIFY_THRESHOLD = 8;

    /* 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;

    static final int MIN_TREEIFY_CAPACITY = 64;

    内部类的Node函数
    Node(int hash, K key, V value, Node 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 V setValue(V newValue) {
    V oldValue = value;
    value = newValue;
    return oldValue;
    }

    public final boolean equals(Object o) {
    if (o == this)
    return true;
    if (o instanceof Map.Entry) {
    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    if (Objects.equals(key, e.getKey()) &&
    Objects.equals(value, e.getValue()))
    return true;
    }
    return false;
    }

    内部类Node结束

    \计算key的hash值
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    是hashmap的容量是2的n次方
    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;
    }

    \初始化table
    transient Node[] table;
    \一组node集合
    transient Set> entrySet;

    key-value的个数
    transient int size;

    transient int modCount;

    int threshold;

    final float loadFactor;

    public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
    }

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
    if (table == null) { // pre-size _float ft = ((float)s / loadFactor) + 1.0F;
    int t = ((ft < (float)_MAXIMUM_CAPACITY    ) ?
    (int)ft : MAXIMUM_CAPACITY);
    if (t > threshold)
    threshold = tableSizeFor(t);
    }
    else if (s > threshold)
    resize();
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
    K key = e.getKey();
    V value = e.getValue();
    putVal(hash(key), key, value, false, evict);
    }
    }
    }

    public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /* Implements Map.get and related methods. @param hash hash for key @param key the key @return the node, or null if none */_final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
    (first = tab[(n - 1) & hash]) != null) {
    if (first.hash == hash &&     // always check first node _((k = first.key) == key || (key != null && key.equals(k))))
    return first;
    if ((e = first.next) != null) {
    if (first instanceof TreeNode)
    return ((TreeNode)first).getTreeNode(hash, key);
    do {
    if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    return e;
    } while ((e = e.next) != null);
    }
    }
    return null;
    }

    1.8版本详解

    hash key value 传入参数

    Node tab 当前tab

    Node p 当前节点

    int n 长度
    int i下标

    Node e

    K k；

    **