简介

HashMap在Map体系中的继承实现关系：

HashMap就是我们常说的哈希表。
哈希表的表示：https://blog.csdn.net/weixin_43598687/article/details/119713753

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap继承至AbstractMap，并且实现了Map, Cloneable, Serializable接口，支持可复制以及序列化操作。

HashMap的底层采用的是数组 + 链表 + 红黑树实现的。使用链地址法来处理冲突，也就是数组加链表的结合，在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

哈希表的初始容量为16，最大容量为1,073,741,824（1<<30，230），负载因子为0.75，HashMap的容量必须为2n，如果相同哈希值，链表的长度超过8，就从链表转换成红黑树。

/** * The default initial capacity - MUST be a power of two. */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 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;

构造方法

HashMap也是我们最常用的一种Map结构，在HashMap中提供了多种构造方法，如下：

HashMap(int initialCapacity, float loadFactor)

构造一个空的 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;
        this.threshold = tableSizeFor(initialCapacity);
    }

HashMap(int initialCapacity)

构造一个空的 HashMap ，具有指定的初始容量和默认负载系数（0.75）。

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

HashMap()

构造一个空的 HashMap ，具有默认初始容量和默认负载系数（0.75）。

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

HashMap(Map<? extends K, ? extends V> m)

构造一个新的HashMap与指定的相同的映射Map 。该HashMap与默认负载因数（0.75）和初始容量足以容纳映射在指定Map创建。

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

HashMap.Node

前面提到Map集合的主干是一个Entry数组，Entry是Map的一个基本单元，每一个Entry包含一个key-value键值对。

Node是HashMap中的一个静态内部类，它实现了Map.Entry接口，一个Node就相当于一个Entry。
Node在HashMap中的定义如下：

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);
        }

        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;
        }
    }

常用方法

int size()

返回此哈希表中键值映射的数量。

public int size() {
        return size;
    }

boolean isEmpty()

如果此哈希表不包含键值映射，则返回 true 。

public boolean isEmpty() {
        return size == 0;
    }

V get(Object key)

返回到指定键所映射的值。

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

boolean containsKey(Object key)

如果此映射包含指定键的映射，则返回 true 。

public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

V put(K key, V value)

将指定的值与此映射中的指定键相关联。

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

void putAll(Map<? extends K, ? extends V> m)

将指定map的所有映射复制到此map。

public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }
    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);
            }
        }
    }

V remove(Object key)

从该map中删除指定键的映射（如果存在）。

public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

void clear()

从该map中删除所有的映射。

public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

boolean containsValue(Object value)

如果此map将一个或多个键映射到指定的值，则返回 true 。

public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

Set keySet()

返回此map中包含的键的Set视图。

public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

Collection values()

返回此map中包含的值的Collection视图。

public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }

Set<Map.Entry<K,V>> entrySet()

返回此map中包含的映射的Set视图。

public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

V getOrDefault(Object key, V defaultValue)

返回到指定键所映射的值，如果此映射不包含该键的映射，返回defaultValue。

public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }

V putIfAbsent(K key, V value)

如果指定的键尚未与值相关联（或映射到 null ）将其与给定值相关联并返回 null ，否则返回当前值。

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

boolean remove(Object key, Object value)

仅当指定的键当前映射到指定的值时删除该条目。

public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true, true) != null;
    }

boolean replace(K key, V oldValue, V newValue)

仅当当前映射到指定的值时，才能替换指定键的条目。

public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            afterNodeAccess(e);
            return true;
        }
        return false;
    }

V replace(K key, V value)

只有当目标映射到某个值时，才能替换指定键的条目。

public V replace(K key, V value) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) != null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
        return null;
    }

Object clone()

返回此 HashMap实例的浅拷贝：键和值本身不被克隆。

public Object clone() {
        HashMap<K,V> result;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
        result.reinitialize();
        result.putMapEntries(this, false);
        return result;
    }

从源码分析哈希表HashMap

简介