为什么都用哈希,Hash 表的时间复杂度为什么是 O(1)？

生如夏花之灿烂,死如秋叶之静美。—— 泰戈尔 《生如夏花》

写在前面

---

• 博文内容为哈希表的简单认知
• 涉及Hash表的索引计算，长度计算，以及如何减少哈希冲突，一致性哈希认知
• 理解不足小伙伴帮忙指正 :),生活加油

生如夏花之灿烂,死如秋叶之静美。—— 泰戈尔 《生如夏花》

---

Hash 表的时间复杂度为什么是 O(1)

讲 Hash 之前，简单聊聊数组(直接寻址表)

数组

数组是内存中一块连续的空间，并且数组中必须存放相同的类型，所以存放数组只需要记住 首地址的位置就可以，而且数组的长度必须是定长。

以 int 数据类型为例，每个 int 占 4 字节内存空间，所以对一个一个长度单位为 5 的整形数组，所占用的字节为 4*5=20 字节，知道首地址，数组每个元素定长，可以轻易算出每个数据的内存下标地址。

+------------+------------+------------+------------+------------+
| arr[0]     | arr[1]     | arr[2]     | arr[3]     | arr[4]     |
+------------+------------+------------+------------+------------+
| 内存地址 1  | 内存地址 2   | 内存地址 3  | 内存地址 4  | 内存地址 5   |
+------------+------------+------------+------------+------------+

在这个例子中，arr[0] 存储在内存地址1，arr[1] 存储在内存地址2，依此类推。每个元素之间的间隔是4个字节（一个整数的大小）。

这样，通过首地址和元素的大小，我们可以计算出数组中任意元素的内存地址。

数组的首地址假设为 base_address = 1000，那么：

• arr[0] 的地址是 base_address
• arr[1] 的地址是 base_address + 4
• arr[2] 的地址是 base_address + 8
• arr[3] 的地址是 base_address + 12
• arr[4] 的地址是 base_address + 16

所以只读取数组元素的时候，可以直接通过下标，也就是索引进行读取，即我们常讲的直接寻址，时间复杂度为 O(1). 所以在算法导论中也会把数组称为直接寻址表

随机快速读写是数组的一个特性，在 Java 中有个 标志性接口 RandomAccess 用于表示此类特性，比如我们经常用的 ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  .......
}

这也是常讲 对于 ArrayList 来说 通过索引访问要优于通过迭代器访问。知道索引下标后，下标乘以元素大小，再加上数组的首地址，就可以获得目标访问地址，直接获取数据。通过迭代器方法，需要通过方法先获取索引，中间多了一步，并且最好指定初始容量，数组定长，所以每一次的扩容都要进行一次数组拷贝

在数组的情况下，由于元素是连续存储的，序列化过程可以直接将整个内存块复制到磁盘或网络中，这样可以减少 CPU 的开销，提高效率。所以数组尤其适合于需要高性能数据传输的场景。

相比在链表中，由于节点是分散存储的，序列化时必须遍历每一个节点，将其值逐个写入到连续的内存中，这样不仅需要更多的计算时间，还可能在内存分配上引入额外的开销。

Hash 表

回头来看 Hash 表，数组可以直接寻址，但是缺点很明显，必须定长，元素大小相等,实际中使用的时候，往往可能不知道需要多长，希望是一个动态集合。

这个时候可以定义一个很大的数组，但是存在一种情况，当要存放的元素远远小于定义某个长度的数组的时候，就会造成资源浪费。

所以我们需要一种数据结构来实现上面的功能，可以根据要放的元素动态的定义数组的大小，这也就是哈希表，算法导论中也叫散列表。

索引计算

哈希表会通过哈希函数把要放的元素转换为一个哈希值，往往是一个 Int 型 的数值，如何得到索引，最简单的方法就是余数法，使用 Hash 表的数组长度对哈希值求余， 余数即为 Hash 表数组的下标,使用这个下标就可以直接访问得到 Hash 表中存储的数据。。每次读写元素的时候会计算哈希值得到索引然后读写。

因为哈希函数的执行时间是常量，数组的随机访问也是常量，时间复杂度就是 O(1)。

在编程语言中，为了避免哈希冲突，会对哈希函数的数据做进一步处理，对于 Java 来讲，HashMap 的 hash 方法接收一个 Object 类型的 key 参数，然后根据 key 的 hashCode() 方法计算出的哈希值 h。

然后会执行位运算 h >>> 16（将 h 的高 16 位右移 16 位），然后将结果与原始哈希值 h 进行异或操作（^），最后返回计算得到的哈希值。

Java 的 HashSet 也是基于 HashMap 的只是 Val 做了单独处理。

下面为 HashMap 的扰动函数

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

Object 的 哈希函数是一个原生的方法，即由 JVM 提供，可能通过 C 或者 C++ 实现。

public native int hashCode();    

通过一个具体的例子来解释 Java 中 HashMap 的 hash 方法是如何工作的，以及为什么通过对原始哈希值的高 16 位和低 16 位进行异或操作可以减少哈希冲突

假设我们有一个字符串键 "example"，其 hashCode() 方法返回的原始哈希值为 1047298352 一个 int 值.

即4字节32 位： 0011 1110 0110 1100 1000 0001 0011 0000

原始哈希值：h = 1047298352

• 高 16 位：0011 1110 0110 1100（二进制）
• 低 16 位：1000 0001 0011 0000（二进制）

右移操作：h >>> 16，高位填0，原来的高位变低位

• 结果：0000 0000 0000 0000 0011 1110 0110 1100（二进制）
• 这个操作将原始哈希值的高位信息“复制”到了低位。

异或操作：h ^ (h >>> 16)

• 结果：1047298352 ^ 15980 = 1047560497（十进制）=00111110011011001011111101011100 （二进制）
• 异或操作将高位的信息混合到了低位，使得高位的变化能够影响到低位。

通过对原始哈希值的高 16 位和低 16 位进行异或操作，HashMap 的 hash 方法试图达到以下目的：

• 均匀分布：这种混合操作有助于在哈希表中更均匀地分布键，因为高位的变化现在能够影响到低位，从而减少了只依赖低位导致的分布不均。
• 减少冲突：由于高位信息现在也被考虑在内，因此具有相似高位但不同低位的键更有可能产生不同的哈希值，从而减少了哈希冲突的可能性。

当调用 putVal 方法插入键值对时，会传入通过 hash 方法计算得到的哈希值作为 hash 参数,然后计算索引

if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

这里的 n 为数组的长度，那么数组长度如何确定？

长度计算

索引的问题解决了，那么长度是如何解决的，我们知道既然使用数组，那么一定是定长才行

和 ArrayList 类似，在Java中，Hash 表的长度是有一个一个默认长度的，当负载因子超过阈值时会自动扩容，扩容同样涉及数组拷贝，哈希值计算。所以一般也需要指定初始容量。

所以 Java 中在创建 HashMap 时，会根据初始容量和负载因子来确定实际的对象数组大小。需要注意 HashMap 的内部实现会确保实际容量为最接近且大于或等于给定初始容量的 2 的幂次方。这样可以充分利用位运算的优势，提高哈希表的性能。

实际中指定初始容量后还会进行进一步的运算，例如，如果初始容量为 16，实际对象数组大小将为 16；如果初始容量为 17，实际对象数组大小将为 32（最接近且大于 17 的 2 的幂次方）。

计算方式通过下面的函数

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

获取到长度之后，通过下面的方式获取索引

index = hash_value & (table_size - 1)

可以看到在 Java 中，这里使用了位运算，而不是之前我们讲的取模运算，

位与运算（bitwise AND）和取模运算（modulo operation，使用%符号）都可以用来将哈希值映射到哈希表的索引范围内，但它们的工作原理和适用场景有所不同。

位与运算（bitwise AND） ，当哈希表的大小是2的幂时，可以使用位与运算来计算索引，这种方法的优点是速度快，因为它只涉及一次位运算。但是，它要求哈希表的大小必须是2的幂。

取模运算（modulo operation），取模运算可以用于任何大小的哈希表，不仅限于2的幂：

index = hash_value % table_size

这也是上面为什么要容量是2的幂，除法运算通常比位运算慢，位运算可以直接映射到硬件层面操作。

那么位运算又是如何计算出索引的？这里的原理是基于二进制的特性以及位运算的规则。

首先，数组的大小是 2 的幂次方，例如 16（2^4）。当数组大小为 2 的幂次方时，它的二进制表示形式中只有一个位为 1，其余位为 0。例如，16 的二进制表示为 10000。

使用按位与运算（&）计算索引。

对哈希码和数组大小减 1（例如 15，见上面的公式）进行按位与运算时，实际上是在将哈希码的二进制表示中的高位全部置为 0，只保留低位的数值。这是因为数组大小减 1 的二进制表示形式中，所有低位都为 1，而高位都为 0。例如，15 的二进制表示为 01111。

使用上面Demo中的数据

0011 1110 0110 1100 1000 0001 0011 0000(2)    1047298352(扰动前哈希值)
0011 1110 0110 1100 1011 1111 0101 1100(2)    1047560497(扰动后哈希值 h >>> 16)
0000 0000 0000 0000 0000 0000 0000 1111(2)    15(哈希表容量-1)
& ---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0000(2)    0 (扰动前计算的索引)
0000 0000 0000 0000 0000 0000 0000 1100(2)    12(扰动后计算的索引)

通过按位与运算，我们可以得到哈希码的低 4 位（在这个例子中），这些低 4 位就是我们要找的索引值。这个过程相当于对哈希码进行模运算（取余数），使用位运算来实现会更高效。这里也可以看到扰动函数的作用，利用高位影响低位。

在Java 中当哈希表的元素个数超过容量乘以加载因子（默认为0.75）时，会触发扩容，扩容会重新计算大小，扩容后的大小为。newCap = oldCap << 1 ,即左移一位，增加当前容量的一倍。

......
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 如果扩容后的容量小于最大容量，并且当前容量大于等于默认初始容量
        oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 将阈值也扩容为原来的两倍
}
....

实际上在 Java 中，，如果类实现了哈希方法，会使用自己覆盖的哈希方法，如果关键字是字符串，会使用 BKDR 哈希算法将其转换为自然数，再，对它进行求余，就得到了数组下标。

下面为 字符串类 String 覆写的 哈希函数。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
        }
        return h;
}

哈希冲突

当多个不同的元素通过哈希函数生成的哈希值后计算的索引一样，就会触发哈希冲突

我们看一个生产的 Demo，下面为两个楼宇编码，需要批量生成每栋楼房间的锁号，这里我们通过楼宇编码生成哈希值，拼接到锁号最前面当楼宇标识。

• 西辅楼： RLD836092851942064128
• 西平房： RLD836132304567926784

这里我们有 8 栋楼宇，所以长度为8.

public static void main(String[] args) {
        String b1 = "RLD836092851942064128";
        String b2 = "RLD836132304567926784";

        int b1i = b1.hashCode() & (8 - 1);
        int b2i = b2.hashCode() & (8 - 1);
        System.out.println(b1.hashCode()+"|  "+b1i);
        System.out.println(b2.hashCode()+"|  "+b2i);

    }

可以看到，虽然哈希值不一样，但是算完的索引一样，

-652344316|  4
1275548884|  4

这两个字符串都会落到下标 4 中，这就产生了冲突。就会促发哈希冲突，解决办法一般有两种：

链接法（Separate Chaining）：

落到数组同一个位置中的多个数据，通过链表串在一起。使用哈希函数查找到这个位置后，再使用链表遍历的方式查找数据。Java 中的哈希表就使用链接法解决冲突。在 Java8 之后，链表节点超过8个自动转为红黑树，小于6个会自动转为链表。

链表法即把冲突的元素放到一个链表里面，链表第一个元素地址放到哈希表索引的元素位置。

所以说最坏的情况下，即所有的元素都哈希冲突，时间复杂度为链表的时间复杂度 O(n).

• 优点：
  • 实现简单，容易处理动态扩容。
  • 允许负载因子大于1，能够处理更多的元素。
  • 可以灵活应对哈希冲突，即使哈希表中的桶很少也能保持性能。
• 缺点：
  • 需要额外的内存用于指针存储，因此每个桶可能需要额外的空间，这导致内存使用不连续。
  • 在序列化时，指针和内存的不连续性会导致效率降低，尤其是在需要将整个哈希表序列化并存储到文件时，可能需要更多的时间来处理指针和数据结构。
  • 空桶可能会浪费空间。

开放寻址法

插入时若发现对应的位置已经占用，或者查询时发现该位置上的数据与查询关键字不同，开放寻址法会按既定规则变换哈希函数（例如哈希函数设为 H(key,i)，顺序地把参数 i 加 1），计算出下一个数组下标，继续在哈希表中探查正确的位置，

• 优点：
  • 所有的元素都存储在数组中，避免了指针导致的内存不连续问题。
  • 序列化效率较高，可以直接将内存中的数组映射到磁盘（如 Linux 的 mmap 机制），这对于大规模数据的备份非常高效。
  • 操作系统的内存映射机制自动处理数据的同步，但为了保证数据一致性和准确性，可能还需要显式调用 msync 来确保内存内容被写入磁盘。
• 缺点：
  • 需要考虑负载因子，如果填充太满，性能会显著下降，特别是插入和删除操作可能会退化为线性时间。
  • 如果哈希表太大，扩展时可能会涉及到大量数据的重新计算和复制。

public void put(String key) {
        int index = hash(key);
        while (table[index] != null) { // 线性探测
            index = (index + 1) % capacity; // 循环处理
        }
        table[index] = key;
    }

实际中可能还要做容量检测，避免死循环。在选择冲突解决策略时，需要综合考虑以下因素：

内存使用：如果内存连续性和序列化效率是关键，开放寻址法可能更适合，尤其是在需要高效序列化的情况下。链接法虽然更灵活，但可能会因为指针和内存不连续性导致序列化和备份成本增加。

数据大小和存储：对于大型哈希表，应该关注内存布局和存储策略，采用分块、压缩或稀疏存储等方式来优化序列化过程。

性能和一致性：在使用内存映射等技术时，确保数据的一致性和完整性依然是关键，可能需要额外的同步操作。

如何减少哈希冲突

理论上频繁发生哈希冲突时，会直接影响时间复杂度，所以检索速度会急剧降低，通过哪些手段减少冲突概率？

• 一是调优哈希函数
• 二是扩容

扩容

装载因子（当前元素个数/数组容量）越接近于 1，冲突概率就会越大。不能改变元素的数量，只能通过扩容提升哈希桶的数量，减少冲突。

哈希表的扩容会导致所有元素在新数组中的位置发生变化，因此必须在扩容过程中同时保留旧哈希表和新哈希表。扩容时，需要遍历旧哈希表中的所有元素，并使用新的哈希函数将它们重新放入合适的新哈希桶中。

上面我们讲到 Java 中 HashMap 会在数组元素个数超过数组容量的 0.75 进行扩容， 扩容机制与上面类似，扩容后的容量始终为 2的幂，

比如如何 HashMap 的初始容量设置为 100，那么扩容后的容量将按照以下公式计算：

newCapacity = oldCapacity * 2`

在这种情况下，oldCapacity 是初始容量 100。但是，HashMap 的容量始终是 2 的幂次方，因此实际的初始容量会被调整为大于或等于 100 的最小的 2 的幂次方，即 128（2^7）。

当 HashMap 需要扩容时，新的容量将是当前容量的两倍。因此，如果初始容量为 128，扩容后的新容量将是：

newCapacity = 128 * 2 = 256（2^8）

所以，初始容量设置为 100，扩容后的容量将为 256。这一过程涉及大量数据操作，扩容是一个极其耗时的操作，尤其在元素数量达到亿级时。

所以在初始化的时候制定容量很有必要，会避免多次扩容，同时可以考虑其他的扩容手段，比如渐进式扩容和双缓存技术.

调优哈希函数

上面我们讲到 Java 中 String 类通过 BKDR 哈希算法计算哈希值，这里的 31 为基数，哈希函数为什么基数必须是素数，欢迎小伙伴们留言讨论 ^_^

它的计算量很小：n*31 ，实际上可以通过先把 n 左移 5 位，再减去 n 的方式替换，即（n*31 == n<<5 - n），因为理论上位运算通常比乘法运算更快

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = n<<5 - n + val[i];
            }
            hash = h;
        }
        return h;
    }

也可以在除以一个质数，这里 prime 是一个大质数，用于减少哈希冲突。

public class BKDRHash {
    private static final int BASE = 31; // 基数
    private static final int PRIME = 1000000007; // 质数

    public static int hash(String str) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash * BASE + str.charAt(i)) % PRIME;
        }
        return hash;
    }
}

也可以使用其他的哈希算法，或者双重哈希处理，在分布式场景通过 一致性哈希 来处理数据的均匀分布,分散数据，降低局部密度，提交分布均匀性，减少冲突的概率。

一致性哈希（Consistent Hashing）算法

分布式系统中数据分布和负载均衡会经常使用一种叫 一致性哈希（Consistent Hashing）的技术。用于解决在集群节点变化（如添加或移除节点）时，如何最小化数据迁移的问题(Ceph,Redis )。以及在网络协议层流量负载均衡如何选择合适的后端节点(haproxy)。

一致性哈希由 哈希环，数据映射，负载均衡 组成

哈希环：

一致性哈希将整个哈希值空间视为一个虚拟的环。每个节点（如服务器）和数据项（如缓存中的数据）都通过哈希函数映射到这个环上。

比如 Redis Cluster 将整个数据集划分为 16384 个哈希槽。每个键通过哈希函数（CRC16）计算出一个哈希值，然后对 16384 取模，得到该键对应的哈希槽。每个节点负责一部分哈希槽。

节点和数据映射：

节点和数据项都被哈希到这个环上。数据项被存储在顺时针方向的第一个节点上。例如，如果数据项 A 被哈希到位置 x，而节点 N1 在 x 的顺时针方向上，那么 A 就存储在 N1 上。

负载均衡：

通过将数据均匀地分布在环上，可以实现负载均衡。即使添加或删除节点，也只会影响到少量数据项的迁移。总体的哈希容量不变，所以计算完的哈希值不会变，只是对 Hash 空间细划。

一致性哈希的优势

最小化数据迁移：当节点加入或离开时，只需重新映射少量数据项，而不是重新分配所有数据。这使得系统在扩展或缩减时更为高效。

动态扩展：系统可以在不影响现有数据的情况下动态扩展，增加新的节点或移除旧的节点。

• 当需要增加新的节点时，只需要将新节点插入到环中的适当位置，并将原节点的一部分数据（即一部分哈希空间）迁移到新节点上。
• 同样地，当需要移除节点时，该节点负责的数据可以迁移到其顺时针方向的下游节点上

容错性：一致性哈希能够容忍节点的故障，数据可以在节点故障后快速恢复。

实现步骤

1. 选择哈希函数：选择一个合适的哈希函数，将节点和数据项映射到哈希环上。
2. 构建哈希环：使用哈希函数生成节点和数据项的哈希值，并将它们放置在环上。
3. 数据存储：当存储数据时，计算数据项的哈希值，并在环上找到顺时针方向的第一个节点，将数据存储在该节点上。
4. 节点变动：当节点加入或离开时，重新计算受影响的数据项，进行必要的迁移。

以下是一个简单的一致性哈希的 Python 示例：

import hashlib
class ConsistentHashing:
    def __init__(self):
        self.ring = {} #键和节点的映射
        self.sorted_keys = [] # 哈希环，于存储已经排序好的哈希键值
        self.nodes_with_weights = {}  # 用于存储节点及其权重信息

    def _hash(self, key):
        """
        对给定的键进行哈希处理，返回一个整数形式的哈希值。
        :param key: 要进行哈希的键，可以是节点名称或者数据项名称等。
        :return: 整数形式的哈希值。
        """
        return int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16)

    def add_node(self, node, weight=1):
        """
        向哈希环中添加一个节点。
        :param node: 要添加的节点名称。
        :param weight: 节点的权重，默认为1，权重越高，在哈希环上对应的副本数量越多。
        """
        replicas = weight * 3  # 简单根据权重设定副本数量，这里可根据实际需求调整倍数关系
        for i in range(replicas):
            key = f"{node}:{i}"
            hashed_key = self._hash(key)
            self.ring[hashed_key] = node
            self.sorted_keys.append(hashed_key)
        self.nodes_with_weights[node] = weight
        self.sorted_keys.sort()

    def remove_node(self, node):
        """
        从哈希环中删除一个节点。
        :param node: 要删除的节点名称。
        """
        weight = self.nodes_with_weights.get(node, 1)
        replicas = weight * 3
        for i in range(replicas):
            key = f"{node}:{i}"
            hashed_key = self._hash(key)
            del self.ring[hashed_key]
            self.sorted_keys.remove(hashed_key)
        del self.nodes_with_weights[node]

    def get_node(self, key):
        """
        确定一个数据项应该映射到哪个节点上。
        :param key: 数据项的名称。
        :return: 数据项映射到的节点名称，如果哈希环为空则返回 None。
        """
        if not self.ring:
            return None
        hashed_key = self._hash(key)
        for node_key in self.sorted_keys:
            if hashed_key <= node_key:
                return self.ring[node_key]
        # 将数据项映射到了哈希环上第一个节点（按照哈希值从小到大排序后的第一个节点）        
        return self.ring[self.sorted_keys[0]]

# 示例使用
if __name__ == "__main__":
    ch = ConsistentHashing()

    # 添加节点及设置不同权重
    ch.add_node('Node1', weight=1)
    ch.add_node('Node2', weight=2)
    ch.add_node('Node3', weight=3)

    data_items = ['data1', 'data2', 'data3', 'data4', 'data5', 'data6', 'data7', 'data8', 'data9', 'data10']

    for item in data_items:
        node = ch.get_node(item)
        print(f"{item} 映射到的节点: {node}")

    # 模拟删除一个节点
    ch.remove_node('Node2')

    print("删除Node2后:")
    for item in data_items:
        node = ch.get_node(item)
        print(f"{item} 映射到的节点: {node}")

输出结果，可以看到删除 Node2 之后，Node3 和 Node1 之前映射的数据并有没有改变，只是原来Node2 的数据被映射到了 Node3

data1 映射到的节点: Node3
data2 映射到的节点: Node1
data3 映射到的节点: Node3
data4 映射到的节点: Node3
data5 映射到的节点: Node1
data6 映射到的节点: Node3
data7 映射到的节点: Node2
data8 映射到的节点: Node1
data9 映射到的节点: Node1
data10 映射到的节点: Node2
删除Node2后:
data1 映射到的节点: Node3
data2 映射到的节点: Node1
data3 映射到的节点: Node3
data4 映射到的节点: Node3
data5 映射到的节点: Node1
data6 映射到的节点: Node3
data7 映射到的节点: Node3
data8 映射到的节点: Node1
data9 映射到的节点: Node1
data10 映射到的节点: Node3

博文部分内容参考

© 文中涉及参考链接内容版权归原作者所有，如有侵权请告知 :)

---

---

© 2018-至今 liruilonger@gmail.com, All rights reserved. 保持署名-非商用-相同方式共享(CC BY-NC-SA 4.0)