从代码层读懂HashMap的实现原理

概述

　Hashmap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。它的key、value都可以为null，映射不是有序的。 　　 　　 Hashmap不是同步的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

Map map = Collections.synchronizedMap(new HashMap());

HashMap 中两个重要的参数：“初始容量” 和 “加载因子”。 容量： 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量 加载因子： 是哈希表在其容量自动增加之前可以达到多满的一种尺度（默认0.75）。　 当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构，桶数Ｘ２）。 加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少, 好处是:冲突的机会减小了,但:空间浪费多了.

HashMap数据结构

Hashmap本质是数组加链表。通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样，然后再计算出数组下标，如果多个key对应到同一个下标，就用链表串起来，新插入的在前面。

先来看看HashMap中Entry类的代码：

static class Entry implements Map.Entry {
    final K key;
    V value;
    // 指向下一个节点
    Entry next;
    final int hash;
    // 构造函数。
    // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
    Entry(int h, K k, V v, Entry n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    public final K getKey() {
        return key;
    }
    public final V getValue() {
        return value;
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    // 判断两个Entry是否相等
    // 若两个Entry的“key”和“value”都相等，则返回true。
    // 否则，返回false
    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }
    // 实现hashCode()
    public final int hashCode() {
        return (key==null   ? 0 : key.hashCode()) ^
               (value==null ? 0 : value.hashCode());
    }
    public final String toString() {
        return getKey() + "=" + getValue();
    }
    // 当向HashMap中添加元素时，绘调用recordAccess()。
    // 这里不做任何处理
    void recordAccess(HashMap m) {
    }
    // 当从HashMap中删除元素时，绘调用recordRemoval()。
    // 这里不做任何处理
    void recordRemoval(HashMap m) {
    }
}

可以看出HashMap就是一个Entry数组，Entry对象中包含了键和值两个属性。

HashMap源码分析 HashMap共有4个构造函数,如下：

• HashMap() 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
• HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
• HashMap(int initialCapacity, float loadFactor) 构造一个带指定初始容量和加载因子的空 HashMap。
• HashMap(Map m) 构造一个映射关系与指定 Map 相同的新 HashMap。

HashMap提供的API方法：

• void clear() 从此映射中移除所有映射关系。
• Object clone() 返回此 HashMap 实例的浅表副本：并不复制键和值本身。
• boolean containsKey(Object key) 如果此映射包含对于指定键的映射关系，则返回 true。
• boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回 true。
• Set entrySet() 返回此映射所包含的映射关系的 Set＜Map.Entry＞ 视图。
• V get(Object key) 返回指定键所映射的值；如果对于该键来说，此映射不包含任何映射关系，则返回 null。
• boolean isEmpty() 如果此映射不包含键-值映射关系，则返回 true。
• Set keySet() 返回此映射中所包含的键的 Set＜Ｋ＞ 视图。
• V put(K key, V value) 在此映射中关联指定值与指定键。
• void　 putAll(Map< extends K, extends V> m) 将指定映射的所有映射关系复制到此映射中，这些映射关系将替换此映射目前针对指定映射中所有键的所有映射关系。
• V remove(Object key) 从此映射中移除指定键的映射关系（如果存在）。
• int 　size() 返回此映射中的键-值映射关系数。
• Collection values() 返回此映射所包含的值的 Collection 视图。

HashMap源码：

package java.util;
import java.io.*;
public class HashMap
    extends AbstractMap
    implements Map, Cloneable, Serializable
{
    //  默认的初始容量（容量为HashMap中桶的数目）是16，且实际容量必须是2的整数次幂。 
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
    static final int MAXIMUM_CAPACITY = 1  MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor