在Java中

在Java中hash表的底层数据结构与扩容等已经是面试集合类问题中几乎必问的点了。网上有对源码的解析已经非常详细了我们这里还是说说其底层实现。

基础架构

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于等于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    // 当桶(bucket)上的结点数小于等于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小容量
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table;
    // 一个包含了映射中所有键值对的集合视图
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;
    // 阈值(容量*负载因子) 当实际大小超过阈值时，会进行扩容
    int threshold;
    // 负载因子
    final float loadFactor;
}

本文所有Java代码均来自JavaGuide（HashMap 源码分析 | JavaGuide），这里主要就是定义一些必要的常量，被用于哈希表的创建参数，扩容参数等待。

然后就是hash表中的Node节点的数据结构，我们的k-v键值对就存储在一个Node类里面。在jdk1.7前其实与redis中的字典Dictionary数据结构中的hash表十分类似，即采用线性搜索和拉链法。在jdk1.8 及以后版本1中，添加了树化，即当节点数大于8就会将当前节点转化为红黑树，这样做的目的主要是为了增加搜索效率，红黑树的时间复杂度为O(log n)如果没有树化链表查询的时间复杂度为O(n) 。接下来就看看JavaGuide中给出的节点类：

链表节点：

// 继承自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
       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; }
        // 重写hashCode()方法
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        // 重写 equals() 方法
        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;
        }
}

树节点：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // 父
        TreeNode<K,V> left;    // 左
        TreeNode<K,V> right;   // 右
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;           // 判断颜色
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        // 返回根节点
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
       }

resize()

然后我们来重点讲一讲resize()扩容这个方法。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 超过最大值就不再扩充了，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没超过最大值，就扩充为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 创建对象时初始化容量大小放在threshold中，此时只需要将其作为新的数组容量
        newCap = oldThr;
    else {
        // signifies using defaults 无参构造函数创建的对象在这里计算容量和阈值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // 创建时指定了初始化容量或者负载因子，在这里进行阈值初始化，
    	// 或者扩容前的旧容量小于16，在这里计算新的resize上限
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 把每个bucket都移动到新的buckets中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    // 只有一个节点，直接计算元素新的位置即可
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 将红黑树拆分成2棵子树，如果子树节点数小于等于 UNTREEIFY_THRESHOLD（默认为 6），则将子树转换为链表。
                    // 如果子树节点数大于 UNTREEIFY_THRESHOLD，则保持子树的树结构。
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

在Java的hashmap中，在jdk1.8以后是通过负载因子的判断来选择是否进行resize()方法默认负载因子是0.75。如果存储数据与当前容量之比为0.75就会进行扩容。同时当我们存储数据过多时，无论我们的hash算法做了什么样的优化，一定还是会有hash冲突的存在，所以为了解决冲突，我们使用拉链法。在插入数据时，我们采用的方式是将已存在hashmap中的键值对的值与插入的值进行比较，如果二者相等就进行覆盖，如果二者不相等就使用尾加法加载链表尾部（在redis5中，使用的是equals()进行比较，因为redis存储的所有值都是String字符串。）。我们将一个拉链称之为一个哈希桶。但是我们试想如果一个桶的节点过于多了，那么我们查找时遍历起来是很花费时间的，在hashtable中使用的是线性搜索法加拉链法来解决这个问题的，但是如果我们一直盲目使用线性搜索法的话，（我们暂且将线性搜索法占据的hash表数组槽位与hash表当前容量的比值称为线性搜索负载因子）当线性搜索负载因子过大时，我们的hash表的查找效率会受到极大的影响。所有在jdk1.8后的树化则很好解决了这个问题，即当拉链上的节点树大于8时，会先对数组容量进行判断，如果小于64先扩容(hashmap扩容都为2倍扩容)，否则进行拉链法。(为什么先扩容呢？因为hashmap的hash函数计算与容量有关所以扩容后会得到新的hash值，避免了hash冲突，相较于红黑树的遍历，我们肯定更优先考虑的是这种做法)

在Golang中

基础架构

type hmap struct {
    count int
    flags uint8
    B uint8
    noverflow uint16
    hash0 uint32
    buckets unsafe.Pointer
    oldbuckets unsafe.Pointer
    nevacuate uintptr
    
    extra *mapextra
}


type mapextra struct {
    overflow *[]*bmap
    oldoverflow *[]*bmap
    nextOverflow *bmap
}

• count 表示当前hash表中的元素。

• B 表示当前hash表持有的 buckets (即桶数组)数量，由于hash表中桶数量都为2的倍数，所以该字段会存储对数。（这里和redis的hash表一样，在redis的rehash过程中，需要先创建一个2倍旧数组长度的新数组，然后进行hash桶迁移）。

• oldbuckets是哈希表在扩容时用于保存之前buckets的字段，它的大小是当前buckets的一半。

在go的hashmap中，我们使用溢出桶来降低扩容频率，本质上就是预先分配几个数组空间用于存储超出容量的k-v

扩容方法

• 开放寻址法

  • 其实就是线性搜索法。简而言之就是依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表，当我们向当前哈希表写入新数据时，如果发生了冲突，就会将键值对写入下一个索引不为空的位置。开放寻址法中对性能影响最大的是装载因子，它是数组中元素数量与数组大小的比值。随着装 载因子的增加，线性探测的平均用时会逐渐增加，这会影响哈希表的读写性能。当装载率超过70% 之后，哈希表的性能就会急剧下降，而一旦装载率达到100%,整个哈希表就会完全失效，这时查找 和插入任意元素的时间复杂度都是O(n)，我们需要遍历数组中的全部元素，所以在实现哈希表时一 定要关注装载因子的变化。

• 拉链法

  • 和jdk 1.7 一样，就不做过多解释。

在go中的k-v添加我们需要注意的是当插入的k-v小于25时会以如下方式插入：

hash := make(map[string]int, 3)
hash["1"] = 1
hash["2"] = 2
hash["3"] = 3

如若大于25个，就会分别创建两个数组，分别存储k 和 v，然后以遍历形式插入。

言归正传，在go的hashmap中扩容条件为：装在因子超过6.5 || 哈希表使用太多溢出桶。

同时由于在go的hashmap的扩容不是原子性的所以需要判断以避免二次扩容（这和redis也一样，增删改查需要判断当前数据库的hash表是否在进行rehash）。

扩容数据结构

说了这么多，接下来我们就来重点介绍go的hashmap扩容的数据结构变化。runtime. evacuate会将一个旧桶中的数据分流到两个新桶，所以它会创建两个用于保存分配 上下文的runtime.evacDst结构体，这两个结构体分别指向了一个新桶。

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
    newbit := h.noldbuckets()
    if !evacuated(b) {
    var xy [2]evacDst
    x := &xy[0]
    x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
    x.k = add(unsafe.Pointer(x.b), dataOffset)
    x. v = add(x.k, bucketCnt*uintptr(t.keysize))
    y ：= &xy[1J
    y. b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
    y.k = add(unsafe.Pointer(y.b), dataOffset)
    y.v = add(y.k, bucketCnt*uintptr(t.keysize))
}

go中的hashamp扩容分为等量扩容和翻倍扩容，如果是前者就只初始化一个桶，如果是翻倍扩容，就会初始化两个桶。会把一个链表数据分到新表两个位置，将8个节点分流到两个桶中（这里获取桶位置采用取模或者位运算来得到数据存储的桶位置），然后将k的指针指向两个桶位置。

在数据查询时，会先判断是否在进行分流，如果在进行，就先会从旧桶中读取数据。相较于Java的hashmap它不会一次性将所有的元素重新哈希，而是在每次插入元素时，都会将一部分元素移动到新的桶中。这样可以避免一次性的大量计算，但可能会导致一段时间内的查询效率稍低。