原创

Java中HashMap(JDK1.7)源码学习

1. 简介

1.1 类定义

继承AbstractMap,实现了Map、Cloneable、Serializable接口。

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

1.2 相关介绍

file

2. 数据结构

2.1 具体描述

HashMap 采用的数据结构(拉链法) = 数组(主) + 单链表(副),具体描述如下:
file

2.2 拉链法示意图

计算出数据的hash值,找到数据应该中数组中插入的位置,如果hash值相同,采用单链表形式插入到链表的头部。

所谓 “拉链法” 就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。
file

2.3 存储流程

对存储流程有个大概印象,后面会有源码分析:

file

2.4 数组元素链表节点的实现类

HashMap中的数组元素、链表节点采用Entry类实现,数组的hash值、键、值、链表信息都存储在Entry对象中。

static class Entry<K,V> implements Map.Entry<K,V> {

    // 键
    final K key;

    // 值
    V value;

    // 链表下一结点
    Entry<K,V> next;

    // key的hash值
    int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

3. 源码分析

  • NUll存在了数组的数组的第一个(索引为0),并不代表只有null,hash计算得出下表为0的也在此处。
  • 添加的时候初始化数组长度,先扩容在添加元素,通过key算出hash得出其在数组中的索引下标,如果hash值存在就放在链表中头部,不存在就直接放在数组中。
  • 如果删除的是首结点,则将下一个结点作为首结点放在数组,如果删除的不是首结点,则将下一个结点提前

3.1 属性说明

// 默认的数组大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大的容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的负载系数
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 用来判断是否初始化的空数据
static final Entry<?,?>[] EMPTY_TABLE = {};

// 存放数组数据的对象。(数组+链表中的数组)
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

// hashmap中存放Entry对象的个数(数组加链表)
transient int size;

// 扩容阈值 = 容量 x 负载系数,达到阀值时扩容。
int threshold;

// 负载系数
final float loadFactor;

// 修改次数
transient int modCount;

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

3.2 构造函数

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;
    threshold = initialCapacity;
    init();
}

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

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

public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);

    putAllForCreate(m);
}

3.3 put方法

  • 如果数组是空时候就初始化,继续。
  • 如果key为null就在table[0]添加/更新value,跳出。
  • 计算key的hash值
  • 计算hash值的数组下标
  • 循环数组下标处的链表
    • 相等就更新
    • 不相等就添加
      • 判断数组是否需要扩容,需要就扩容,并将旧数据复制到新数组上
      • 增加数据
public V put(K key, V value) {
    // 如果是空数组,就初始化哈希表
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 如果key为null时候操作
    if (key == null)
        return putForNullKey(value);
    // 计算key的hash值
    int hash = hash(key);
    // 得到数组下表
    int i = indexFor(hash, table.length);
    // 循环链表中的元素,如果存在就更新value值
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 如果hash值并且key值相等,则更新value。
        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 void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);
    // 计算扩容因子
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 初始化数组
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

key为空时添加值:

private V putForNullKey(V value) {
    // key为null的数据默认放在数组0位置
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

计算key的哈希值:

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

计算数组下表:

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

判断是否需要扩容并调用增加元素方法:

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果hashmap大小大于等于加载因子并当前添加值不是null就触发扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩容数组的2倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        // 重新计算数组下表
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

数组扩容逻辑:

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

旧数组数据转移到新扩容数组上:

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 ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

实际增加逻辑:

void createEntry(int hash, K key, V value, int bucketIndex) {
    // 得到当前索引处的数据
    Entry<K,V> e = table[bucketIndex];
    // 添加在当前索引处的头部
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

3.4 get方法

  • 获取的key是null就去table[0]处找
  • 不是循环对应数组下标处的链表获取key处的Entry对象
public V get(Object key) {
    // 如果key为null,就去table[0]处取数据
    if (key == null)
        return getForNullKey();
    // 如果不是就循环对应数组下标处的链表获取key处的Entry对象
    Entry<K,V> entry = getEntry(key);
    // 没找到返回null,否则获取对应的值
    return null == entry ? null : entry.getValue();
}

获取key为null处的值:

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

循环对应数组下标处的链表获取key处的Entry对象:

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    // 计算key的hash值
    int hash = (key == null) ? 0 : 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;
}

3.5 remove方法

  • 计算key的hash
  • 根据hash找到数组下标位置
  • 遍历数组下标位置的链表找到要删除的Entry对象
    • 如果删除的是首结点,则将下一个结点作为首结点放在数组
    • 如果删除的不是首结点,则将下一个结点提前
public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

通过key删除Entry对象:

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : 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;
}
正文到此结束
本文目录