深入理解map系列-HashMap（一）

Map系列之HashMap（源码基于java8）

HashMap是我们最常用的map实现之一，这篇文章将会介绍HashMap内部是如何工作的，以及内部的数据结构是怎样的

一、数据结构简图

二、源码解析

首先看下Map接口里常用的几个方法：

代码块1

V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);

上面是常用的主要操作方法，下面来看下map的基本存储单位Entry：

代码块2

interface Entry<K,V> {
        
     K getKey(); //返回当前存储数据里的key

     V getValue(); //返回当前存储数据里的value

     V setValue(V value); //给value赋值
        
     boolean equals(Object o); //重写equals方法

     int hashCode(); //重写hashCode方法
        
}

然后我们来看下HashMap里对该接口的实现：

代码块3

// 基本存储结构，可以看出来这是一个简单的链表结构，这里的实现类叫Node
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; //根据key计算出来的哈希值
        final K key; //数据键
        V value; //数据值
        Node<K,V> next; //下一个数据节点

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }

        public final V getValue()      { return value; }

        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        // 判等，要求k，v必须满足相等才行
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

我们再来看看hash值的计算，在哈希表中，哈希值取决了散列度，最终插入的数据会分布到哪个数组下标下，hash值起着至关重要的作用：

代码块4

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

下面我们来看看具体插入数据时做的操作，具体解释已经加上注释：

代码块5

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        HashMap.Node<K,V>[] tab; //存储链表的数组结构

        HashMap.Node<K,V> p; //被插入的元素链表头部元素

        int n, i; //n表示当前哈希表数组长度，i表示本次插入元素被分配的下标

        if ((tab = table) == null || (n = tab.length) == 0) { //表示哈希表数组还未被初始化
            n = (tab = resize()).length; //初始化，resize用来扩容
        }
        //表示当前（下标由最大下标值和当前元素哈希值位运算得出）位置还没有任何链表结构，这时直接初始化即可
        if ((p = tab[i = (n - 1) & hash]) == null) {
            tab[i] = newNode(hash, key, value, null);
        } else { // 否则，需要进行链表数据插入的操作，注意现在p已经是计算出来的链表头元素了
            HashMap.Node<K,V> e;
            K k;
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k)))) {
                e = p; // 若发现插入的数据跟p哈希值、key完全一致，则直接让新插入的数据等于p即可
            } else if (p instanceof HashMap.TreeNode){ // 结合下面的代码，链表深度大于8后，就是个红黑树结构了，这时启用下面的代码加入新数据
                e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            } else { // 说明插入的是新元素
                for (int binCount = 0; ; ++binCount) { // 遍历链表
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null); //插入链表尾部
                        if (binCount >= TREEIFY_THRESHOLD - 1) // java8新引入的概念，当链表深度大于8时，就转换为红黑树结构了
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k)))) {
                        break; // 若发现遍历过程中存在与插入值一致的，直接break
                    }
                    p = e;
                }
            }
            if (e != null) { // 说明未成功插入
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue; // 返回已存在的旧值
            }
        }
        ++modCount;
        if (++size > threshold) { //新插入值后，满足扩容条件则进行扩容
            resize(); //扩容 
        }
        afterNodeInsertion(evict);
        return null;
    }

由于java8做了根据元素数量，转换成红黑树结构的优化处理，所以上述代码中会掺杂一些相关的代码，这里先不用关心，我们按照最基本的哈希表结构来看就行，下一讲将会分析红黑树结构。

我们接下来来看下get方法：

代码块6

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

然后getNode方法：

代码块7

final HashMap.Node<K,V> getNode(int hash, Object key) {
        HashMap.Node<K,V>[] tab; //哈希表数组
        HashMap.Node<K,V> first, e; //根据hash查找数组内的第一个元素
        int n; K k; // n表示数组长度
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) { // 根据下标（下标由最大下标值和当前元素哈希值位运算得出）获取当前对应第一个元素（链表或者红黑树的根元素）
            if (first.hash == hash && // 检查第一个节点的key是否等于当前查找的key，若等，直接返回
                    ((k = first.key) == key || (key != null && key.equals(k)))){
                return first;
            }
            // 否则继续遍历查找
            if ((e = first.next) != null) {
                if (first instanceof HashMap.TreeNode) { //红黑树结构的查询
                    return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key); 
                }
                // 普通链表结构遍历查询，查到直接返回
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k)))){
                        return e;
                    }
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

ok,上面说完了put和get，现在我们来看下remove，也是先抛开红黑树不谈，只看链表部分，会很容易：

代码块8

public V remove(Object key) {
        HashMap.Node<K, V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
    }

final HashMap.Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
        HashMap.Node<K, V>[] tab; //哈希表数组
        HashMap.Node<K, V> p; //需要被移除的元素所属的根元素
        int n, index; //n表示数组长度，index表示需要被移除元素根元素位于数组的下标值
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
            HashMap.Node<K, V> node = null, e; // node表示最终需要被移除的元素
            K k;
            V v;
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k)))) {
                node = p; // 若根元素就等于需要被移除的元素，则直接将node赋值为p
            } else if ((e = p.next) != null) { // 否则继续往下查找，结构依然分为两种，红黑树暂不看
                if (p instanceof HashMap.TreeNode) {
                    node = ((HashMap.TreeNode<K, V>) p).getTreeNode(hash, key);
                } else {
                    do {
                        if (e.hash == hash &&
                                ((k = e.key) == key ||
                                        (key != null && key.equals(k)))) {
                            node = e;
                            break; // 找到对应的元素，break
                        }
                        p = e; // 找不到对应元素时，让p一直下移（e.next）
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                    (value != null && value.equals(v)))) {
                if (node instanceof HashMap.TreeNode) { //红黑树移除
                    ((HashMap.TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
                } else if (node == p) { // 待移除元素等于根元素时，直接让对应下标下的数组元素赋值为根元素的下一个值
                    tab[index] = node.next;
                } else { //否则，就进行链表正常删除逻辑，让被移除元素的前一个元素（为什么现在的p是前一个元素呢？因为在上述do while操作时已经重新赋值了）的下一个值指向被移除元素的下一个值
                    p.next = node.next;
                }
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

好了，目前基本上把重要的一些操作给介绍完了，现在再看下containsKay这个方法，这个方法极度简单，直接调用getNode方法判空即可：

代码块9

public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
}

本篇的侧重点在于HashMap在使用纯链表时的插入、移除、查找方式，下一篇将会介绍HashMap如何扩容数组、以及在启用红黑树结构下，会如何做插入、移除、查找这几种操作方式。