HashMap源码分析，看一遍就懂！("HashMap源码深入解析，轻松看懂不求人！")

一、HashMap简介

HashMap是Java中非常常用的一个数据结构，它基于散列（Hashing）实现，允许我们以键值对（Key-Value）的形式存储数据。HashMap具有以下几个特点：

• 允许使用null作为键和值
• 键值对无序
• 不允许重复的键
• 查询、插入和删除操作的时间繁复度为O(1)（理想情况下）

二、HashMap的数据结构

HashMap底层采用数组加链表（或红黑树）的结构，当数组中的某个索引位置出现哈希冲突时，会使用链表（或红黑树）来存储具有相同哈希值的不同键值对。

三、HashMap源码分析

下面，我们将从HashMap的构造方法、get方法、put方法、resize方法等方面，对HashMap的源码进行深入分析。

1. 构造方法

HashMap的构造方法首要有以下几个：

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0 || loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity + " or load factor: " +
                                           loadFactor);
    }
    this.loadFactor = loadFactor;
    this.threshold = (int)(initialCapacity * loadFactor);
    this.table = new Entry[initialCapacity];
    init();
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}

HashMap提供了三个构造方法，分别允许用户自定义初始容量、加载因子以及无参构造方法。初始容量即数组的大小，加载因子即当数组中的元素数量大致有数组大小乘以加载因子时，会进行扩容操作。默认加载因子为0.75，是一个时间和空间成本的综合考虑。

2. put方法

put方法用于向HashMap中添加键值对，下面是put方法的源码实现：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry 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;
}

首先，对key进行hash计算，然后计算出在数组中的索引位置。遍历数组该索引位置的链表，如果找到相同的key，则替换其value。如果没有找到相同的key，则调用addEntry方法添加新的键值对。

3. get方法

get方法用于从HashMap中获取指定key对应的value，下面是get方法的源码实现：

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

get方法的实现逻辑与put方法类似，首先计算key的hash值，然后遍历数组该索引位置的链表，找到对应的key后返回其value。

4. resize方法

resize方法用于对HashMap进行扩容操作，下面是resize方法的源码实现：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUN_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

resize方法首先创建一个新的数组，然后遍历原数组中的所有键值对，重新计算它们在新数组中的索引位置，并重新插入。最后，将新数组赋值给table，并更新threshold。

四、总结

HashMap是Java中非常常用的数据结构，其底层采用数组加链表（或红黑树）的结构。通过分析HashMap的源码，我们了解了其构造方法、get方法、put方法和resize方法的实现原理。HashMap的时间繁复度取决于散列函数的设计和散列冲突的处理，理想情况下，HashMap的查询、插入和删除操作的时间繁复度为O(1)。

本文由IT视界版权所有,禁止未经同意的情况下转发