HashMap分析

内部节点类

class Node<K,V> {
    // 键值对
    private K key;
    private V value;
  
    // 链表，后继
    private Node<K,V> next;
  
    public Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
  
    public Node(K key, V value, Node<K,V> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

成员变量

// 默认初始容量
final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子
final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树的长度阈值
final int TREEIFY_THRESHOLD = 8;
// 红黑树退化成链表的长度阈值
final int UNTREEIFY_THRESHOLD = 6;
// 链表转红黑树时，要求数组的最小长度
final int MIN_TREEIFY_CAPACITY = 64;
// 桶数组，每次2倍扩容，允许长度为0
transient Node<K,V>[] table;
// key-value映射的数量
transient int size;
// 修改内部结构的次数
transient int modCount;

构造方法

// 无参构造器 
public ThirdHashMap() {
    buckets = new Node[DEFAULT_CAPACITY];
    size = 0;
}
// 有参构造器
public ThirdHashMap(int capacity) {
    buckets = new Node[capacity];
    size = 0;
}

散列函数

private int getIndex(K key, int length) {
    // 获取hash code
    int hashCode = key.hashCode();
    // 和桶数组长度取余
    int index = hashCode % length;
    return Math.abs(index);
}

put方法

基本逻辑：

• 获取元素插入位置
• 当前位置为空，直接插入
• 位置不为空，发生冲突，遍历链表
• 如果元素key和节点相同，覆盖，否则新建节点插入链表头部

public void put(K key, V value) {
    if(size >= buckets.length * LOAD_FACTOR) resize();
    putVal(key, value, buckets);
}
private void putVal(K key, V value, Node<K, V>[] table) {
    // 获取位置
    int index = getIndex(key, table.length);
    Node node = table[index];
    // 插入的位置为空
    if(node == null) {
        table[index] = new Node<>(key, value);
        size++;
        return;
    }
    // 插入位置不为空，说明发生冲突，使用链地址法，遍历链表
    while(node != null) {
        // 如果key相同，就覆盖掉
        if((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) {
            node.value = value;
            return;
        }
        node = node.next;
    }
    // 当前key不在链表中，插入链表头部
    Node newNode = new Node(key, value, table[index]);
    table[index] = newNode;
    size++;
}

get方法

通过散列函数获取地址。

public V get(K key) {
    // 获取key对应的地址
    int index = getIndex(key, buckets.length);
    if(buckets[index] == null) return null;
    Node<K,V> node = buckets[index];
    // 查找链表
    while(node != null) {
        if((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) {
            return node.value;
        }
        node = node.next;
    }
    return null;
}

扩容方法

• 创建两倍容量的新数组
• 将当前桶数组的元素重新散列到新的数组
• 新数组置为map的桶数组

private void resize() {
    // 创建一个两倍容量的桶数组
    Node<K,V>[] newBuckets = new Node[buckets.length * 2];
    // 将当前元素重新散列到新的桶数组
    rehash(newBuckets);
    buckets = newBuckets;
}
/**
 * 重新散列当前元素
 *
 */
private void rehash(Node<K,V>[] newBuckets) {
    // map大小重新计算
    size = 0;
    // 将旧的桶数组元素全部刷到新的桶数组里
    for(int i = 0;i<buckets.length;i++) {
        // 为空，跳过
        if(buckets[i] == null) {
            continue;
        }
        Node<K,V> node = buckets[i];
        while(node != null) {
            // 将元素放入新数组
            putVal(node.key, node.value, newBuckets);
            node = node.next;
        }
    }
}

参考

[1] 牛客网，手写HashMap。https://www.nowcoder.com/discuss/997806

[2] jdk1.8 HashMap源码