06.Java 集合 - HashMap

基本概念

HashMap 实现了 Map 接口，继承自 AbstractMap。它接受 Map 接口定义的键映射到值的规则。

HashMap 内部通过维护着一个哈希表来存储元素。

HashMap 是非线程安全的。

HashMap 接受 key 为 null 的键值对，并统统把它们存放在哈希表的第一个位置。

内部构造

1.Entry

Entry，即节点，是 HashMap 中一个重要的静态内部类，它由一个键值对（k，v）、指针域（next）、哈希值（hash）构成，不同的节点可组成一个单向链表。

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

    // 构造函数
    Entry(int h, K k, V v, Entry<K, V> n) {
        key = k; 
        value = v;
        hash = h;
        next = n;
    }

    // 省略部分代码...
}

根据代码，可得结构图如下：

06.Java 集合 - HashMap

2.构造函数

先来看 HashMap 内部几个重要的成员变量：

// 数组（由节点组成），即哈希表
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;

// 空的哈希表
static final Entry<?, ?>[] EMPTY_TABLE = {};

// 负载因子，表示哈希表的饱和程度
final float loadFactor;

// 临界值，哈希表的元素数量超过该值时需要做扩容操作
int threshold;

明白了这个几个成员变量的概念后，再来看它的构造函数：

// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = f;

// 默认容量（2^4 =16）、最大容量（2^30）
static final int DEFAULT_INITIAL_CAPACITY =  << ; 
static final int MAXIMUM_CAPACITY =  << ;

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

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

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < ){
        //抛出异常...
    }   
    if (initialCapacity > MAXIMUM_CAPACITY){
        initialCapacity = MAXIMUM_CAPACITY;
    }   
    if (loadFactor <=  || Float.isNaN(loadFactor)){
        //抛出异常...
    }

    this.loadFactor = loadFactor;
    threshold = initialCapacity;

    // 空方法，留给子类实现
    init();
}

观察它的构造函数，HahsMap 在被创建时需要指定两个变量：初始容量、加载因子。若不指定时，默认会构建一个初始容量为 16，加载因子为 0.75 的哈希表。

关于哈希表，现在可以知道的是它是由多个单向链表组成的数组，根据描述可以绘制下图：

06.Java 集合 - HashMap

3.初始化

HashMap 在其构造函数中并未做初始化。即 table（哈希表）默认是容量为 0 的空哈希表。

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

HashMap 只有在执行添加/修改操作时，会对其进行初始化。

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        // 初始化...
        inflateTable(threshold);
    }

    // 省略部分代码...
}

关键来看 inflateTable：

private void inflateTable(int toSize) {
    // 设置哈希表的容量，为比 toSize（临界值）大的最小 2 的倍数
    // 假设 toSize = 9 ，则 capacity = 16
    int capacity = roundUpToPowerOf2(toSize);

    // 关键 -> 临界值 = 负载因子*容量
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + );

    // 创建哈希表
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

操作方法

1.扩容检测

由于 HashMap 由哈希表组成，同样有着容量固定的缺陷，所以在每次添加操作之前都需要进行扩容检测，以保证整个哈希表的元素数量不会过于饱和。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + );
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K, V> e : table) {
        while (null != e) {
            Entry<K, V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ?  : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

static int indexFor(int h, int length) {
    return h & (length - );
}

2.添加（修改）操作

在 HashMap 中执行添加、修改操作都通过 put 方法来实现，下面来看它的源码：

public V put(K key, V value) {
    // 第一次添加时，哈希表为空则进行扩容操作
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }

    // 判断 key 是否为空，为空则添加到数组的第一个
    if (key == null){
        return putForNullKey(value);
    }

    // 根据 key 的哈希值计算其要放置的数组位置   
    int hash = hash(key);
    int i = indexFor(hash, table.length);

    // 遍历该位置上的链表
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;

        // 判断是否存在相同节点，存在则执行修改操作
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;

            // 空方法，留给子类实现
            e.recordAccess(this);

            return oldValue;
        }
    }

    modCount++;

    // 不存在相同节点，执行添加操作
    addEntry(hash, key, value, i);
    return null;
}

private V putForNullKey(V value) {
    // 关键 -> 当 key 为 null 时，默认存储在数组的第一个位置
    for (Entry<K, V> e = table[]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(, null, value, );
    return null;
}

分析代码， HashMap 的 put 方法的执行过程如下：

判断哈希表是否为空，为空则进行扩容操作
判断要添加的键值对 key 是否为 null，为空则放置到数组第一个位置的链表上
不为空则进行计算键值对的位置，遍历该位置的链表，执行添加或修改操作。

修改操作在上面已经介绍过，具体来看下添加操作：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩充容量
        resize( * table.length);

        // 计算新的数组位置
        hash = (null != key) ? hash(key) : ;
        bucketIndex = indexFor(hash, table.length);
    }

    // 创建新节点，并插入链表
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    // 取得数组 bucketIndex 位置上链表的头结点
    Entry<K, V> e = table[bucketIndex];

    // 将新加入的节点设置为头结点
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

整个过程如下图所示：

06.Java 集合 - HashMap

3.删除操作

在 HahsMap 中的删除操作只有删除指定元素一种：

public V remove(Object key) {
    Entry<K, V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

final Entry<K, V> removeEntryForKey(Object key) {
    // 判断哈希表是否为空，为空返回 null
    if (size == ) {
        return null;
    }

    // 找到该节点所在链表的数组位置，并取得链表的头节点
    int hash = (key == null) ?  : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K, V> prev = table[i];
    Entry<K, V> e = prev;

    // 遍历链表
    while (e != null) {
        Entry<K, V> next = e.next;
        Object k;

        // 判断是否存在该节点
        if (e.hash == hash && 
            ((k = e.key) == key || (key != null && key.equals(k)))) {

            modCount++;
            size--;

            // 判断该节点是否是链表的头节点
            if (prev == e){
                // 设置其下个节点设置为新的头节点
                table[i] = next;
            }else{
                // 修改前节点的指针
                prev.next = next;
            }

            // 空方法，留给子类实现   
            e.recordRemoval(this);
            return e;
        }

        // 准备下一轮遍历
        prev = e;
        e = next;
    }

    return e;
}

分析代码，整个过程跟添加操作大同小异，具体如下：

获取指定节点索引位置。
遍历索引位置的单链表。
存在相同的节点能移除并返回该节点，不存在返回 null

06.Java 集合 - HashMap

4.查询操作

这里介绍下 HashMap 查询时常用的 get 方法：

public V get(Object key) {

    if (key == null){
        return getForNullKey();
    }

    Entry<K, V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
    if (size == ) {
        return null;
    }
    for (Entry<K, V> e = table[]; e != null; e = e.next) {
        if (e.key == null){
            return e.value;
        }   
    }
    return null;
}

final Entry<K, V> getEntry(Object key) {
    if (size == ) {
        return null;
    }

    int hash = (key == null) ?  : hash(key);
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
            return e;
        }   
    }
    return null;
}

这里只贴出源码，不再分析，大致过程如下：

判断 key 是否为空，为空则在数组第一个位置的链表上查询
判断哈希表是否为空，为空返回 null
找到指定位置的链表，遍历链表查询指定元素

06.Java 集合 - HashMap

基本概念

内部构造

1.Entry

2.构造函数

3.初始化

操作方法

1.扩容检测

2.添加（修改）操作

3.删除操作

4.查询操作

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method