哈希表总结以及哈希表在Java和Redis中的实现

本文首先简单总结了哈希表，然后考虑了哈希表在Java和Redis中的实现，最后得出结论。如果有某个主题，您已经熟悉它，那么您可以直接跳到文章末尾的比较和总结部分。

哈希表概述

Objective-C Dictionary NSDictionary底层其实就是哈希表。其实大部分语言都是通过哈希表来实现字典的，比如Swift，我已经分析过字典实现的原理。

在讨论哈希表之前，我们先标准化一下接下来会用到的一些术语。儒家表的本质是一个数组。数组的每个元素称为一个桶，桶中存储键值对。

哈希表记录过程如下：

1. 根据密钥计算出这个哈希值h。
2. 假设盒子的数量为n，那么这个键值对应该放在第(h % n)第个盒子中。
3. 如果盒子已经有键值对，可以使用开放寻址方式或者拉链方式解决冲突。

当使用哈希拉链法解决冲突时，每个盒子实际上是一个链表，属于同一个盒子的所有键值对都被排序到链表中。

哈希表还有一个重要的属性：负载因子，用于衡量

哈希表的空/满程度。也能在一定程度上反映查询的有效性。计算公式如下： ：

负载因子=键值对总数/盒子数量

负载因子越高，哈希表越满，越容易引起冲突和冲突降低性能。所以，如果负载因子大于某个常数（可能是1或0.75等），哈希表就会自动扩展。

当哈希表自动扩展时，它通常会创建两倍于原始数量的盒子。因此，即使键的哈希值保持不变，取剩余盒子数量的结果也会发生变化，因此Storage位置中所有键值对的值都可能发生变化。这个过程也称为重新哈希。

扩大儒家表并不总能有效解决负载系数过高的问题。假设所有key的儒家值都相同，那么即使扩容后它们的位置也不会改变。虽然负载因子降低了，但是每个盒子实际存储的链表长度并没有改变，所以哈希表的查询性能无法得到提升。

根据上面的总结，细心的读者可能会发现哈希表存在两个问题：

1. 如果初始哈希表的单元格较多，扩容时需要重做哈希表并移动数据，这会对性能产生较大的影响。
2. 如果哈希函数的设计不合理，哈希表在极端情况下会变成性能极低的线性表。

我们分别通过Java和Redis的源码来了解以上问题，并看看他们的解决方案。

Java 8 中的哈希表

JDK 代码是开源的，可以在这里下载。您要查找的 HashMap.java 目录位于 openjdk/jdk/src/share/classes/java /util/HashMap.java。

HashMap是一种基于HashTable的数据结构。基于标准的哈希表，支持多线程操作和空键值。

HashMap 中定义了几个常量：

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 int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

一一解释一下上面的常量：

1. DEFAULT_INITIAL_CAPACITY：初始容量，默认创建 16 个盒子。盒子的数量不能太多或太少。 。如果太少，很容易引发扩张。如果太多的话，查哈希表会比较慢。
2. MAXIMUM_CAPACITY：哈希表的最大容量。一般来说，只要内存足够，哈希表就没有问题。
3. DEFAULT_LOAD_FACTOR：默认负载系数。因此，如果键值对的数量大于16 * 0.75 = 12，就会触发扩容。
4. TREEIFY_THRESHOLD：如上所述，如果哈希函数不合理，即使扩容也无法减少装箱链表的长度，所以Java的解决方案是使其成为链表中的红黑树。太长。该值表示如果给定框中的链表长度大于8，则可以将其转换为树。
5. UNTREEIFY_THRESHOLD：如果展开哈希表，发现链表长度小于6，则树折叠回链表。
6. MIN_TREEIFY_CAPACITY：变成树之前有一个判断。仅当键值对数量大于64时才进行转换。这是为了避免在创建哈希表的初始阶段将多个键值对添加到同一个链表中而导致不必要的转换。

学过概率论的读者可能知道，理想条件下，哈希表每个方框内的元素数量服从泊松分布：

当负载因子为0.75时，上式中的λ近似相等。变为0.5，所以框中的元素个数与概率的关系为： 0.0 0157952

50.0001579560.000013167 0.0000009480.00000006

这就是为什么会出现这种现象：长度链接列表黑名单的数量变为 8，并且如果该框超出了 proring，则树将来会变为红色。在正常情况下很小，可以忽略不计。如果出现这种情况，几乎可以归咎于儒家功能结构的问题。

Java的哈希表设计在一定程度上避免了由于哈希函数不合适而带来的性能问题。每个框中的链表可以与红黑树进行交换。

Redis

Redis是一个高效的键值缓存系统，也可以理解为基于键值对的数据库。哈希桌的设计有很多值得学习的地方。我会在不影响源码逻辑的情况下，尽可能的简化，突出重点。

数据结构

在Redis中，字典是dict类型的结构，定义于src/dict.h5❀ dictt 是一种结构，用于存储数据。注意，我们定义了一个长度为2的数组，引入它是为了解决扩展缓慢的问题。后面会详细介绍其原理。扩张时还需要rehasidx。我们先看一下dicttht的定义：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long used;
} dictht;

可以看出，该结构体中包含了table中的二维数组。元素类型为dictEntry，对应存储的key。值对：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

从指针next和二维数组可以看出，Redis 哈希表使用拉链方式解决冲突。

整个字典的层次结构如下所示：

添加元素

向字典中添加键值对的底层实现如下： t用于判断哈希表是否为的函数修改的。所谓重孔，就是在扩容的过程中，原来的键值对必须改变位置。为了优化 哈希 的体验，Redis 一次只移动一个盒子的内容，这将在下一节中详细解释。

如果你仔细阅读光标行为部分，你会发现新输入的键值对被放置在框中链表的头部，而不是在尾部继续添加。这个细节上的改变至少带来两个好处：

1. 查找链表末尾的时间复杂度为O(n)，或者必须使用额外的内存地址来存储链表末尾的位置。头部插入方式节省了插入时间。
2. 使用数据库系统，通常更有可能更频繁地检索最近输入的数据。主插法可以节省您搜索的时间。

增量扩展

增量扩展是指当再次需要使用哈希时，一次只迁移框中的一个链表，这样在扩展过程中不会出现明显的性能下降。

为了表示哈希表正在扩展，我们使用结构rehashidx，即数据当前正在迁移到哪个框。由于该结构中实际上有两个哈希表，因此当哈希表扩展时添加新的键值对时，我们首先将盒子数据从第一个哈希表移动到第二个哈希表，然后将键值对被添加到第二个哈希表中。

上面的方法dictAddRaw有两条代码语句：

if (dictIsRehashing(d)) _dictRehashStep(d);
// ...
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

第二条语句用于选择添加哪一个哈希表，第一条语句是迁移rehashidx链表在位置。这实际上调用了dictRehash(d,1)，这是一步迁移。 dictRehash功能实现如下：

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    return 1;
}

这段代码比较长，但是不难理解。它由一个 while 循环和一个 if 语句组成。对于一步迁移，外部 while 循环没有意义，可以在内部拆分为两个 while 循环。

第一个循环用于更新rehashidx的值。由于有些盒子是空的，所以rehashidx每次不会从原来的位置前进一位，而是可以前进多次。位置，但不超过10个。第二个循环用于从链表中复制数据。

极端情况下，如果发现旧的哈希表完全迁移，则释放旧的哈希表的内存，并将新的哈希表分配给旧的哈希表。最后rehashidx重置为-1，表示硬哈希过程结束。

哈希默认函数

与Java不同，Redis提供了一个函数void *键类型哈希函数，即可以通过任意类型的键指针获取哈希的值。具体算法在函数dictGenHashFunction中定义。由于代码太长并且包含一些位事务，因此不显示。

它的实现原理是根据指针的地址和该内存的长度来获取内存中的一个值，并将其放入一个数组中。可以看出这个数组只由0和1组成。然后用这些数字做哈希动作。因此，即使两个指针指向的地址不同，只要内容相同，也能得到相同的哈希值。

归纳比较

首先我们回顾一下Java和Redis的解决方案。

Java的优点是，如果哈希函数不合理，链表过长，则使用红黑树来保证插入和检索的效率。缺点是当哈希表比较大时，功率增大时瞬时效率下降。

Redis 通过增量扩展来解决这个缺点。不过，如何实现zipper方法（替换在链表顶部）是值得学习的。 Redis还提供了默认的哈希特性，该特性已经过广泛测试并且运行良好，避免了链表过长的问题。

Objective-C 实现与 Java 类似。如果我们需要重写 isEqual() 方法，我们还需要重写 hash 方法。两种语言并没有提供共同的默认哈希函数，主要是因为方法isEqual()可以被重写，可以认为两个内存数据不同的对象在语义上是相同的。如果使用默认的哈希函数，你会得到不同的哈希值，两个对象会同时添加到NSSet，这可能会破坏我们的预期结果。

据我了解，Redis不支持重写哈希方法。 Redis难道没有想过这个问题吗？其实我们需要从Redis的定位说起。作为一个高效的键值存储系统，它的键不是对象，而是用于唯一标识对象的标签。

一般情况下，如果要存储用户信息，键值可以是：user:100001。 Redis 只关心键内存中的数据，因此任何可以用二进制表示的东西（例如图像）都可以用作键。Redis支持的数据结构包括哈希表和集合，但数据类型只能是字符串。因此，Redis不考虑对象相等性，可以提供默认的哈希功能。

Redis、Java、Objective-C的异同再次证明了一件事：

没有完美的架构，只有满足需求的架构。

总结

回到文章开头的问题，有两个字典，分别存储100和10000个数据单元。如果使用不存在的键来查找数据，哪个字典更快？ ？

完整的答案是：

由于自动扩展和哈希的默认功能，两个搜索在红色中同样快。在Java和Objective-C中，如果哈希函数不合理，返回值过于集中，会让大型字典变慢。因为Java有链表和红黑树交换机制，所以搜索时间是对数增长而不是线性增长。理想的哈希函数，无论字典有多大，查找速度都是一样的。

最后，我整理了本文提到的知识点。希望您看完文章后能够更加清晰、透彻地理解以下问题：

1. 哈希表中负载因子的概念
2. 哈希表扩展的过程以及对搜索性能的影响
3. 优化哈希表扩展速度，优化拉链方式插入新元素，优化链表过长的情况
4. 不同语言和使用场景的交易

参考资料

1. ReleHaseshMapp源码vs Hashtable vs HashSet
2. 泊松分布
3. Redis源代码
4. Redis数据类型和抽象介绍

作者：https://www.bestswifter。 im/post/57a3e43e8ac247005f19117e
来源：掘金
版权归作者所有。商业转载请联系作者获取授权。非商业转载请注明出处。