Enter your search text in the box above

Select a result to preview

Hash算法与数据库实现

Hash函数

Hash 函数的作用

Hash 函数的要求 (理想情况)

一个好的 Hash 函数应该满足：

注意：实现一个完全无冲突的 Hash 函数是极具挑战性的。

取模算法（Modulo Operation）

1. 定义与公式

取模运算返回两数相除后的余数。

- a (Dividend): 运算起点，代数基础变量。
- n (Modulus): 拉丁语 Modulus (标准)，表示周期的步长。
- q (Quotient): 拉丁语 Quotiens (次数)，表示包含多少个 n。
- r (Remainder): 拉丁语 Remanere (残留)，表示除去完整周期后的余量。

2. 负数取模的差异

类型 代表语言 公式 示例 (−7mod3) 结果符号
截断取整 (Truncated) C, Java, Php, Go, JS 使用 (int)(a/n) 这种1;;向零取整的方式。 −1 与1;;被除数一致
地板取整 (Floored) Python, Ruby 使用⌊a/n⌋这种1;;向下取整的方式。 2（因为 −7=3×(−3)+2） 与1;;除数一致
为什么 Python 中 −7mod3=2？ 因为 Python 向下取整，−7/3≈−2.33→−3。公式计算：−7−(3×−3)=2。

3. 核心算法性质

在处理大数运算（如加密算法）时，以下性质至关重要：

4. 典型应用场景

Hash算法

概念

Hash 算法（散列函数）将关键字 k 映射到 Hash 表中的一个存储地址 h(k)。关键字 k 可以是1;;整数或1;;字符串。

Hash 冲突 (Collision)

不同的关键字 k1≠k2 经过 Hash 算法计算后得到相同的地址 1;;h(k1)=h(k2)。

Hash 表的装填因子 (α)

衡量 Hash 表被1;;填满程度的指标。α 越大，Hash 冲突的概率越1;;高，查找效率越1;;低，公式：1;;α=表中已存关键字个数 nHash 表的长度 m

整数关键字的 Hash 算法

直接取余法 (Division Method)

速度对比和原理

1. 模运算 (%)
2. 位与运算 (&)
结论
表达式 适用条件 速度 底层操作
hash_value%M 适用于任何 M>0 1;;慢 整数除法 (代价高)
hash_value&(M−1) 仅适用于 M=2N 1;;快 位与操作 (代价极低)

乘积取整法 (Multiplication Method)

代码实例

#include <stdio.h>
#include <math.h>

// 推荐常数 A：黄金分割率的倒数
#define A_CONSTANT 0.6180339887

/**
 * 乘积取整法 Hash 函数
 * @param key 关键字 (整数)
 * @param m Hash 表的大小
 * @return int Hash 表的地址 (0 到 m-1)
 */
int multiplicationHash(int key, int m)
{
    // 提取小数部分 (kA mod 1)：fmod(kA, 1.0) 计算 kA 除以 1.0 的余数，即小数部分。「或者使用 kA - floor(kA);」
    return (int)floor(m * fmod((double)key * A_CONSTANT, 1.0));
}

int main()
{
    // 假设 Hash 表大小为 m=1000
    int m = 1000;
    // 示例关键字
    int keys[] = {12345, 98765, 42};
    /* 解释：
     * sizeof(keys) 返回整个数组占用的字节数：数组包含 3 个元素，每个元素类型为 int（在常见平台上为 4 字节），因此整个数组大小为 3 * 4 = 12 字节。
     * sizeof(keys[0]) 返回数组第一个元素的字节数，即 sizeof(int)，通常为 4。
     * 注意：当数组传入函数时会退化为指针（array-to-pointer decay），在函数内部对参数使用 sizeof 会得到指针大小（例如 8），而不是数组总大小。
     */
    int num_keys = sizeof(keys) / sizeof(keys[0]);
    printf("--- 乘积取整法 Hash 示例 (m=%d) ---\n", m);
    for (int i = 0; i < num_keys; i++)
    {
        int hash_address = multiplicationHash(keys[i], m);
        printf("Key: %d -> Hash Address: %d\n", keys[i], hash_address);
    }
    return 0;
}

示例输出 (可能的运行结果):

--- 乘积取整法 Hash 示例 (m=1000) ---
Key: 12345 -> Hash Address: 629
Key: 98765 -> Hash Address: 126
Key: 42 -> Hash Address: 957

字符串关键字的 Hash 算法

当关键字是字符串的时候，需要先将所有字符的1;;ASCII码转成整数，然后再使用整数关键字的Hash算法

Times33 (T33 / DJB Hash)

核心原理

Times33 算法是一种基于加权1;;累加的迭代算法。它将字符串 S=s0s1s2...sn−1 视为一个以1;;33为基数的数字，其中每个字符的 ASCII 值 si 是该数字的一位。

使用场景

需求维度 适用程度 核心原因（为什么使用） 潜在风险（为什么不适用）
追求计算速度 极度适用 指令级优化：仅需位移（<< 5）和加法，不依赖昂贵的硬件乘法器，CPU 周期消耗极低。 过于简单：在现代高性能 CPU 上，虽然快，但相比 MurmurHash3 等算法，它缺乏复杂的位混淆步骤。
短字符串随机化 非常适用 ASCII 亲和力：初始值 1;;5381 配合乘数 33 能迅速扩散短字符（如变量名、URL）的差异，分布均匀。 规律性数据：如果输入是具有极强数学规律的序列（如纯数字递增），可能会出现局部聚簇。
处理超长文本 不推荐 无 高位溢出丢失：长文本前面的字符信息会因多次位移从寄存器左侧溢出，导致哈希值只取决于末尾文本，碰撞率激增。
抗碰撞攻击 (安全) 禁止使用 无 确定性危机：算法固定且线性，攻击者可轻易构造大量哈希值相同的字符串，触发“哈希洪水攻击”使服务瘫痪。
分布式负载均衡 基本适用 计算一致性：算法实现简单，各语言版本一致，能确保同一个 Key 始终映射到同一个节点。 节点倾斜：若 Key 的特征分布不均，简单的 Times33 可能导致某些节点压力过大，不如一致性哈希配合 MurmurHash。 
/**
 * DJBHash - 字符串 Hash 算法 (Times33)
 * @param str 要计算 Hash 值的字符串
 * @return unsigned int 计算得到的 Hash 值
 */
unsigned int DJBHash(char *str)
{
    // 初始种子值，常用奇素数 5381。
    unsigned int hash = 5381;
    // 循环遍历字符串，直到字符串结束符 '\0'。
    while (*str)
    {
        // 核心计算: hash = hash * 33 + 字符ASCII码
        // hash << 5 即 hash * 32。利用位运算实现高效乘 33。
        // *str++ 获取当前字符并使指针前进。
        hash += (hash << 5) + (*str++);
    }
    // 返回非负值：清除最高位，确保结果为正数。
    return (hash & 0x7FFFFFFF);
}

int main()
{
    char *test_str = "Hello, World!";
    unsigned int hash_value = DJBHash(test_str);
    printf("DJBHash of \"%s\" is: %u\n", test_str, hash_value); // DJBHash of "Hello, World!" is: 383943310
    return 0;
}

初始值 0 vs 5381

这是一个关于哈希算法初始化值（Seed）的经典问题，特别是针对 Times33（或称为 1;;DJB2 算法）。
在 Times33 算法中，初始值（种子，Seed）的选择对最终的哈希分布影响很大。对于 0 和 5381 这两个值，1;;5381 被认为是更好的选择。
以下是对比和原因的详细解释：

1. 初始值 hash=0

如果将初始哈希值设置为 0，则：

2. 初始值 hash=5381 (推荐)

5381 是一个经验上被证明效果非常好的初始值（或称为魔法数字）。它在 DJB2 算法中被广泛采用。

hash=hash×33+char

当 hash 已经是一个大数值（如 5381）时，乘法操作会更有效地将输入字符的位分布散布到哈希值的各个位上，从而获得更均匀的分布。

💡举例说明
总结对比
特性 初始值 hash=0 初始值 hash=5381
第一次迭代 哈希值等于第一个字符的 ASCII 值 哈希值是 5381×33+char1
碰撞风险 高，尤其对于第一个字符相同的键 低，分布更均匀
分布均匀性 较差 更好（推荐）
实际应用 不常用，仅用于简单示例 广泛用于 DJB2 和 Times33 算法

结论： 在实际应用中，如果使用 Times33 或 DJB2 哈希算法，初始值 5381 明显优于 0，因为它能带来更优异的哈希分布性能。

计算步骤示例

假设我们要计算字符串 "cat" 的 Hash 值。Hash 表大小 m 假设为 1000。
我们从左到右处理字符，并设置初始 Hash 值 Hinit=5381。

步骤 (i) 字符 (si) ASCII 值 (ASCII(si)) 计算 (Hi−1×33+ASCII(si)) Hash 值 (Hi)
0 (Init) - - 初始值 5381
1 ('c') 'c' 99 5381×33+99 177672
2 ('a') 'a' 97 177672×33+97 5863263
3 ('t') 't' 116 5863263×33+116 193487775
最终得到的整数 Hash Code 是 193,487,775。

映射到 Hash 表地址

为了得到 Hash 表地址 h(k)，我们使用直接取余法：h(k)=Hnmodm
继续以上示例，如果 Hash 表大小 m=1000：h("cat")=193487775mod1000=775
Hash 地址为 775。

($m & ($m - 1)) === 0 是一个经典的位运算技巧

m (十进制) m (二进制) m−1 (二进制) m&(m−1) (二进制)
1 (20) 0001 0000 0001 & 0000 = 0000
2 (21) 0010 0001 0010 & 0001 = 0000
4 (22) 0100 0011 0100 & 0011 = 0000
8 (23) 1000 0111 1000 & 0111 = 0000

PHP 伪代码实现

/**
 * Times33 Hash 算法 - 优化后的 PHP 实现 (解决浮点溢出)
 * @param string $key 要计算 Hash 值的字符串
 * @param int    $n   Hash 表的长度 (模数)
 * @return int Hash 表的地址 (0 到 $m-1)
 */
function fastTimes33HashOptimized(string $key, int $n): int
{
    // 1. 哈希值计算（循环累积）
    $hash = 5381;
    $i    = 0;
    while (isset($key[$i])) {
        $char_ascii = ord($key[$i++]);
        // 公式(hash = hash * 33 + char_ascii)用位运算: hash = (hash << 5) + hash + char_ascii
        $hash += ($hash << 5) + $char_ascii;
        // 💡0xFFFFFFFF 确保$hash始终保持在 [0, 2^32 - 1] 范围内，防止溢出到 float。
        $hash = $hash & 0xFFFFFFFF;
    }

    // 检查 $m 是否为 2 的幂次 (标准位操作检查)， 否则使用标准取模
    return $n > 0 && (($n & ($n - 1)) === 0) ? $hash & ($n - 1) : $hash % $n;
}

$k  = "hello world";
$n1 = 1024;
$n2 = 1009; // 素数
echo "使用位与 (M=$n1): " . fastTimes33HashOptimized($k, $n1) . "\n"; // 使用位与 (M=1024): 193
echo "使用取模 (M=$n2): " . fastTimes33HashOptimized($k, $n2) . "\n"; // 使用取模 (M=1009): 100

Hash表

Hash表结构

基本概念与结构

时间复杂度：Hash 表的时间复杂度为 O(1)。
散列函数作用：将关键字 Key 映射到数组的某个位置。
Hash 表结构：Hash 表结构可以用图13-1展示。它由两个主要部分构成：

Hash 表实现步骤

要实现一个 Hash 表，需要遵循以下三个主要步骤：

  1. 创建数组： 创建一个固定大小的数组用于存放数据。
  2. 设计函数： 设计 Hash 函数（散列函数）。
  3. 数据存取： 通过 Hash 函数把关键字映射到数组的某个位置，并在此位置上进行数据存取。

使用PHP实现Hash表

首先创建一个 HashTable 类，包含 $buckets（存储数据的数组）和 $size（数组大小）两个属性。在构造函数中，为 $buckets 分配内存。

注意: SplFixedArray 需安装并开启 SPL 扩展（PHP 5.3+ 默认开启）。

代码实例

class HashTable
{
    private SplFixedArray $buckets;
    private int           $size = 10;

    public function __construct()
    {
        // 为 $buckets 数组分配一个大小为 10 的内存
        $this->buckets = new SplFixedArray($this->size);
    }

    private function hashFunc($key): int
    {
        $strlen  = strlen($key);
        $hashVal = 0;
        // 累加所有字符的 ASCII 码
        for ($i = 0; $i < $strlen; $i++) {
            $hashVal += ord($key[$i]);
        }
        // 对 Hash 表大小取余，得到数组索引
        return $hashVal % $this->size;
    }

    public function insert($key, $val): void
    {
        // 1. 计算 Hash 索引
        $index = $this->hashFunc($key);
        // 2. 将值保存到对应的桶中
        $this->buckets[$index] = $val;
    }

    public function find($key)
    {
        // 1. 计算 Hash 索引
        $index = $this->hashFunc($key);
        // 2. 返回对应桶中的数据
        return $this->buckets[$index];
    }
}

测试代码

$ht = new HashTable();
// 插入 key1 => value1
$ht->insert('key1', 'value1');
// 插入 key2 => value2
$ht->insert('key2', 'value2');
// 查找 key1 对应的数据
echo $ht->find('key1');
// 查找 key2 对应的数据
echo $ht->find('key2');

输出结果

value1
value2

Hash 冲突

冲突原因： key1、key12计算出的ASCII码分别为378、428，然后两者%10的索引位置都等于8，故冲突

$ht = new HashTable();
// 插入 key1 => value1
$ht->insert('key1', 'value1');
// 插入 key2 => value2
$ht->insert('key12', 'value2');
// 查找 key1 对应的数据
echo $ht->find('key1');
// 查找 key2 对应的数据
echo $ht->find('key12');

输出结果

value2
value2

好的，我将根据您提供的关于“拉链法解决冲突”的描述和图片中的代码，整理出一份完整的技术笔记。

拉链法解决冲突 (Separate Chaining)

拉链法原理与结构

代码实例

通过插入 key1 和 key12（假设它们发生冲突，映射到同一个地址）并查找，可以验证拉链法是否成功解决了冲突问题.

代码清单 (测试代码)

/**
 * 由于节点需要保存关键字（Key）和数据（Value），同时还要记录具有相同 Hash 值的下一个节点，因此需要创建一个 `HashNode` 类。
 */
class HashNode
{
    public $key; // 节点的关键字。
    public $value; // 节点的值。
    public $nextNode; // 指向具有相同 Hash 值链表中下一个节点的指针。

    public function __construct($key, $value, $nextNode = null)
    {
        $this->key      = $key;
        $this->value    = $value;
        $this->nextNode = $nextNode;
    }
}

class HashTable
{
    private SplFixedArray $buckets;
    private int           $size = 10;

    public function __construct()
    {
        // 为 $buckets 数组分配一个大小为 10 的内存
        $this->buckets = new SplFixedArray($this->size);
    }

    // 为了简化，这里使用一种基本的 Hash 算法：将字符串的所有字符 ASCII 码相加，再对 `$this->size` 取余（直接取余法）。
    private function hashFunc($key): int
    {
        $strlen  = strlen($key);
        $hashVal = 0;
        // 累加所有字符的 ASCII 码
        for ($i = 0; $i < $strlen; $i++) {
            $hashVal += ord($key[$i]);
        }
        // 对 Hash 表大小取余，得到数组索引
        return $hashVal % $this->size;
    }

    /**
     * 插入数据时，新节点总是插入到链表的"头部"，以保持 O(1) 的插入时间。
     * 插入算法流程
     *   1.使用 Hash 函数计算关键字的 Hash 值，通过 Hash 值定位到 Hash 表的指定位置。
     *   2.如果此位置已经被其他节点占用，将新节点的 `$nextNode` 指向此节点（即旧的头节点）。
     *   3.否则，将新节点的 `$nextNode` 设置为 `NULL`。
     *   4.将新节点保存到 Hash 表的当前位置，使其成为新的链表头。
     *   经过这 4 个步骤，相同 Hash 值的节点会被连接在同一个链表.
     */
    public function insert($key, $value)
    {
        $index = $this->hashfunc($key);
        /* 新创建一个节点 */
        if (isset($this->buckets[$index])) {
            // 如果桶中已有节点，将新节点插到链表头部
            $newNode = new HashNode($key, $value, $this->buckets[$index]);
        } else {
            // 如果桶中没有节点，新节点是链表尾部（下一个节点为NULL）
            $newNode = new HashNode($key, $value, null);
        }
        $this->buckets[$index] = $newNode; /* 保存新节点，使其成为新的链表头 */
    }

    /**
     * 查找算法流程
     *   1.使用 Hash 函数计算关键字的 Hash 值，通过 Hash 值定位到 Hash 表的指定位置。
     *   2.获取该位置的链表头节点 `$current`.
     *   3.遍历当前链表，比较链表中每个节点的关键字 `$current->key` 与查找关键字 `$key` 是否相等。
     *   4.如果相等，返回该节点的值 (`$current->value`)，查找成功。
     *   5.如果整个链表遍历完毕都没有找到，返回 `NULL`，查找失败.
     */
    public function find($key)
    {
        $index   = $this->hashfunc($key);
        $current = $this->buckets[$index];
        while (isset($current)) { /* 遍历当前链表 */
            if ($current->key == $key) { /* 比较当前节点的关键字 */
                return $current->value; /* 查找成功 */
            }
            $current = $current->nextNode; /* 比较下一个节点 */
        }
        return null; /* 查找失败 */
    }
}

$ht = new HashTable();
// 插入 key1 => value1
$ht->insert('key1', 'value1');
// 插入 key2 => value2
$ht->insert('key12', 'value2');
// 查找 key1 对应的数据
echo $ht->find('key1');
// 查找 key2 对应的数据
echo $ht->find('key12');

输出结果

运行测试代码后，输出结果为:

value1
value12

基于文件的Hash数据库

数据结构

索引文件 (.idx)

由三部分组成：1;;空闲链表指针、1;;Hash 表（桶） 和 1;;索引记录。所有指针（文件偏移量）均存储为1;;4字节的==1;;int==类型

索引记录结构

数据文件 (.dat)

存储实际的用户数据记录

索引组织方式

索引文件采用固定大小的1;;Hash 表来组织，并使用1;;拉链法（通过指针字段连接索引记录）来解决 Hash 冲突

数据查找过程

代码实例

尾插法「O(n)」

class HashTable
{
    public const int     DB_BUCKET_SIZE      = 2 ** 10; // Hash表的桶大小 (1024*4字节)(每个指针4字节)「💡2^N，利于位运算」
    public const int     DB_POINTER_SIZE     = 4;       // 指针大小(4 字节)
    public const int     DB_KEY_SIZE         = 128;     // 键大小(128 字节)
    public const int     DB_DATA_OFFSET_SIZE = 4;       // 数据偏移量(4 字节)
    public const int     DB_DATA_LENGTH_SIZE = 4;       // 数据长度(4 字节)
    public const int     INIT                = 5381;    // 初始化 Hash 值

    public const int DB_INDEX_SIZE = self::DB_POINTER_SIZE + self::DB_KEY_SIZE +
                                     self::DB_DATA_OFFSET_SIZE + self::DB_DATA_LENGTH_SIZE;

    public const bool DB_SUCCESS = true;

    private mixed $idxFp;
    private mixed $datFp;
    private bool  $closed = false;

    /**
     * 获取Hash值方法（Times33 算法 + 映射）
     * @param string $string Key
     * @return int 索引文件中的指针偏移量
     */
    private function getHash(string $string): int
    {
        $hash   = self::INIT;
        $strLen = strlen($string);
        for ($i = 0; $i < $strLen; $i++) {
            // Times33 算法核心
            // hash = hash * 33 + char
            $hash += ($hash << 5) + ord($string[$i]);
            // Hash值：返回32位无符号整数 (防止PHP溢出到float)
            $hash &= 0xFFFFFFFF;
        }

        // 映射到索引文件中的指针偏移量： (hash % DB_BUCKET_SIZE) * 4 (每个指针4字节)
        return ($hash % self::DB_BUCKET_SIZE) << 2;
    }

    public function open($fileName): bool
    {
        $idxPath = $fileName . '.idx';     // 索引文件路径
        $datPath = $fileName . '.dat';     // 数据文件路径
        $init    = !file_exists($idxPath); // 判断索引文件是否存在
        $mode    = $init ? "w+b" : "r+b";  // w+b: 创建文件并打开文件, r+b: 打开文件并读取文件
        // 打开索引文件
        $this->idxFp = fopen($idxPath, $mode);
        if (!$this->idxFp) {
            throw new Exception('idxFp Open file failure');
        }
        // 初始化索引文件
        if ($init) {
			/* fseek 移动到逻辑末尾，fwrite 写入最后一个字节0，强制 OS 填充中间的“逻辑零”，这种机制为级联反应：
				操作系统为了维护文件的一致性，必须确保从文件开头到该点之间是有内容的。
				由于你并没有显式写入中间的数据，操作系统会通过元数据操作（Metadata Update）瞬间将中间部分标记为全 0（即 \0）。
            */
            fseek($this->idxFp, self::DB_BUCKET_SIZE * 4 - 1); // 文件位置是从0开始计数的，所以-1
            fwrite($this->idxFp, "\0");
        }
        // 打开数据文件
        $this->datFp = fopen($datPath, $mode);
        if (!$this->datFp) {
            throw new Exception('datFp Open file failure');
        }

        return self::DB_SUCCESS;
    }

    // 插入记录方法
    public function insert($key, $data): bool
    {
        $keyLen = strlen($key);
        if ($keyLen > self::DB_KEY_SIZE) {
            throw new Exception('Key length too long');
        }

        // 1. 准备工作
        // Hash 链表指针在索引文件中的偏移量
        $hashOffset = $this->getHash($key);

        // 获取新记录的写入偏移量
        $idxOffset = intval(fstat($this->idxFp)['size']);
        $datOffset = intval(fstat($this->datFp)['size']);

        // 2. 构造新索引记录块 ($block)
        // 指针(0) + Key(填充) + 数据偏移量 + 数据长度
        // 优化：使用 str_pad 替换 for 循环填充
        $block = pack('L', 0x00000000);
        $block .= str_pad($key, self::DB_KEY_SIZE, "\0");
        $block .= pack('L', $datOffset);
        $block .= pack('L', strlen($data));

        // 3. 获取链表头节点偏移量 ($headPos)「unpack的结果默认数组索引从1开始」
        // 移动文件指针到Hash链表的偏移量
        fseek($this->idxFp, $hashOffset);
        $headPos = unpack('L', fread($this->idxFp, 4))[1];

        // 4. 遍历链表查找冲突/确定尾部
        $curr = $headPos;
        $prev = 0; // 记录前一个节点的偏移量

        while ($curr) {
            // 移动文件指针索引记录的偏移量
            fseek($this->idxFp, $curr);
            // 读取索引记录
            $tmpBlock = fread($this->idxFp, self::DB_INDEX_SIZE);
            // 获取索引记录的Key
            $tmpKey = substr($tmpBlock, 4, self::DB_KEY_SIZE);
            // 比较键是否相等 (Key 冲突检查)
            if (!strncmp($key, $tmpKey, $keyLen)) {
                throw new Exception('Key already exists');
            }
            // 记录当前节点为下一个循环的前一个节点
            $prev = $curr;
            // 下一个节点偏移量
            $curr = unpack('L', substr($tmpBlock, 0, 4))[1];
        }

        // 5. 写入新记录
        // 将新索引记录写入索引文件的末尾
        fseek($this->idxFp, 0, SEEK_END);
        fwrite($this->idxFp, $block, self::DB_INDEX_SIZE);

        // 将数据写入数据文件的末尾
        fseek($this->datFp, 0, SEEK_END);
        fwrite($this->datFp, $data, strlen($data));

        // 6. 更新指针
        if ($prev == 0) {
            // 链表为空，更新 Hash 链表头指针
            fseek($this->idxFp, $hashOffset);
        } else {
            // 链表不为空，更新链表最后一个节点 ($prev) 的 next 指针
            fseek($this->idxFp, $prev);
        }
        // 修改指针指向新记录
        fwrite($this->idxFp, pack('L', $idxOffset), 4);

        return self::DB_SUCCESS;
    }

    // 查找记录方法
    public function fetch($key): false|string|null
    {
        $hashOffset = $this->getHash($key);
        fseek($this->idxFp, $hashOffset);
        $pos    = unpack('L', fread($this->idxFp, 4))[1];
        $keyLen = strlen($key);
        // 遍历Hash链表 (直到偏移量为0)
        while ($pos) {
            // 移动到当前索引记录位置
            fseek($this->idxFp, $pos);
            // 读取一条索引记录大小的数据块
            $block = fread($this->idxFp, self::DB_INDEX_SIZE);
            // 获取索引记录的Key
            $tmpKey = substr($block, 4, self::DB_KEY_SIZE);
            // 比较键是否相等「相等返回 0」
            if (!strncmp($key, $tmpKey, $keyLen)) {
                // 获取数据偏移量和长度
                $keyOffset  = self::DB_POINTER_SIZE + self::DB_KEY_SIZE;
                $dataOffset = unpack('L', substr($block, $keyOffset, 4))[1];
                $dataLength = unpack('L', substr($block, $keyOffset + self::DB_DATA_OFFSET_SIZE, 4))[1];
                // 从数据文件读取数据
                fseek($this->datFp, $dataOffset);

                return fread($this->datFp, $dataLength);
            }
            // 下一条索引记录的偏移量
            $pos = unpack('L', substr($block, 0, 4))[1];
        }

        return null;
    }

    // 删除记录方法
    public function delete($key): bool
    {
        // Hash 链表指针在索引文件中的偏移量
        $hashOffset = $this->getHash($key);
        // 移动文件指针到Hash链表的偏移量
        fseek($this->idxFp, $hashOffset);
        // 读取链表头节点偏移量
        $head = unpack('L', fread($this->idxFp, 4))[1];
        // 当前节点偏移量
        $curr = $head;
        // 上一个节点偏移量 (0表示Hash链表指针)
        $prev = 0;
        // 键长度
        $keyLen = strlen($key);
        // 遍历链表
        while ($curr) {
            // 移动文件指针索引记录的偏移量
            fseek($this->idxFp, $curr);
            // 读取索引记录
            $block = fread($this->idxFp, self::DB_INDEX_SIZE);
            // 下一条索引记录的偏移量
            $next = unpack('L', substr($block, 0, 4))[1];
            // 获取索引记录的Key
            $tmpKey = substr($block, 4, self::DB_KEY_SIZE);
            // 比较键是否相等「相等返回 0」
            if (!strncmp($key, $tmpKey, $keyLen)) {
                break; // 找到记录，退出循环
            }
            $prev = $curr;
            $curr = $next;
        }
        // 如果循环结束 curr 为 0，说明未找到
        if (!$curr) {
            throw new Exception('Key not found');
        }
        // 更新链表指针，移除当前节点
        if ($prev == 0) { // 删除的是头节点
            fseek($this->idxFp, $hashOffset);
        } else { // 删除的是非头节点
            fseek($this->idxFp, $prev);
        }
        // 将 next 指针写入
        fwrite($this->idxFp, pack('L', $next), 4);

        return self::DB_SUCCESS;
    }

    // 关闭数据库方法
    public function close()
    {
        if (!$this->closed) {
            fclose($this->idxFp);
            fclose($this->datFp);
            $this->closed = true;
        }
    }

    // 析构方法
    public function __destruct()
    {
        $this->close();
    }
}

// 示例调用保持不变
$db = new HashTable();
$db->open(__FILE__);
$list = ['test0' => 'aaa', 'test1' => 'bbb', 'test2' => 'ccc', 'test3' => 'ddd', 'test4' => 'eee'];
foreach ($list as $key => $value) {
    $db->insert($key, $value);
}
$result = [];
foreach ($list as $key => $value) {
    $result[] = $db->fetch($key);
}
var_dump($result);
/*
array(5) {
  [0]=>
  string(3) "aaa"
  [1]=>
  string(3) "bbb"
  [2]=>
  string(3) "ccc"
  [3]=>
  string(3) "ddd"
  [4]=>
  string(3) "eee"
}
*/

头插法「O(1)」

class HashTable
{
    public const int     DB_BUCKET_SIZE      = 2 ** 10; // Hash表的桶大小 (1024*4字节)(每个指针4字节)「💡2^N，利于位运算」
    public const int     DB_POINTER_SIZE     = 4;       // 指针大小(4 字节)
    public const int     DB_KEY_SIZE         = 128;     // 键大小(128 字节)
    public const int     DB_DATA_OFFSET_SIZE = 4;       // 数据偏移量(4 字节)
    public const int     DB_DATA_LENGTH_SIZE = 4;       // 数据长度(4 字节)
    public const int     INIT                = 5381;    // 初始化 Hash 值

    public const int DB_INDEX_SIZE = self::DB_POINTER_SIZE + self::DB_KEY_SIZE +
                                     self::DB_DATA_OFFSET_SIZE + self::DB_DATA_LENGTH_SIZE;

    public const bool DB_SUCCESS = true;

    private mixed $idxFp; // 索引文件句柄
    private mixed $datFp; // 数据文件句柄
    private bool  $closed = false; // 是否关闭

    /**
     * 获取Hash值方法（Times33 算法 + 映射）
     * @param string $string Key
     * @return int 索引文件中的指针偏移量
     */
    private function getHash(string $string): int
    {
        $hash   = self::INIT;
        $strLen = strlen($string);
        for ($i = 0; $i < $strLen; $i++) {
            // Times33 算法核心
            // hash = hash * 33 + char
            $hash += ($hash << 5) + ord($string[$i]);
            // Hash值：返回32位无符号整数 (防止PHP溢出到float)
            $hash &= 0xFFFFFFFF;
        }

        // 映射到索引文件中的指针偏移量： (hash % DB_BUCKET_SIZE) * 4 (每个指针4字节)
        return ($hash % self::DB_BUCKET_SIZE) << 2;
    }

    public function open($fileName): bool
    {
        $idxPath = $fileName . '.idx';     // 索引文件路径
        $datPath = $fileName . '.dat';     // 数据文件路径
        $init    = !file_exists($idxPath); // 判断索引文件是否存在
        $mode    = $init ? "w+b" : "r+b";  // w+b: 创建文件并打开文件, r+b: 打开文件并读取文件
        // 打开索引文件
        $this->idxFp = fopen($idxPath, $mode);
        if (!$this->idxFp) {
            throw new Exception('idxFp Open file failure');
        }
        // 初始化索引文件
        if ($init) {
            /* 💡fseek 移动到逻辑末尾，fwrite 写入最后一个字节0，强制 OS 填充中间的“逻辑零”，这种机制为级联反应：
                操作系统为了维护文件的一致性，必须确保从文件开头到该点之间是有内容的。
                由于你并没有显式写入中间的数据，操作系统会通过元数据操作（Metadata Update）瞬间将中间部分标记为全 0（即 \0）。
            */
            fseek($this->idxFp, self::DB_BUCKET_SIZE * 4 - 1); // 文件位置是从0开始计数的，所以-1
            fwrite($this->idxFp, "\0");
        }
        // 打开数据文件
        $this->datFp = fopen($datPath, $mode);
        if (!$this->datFp) {
            throw new Exception('datFp Open file failure');
        }

        return self::DB_SUCCESS;
    }

    // 插入记录方法
    public function insert($key, $data): bool
    {
        $keyLen = strlen($key);
        if ($keyLen > self::DB_KEY_SIZE) {
            throw new Exception('Key length too long');
        }

        // 1. 准备工作
        // Hash 链表指针在索引文件中的偏移量
        $hashOffset = $this->getHash($key);

        // 获取新记录的写入偏移量
        $idxOffset = intval(fstat($this->idxFp)['size']);
        $datOffset = intval(fstat($this->datFp)['size']);

        // 2. 获取链表头节点偏移量 ($headPos)「unpack的结果默认数组索引从1开始」
        // 移动文件指针到Hash链表的偏移量
        fseek($this->idxFp, $hashOffset);
        $headPos = unpack('L', fread($this->idxFp, 4))[1];

        // 3. 头插法
        if ($headPos) {
            // 移动文件指针索引记录的偏移量
            fseek($this->idxFp, $headPos);
            // 读取索引记录
            $tmpBlock = fread($this->idxFp, self::DB_INDEX_SIZE);
            // 获取索引记录的Key
            $tmpKey = substr($tmpBlock, 4, self::DB_KEY_SIZE);
            // 比较键是否相等 (Key 冲突检查)
            if (!strncmp($key, $tmpKey, $keyLen)) {
                throw new Exception('Key already exists');
            }
            // 下一个节点偏移量
            $nextPtr = $headPos;
        } else {
            // 链表为空
            $nextPtr = 0x00000000;
        }

        // 4. 构造新索引记录块 ($block)
        // 指针(0) + Key(填充) + 数据偏移量 + 数据长度
        // 优化：使用 str_pad 替换 for 循环填充
        $block = pack('L', $nextPtr);
        $block .= str_pad($key, self::DB_KEY_SIZE, "\0");
        $block .= pack('L', $datOffset);
        $block .= pack('L', strlen($data));

        // 5. 写入新记录
        // 将新索引记录写入索引文件的末尾
        fseek($this->idxFp, 0, SEEK_END);
        fwrite($this->idxFp, $block, self::DB_INDEX_SIZE);

        // 将数据写入数据文件的末尾
        fseek($this->datFp, 0, SEEK_END);
        fwrite($this->datFp, $data, strlen($data));

        // 6. 更新指针
        // 更新 Hash 链表头指针
        fseek($this->idxFp, $hashOffset);
        // 修改指针指向新记录
        fwrite($this->idxFp, pack('L', $idxOffset), 4);

        return self::DB_SUCCESS;
    }

    // 查找记录方法
    public function fetch($key): false|string|null
    {
        $hashOffset = $this->getHash($key);
        fseek($this->idxFp, $hashOffset);
        $pos    = unpack('L', fread($this->idxFp, 4))[1];
        $keyLen = strlen($key);
        // 遍历Hash链表 (直到偏移量为0)
        while ($pos) {
            // 移动到当前索引记录位置
            fseek($this->idxFp, $pos);
            // 读取一条索引记录大小的数据块
            $block = fread($this->idxFp, self::DB_INDEX_SIZE);
            // 获取索引记录的Key
            $tmpKey = substr($block, 4, self::DB_KEY_SIZE);
            // 比较键是否相等「相等返回 0」
            if (strncmp($key, $tmpKey, $keyLen) == 0) {
                // 获取数据偏移量和长度
                $keyOffset  = self::DB_POINTER_SIZE + self::DB_KEY_SIZE;
                $dataOffset = unpack('L', substr($block, $keyOffset, 4))[1];
                $dataLength = unpack('L', substr($block, $keyOffset + self::DB_DATA_OFFSET_SIZE, 4))[1];
                // 从数据文件读取数据
                fseek($this->datFp, $dataOffset);

                return fread($this->datFp, $dataLength);
            }
            // 下一条索引记录的偏移量
            $pos = unpack('L', substr($block, 0, 4))[1];
        }

        return null;
    }

    // 删除记录方法
    public function delete($key): bool
    {
        // Hash 链表指针在索引文件中的偏移量
        $hashOffset = $this->getHash($key);
        // 移动文件指针到Hash链表的偏移量
        fseek($this->idxFp, $hashOffset);
        // 读取链表头节点偏移量
        $head = unpack('L', fread($this->idxFp, 4))[1];
        // 当前节点偏移量
        $curr = $head;
        // 上一个节点偏移量 (0表示Hash链表指针)
        $prev = 0;
        // 键长度
        $keyLen = strlen($key);
        // 遍历链表
        while ($curr) {
            // 移动文件指针索引记录的偏移量
            fseek($this->idxFp, $curr);
            // 读取索引记录
            $block = fread($this->idxFp, self::DB_INDEX_SIZE);
            // 下一条索引记录的偏移量
            $next = unpack('L', substr($block, 0, 4))[1];
            // 获取索引记录的Key
            $tmpKey = substr($block, 4, self::DB_KEY_SIZE);
            // 比较键是否相等「相等返回 0」
            if (!strncmp($key, $tmpKey, $keyLen)) {
                break; // 找到记录，退出循环
            }
            $prev = $curr;
            $curr = $next;
        }
        // 如果循环结束 curr 为 0，说明未找到
        if (!$curr) {
            throw new Exception('Key not found');
        }
        // 更新链表指针，移除当前节点
        if ($prev == 0) { // 删除的是头节点
            fseek($this->idxFp, $hashOffset);
        } else { // 删除的是非头节点
            fseek($this->idxFp, $prev);
        }
        // 将 next 指针写入
        fwrite($this->idxFp, pack('L', $next), 4);

        return self::DB_SUCCESS;
    }

    // 关闭数据库方法
    public function close()
    {
        if (!$this->closed) {
            fclose($this->idxFp);
            fclose($this->datFp);
            $this->closed = true;
        }
    }

    // 析构方法
    public function __destruct()
    {
        $this->close();
    }
}

// 示例调用保持不变
$db = new HashTable();
$db->open(__FILE__);
$list = ['test0' => 'aaa', 'test1' => 'bbb', 'test2' => 'ccc', 'test3' => 'ddd', 'test4' => 'eee'];
foreach ($list as $key => $value) {
    $db->insert($key, $value);
}
$result = [];
foreach ($list as $key => $value) {
    $result[] = $db->fetch($key);
}
var_dump($result);
/*
array(5) {
  [0]=>
  string(3) "aaa"
  [1]=>
  string(3) "bbb"
  [2]=>
  string(3) "ccc"
  [3]=>
  string(3) "ddd"
  [4]=>
  string(3) "eee"
}
*/

Hash方案对比(PHP/Java/Go)

特性 PHP 8.5.3 (Zend HashTable) Java (HashMap) Go (map)
底层结构 1;;Index数组 + 1;;Data 连续数组
通过 *arData 正负偏移访问		 1;;数组 + 1;;单向链表 -> 红黑树 1;;数组 + 1;;桶（Bucket）
每个桶存 8 个键值对
顺序保证 1;;物理顺序维护
按 Data 数组下标顺序遍历		 1;;无序 1;;无序
迭代起始点随机
冲突解决方法 1;;逻辑拉链法 (Chaining)
利用 1;;zval.u2.next 存储下标		 拉链法(Chaining)
链表长度 ≥ 1;;8 且数组 ≥ 1;;64 转红黑树
 1;;拉链法 (Chaining) + 1;;溢出桶 (Overflow Bucket)
初始容量 1;;8 1;;16 1;;8（1个桶）
触发扩容阈值 1;;1.0 (即 n=m) 1;;0.75 1;;6.5 (基于桶填充程度计算)
扩容阈值触发条件 当 n/m > 1;;1 当已存元素数 n/m > 1;;0.75 当 n/m > 1;;6.5 或溢出桶过多
扩容倍数 1;;2 倍 (且必须是 2 的幂次) 1;;2 倍 1;;2 倍（翻倍扩容）或 1 倍（等量重排）
扩容方式 1;;物理全量拷贝（memcpy） + 1;;重建映射（*arHash） 1;;全量 Rehash 1;;双表渐进式 Rehash
扩容过程 1;;全量搬迁：利用 memcpy 快速搬迁 Bucket 数组。

1;;重建映射：扩容瞬间清空索引表，然后1;;重建映射。		 1;;全量搬迁：在单次 put 触发阈值时，立即创建新数组并重新计算所有元素的 Hash 位置并分配，可能造成明显的响应抖动。 1;;逐步搬迁：扩容期间新旧表共存。每次进行写入或删除操作时，顺带触发 1-2 个桶（Bucket）的迁移，将压力平摊到多次操作中。
性能表现 连续内存地址带来极高的物理搬迁速度和重建速度。 海量数据下扩容会有明显的毫秒级==1;;“毛刺”==感。 响应时间极度平稳，消灭了扩容引起的延迟波峰，但内部逻辑最复杂。

PHP8：兼顾顺序与速度

flowchart LR
    %% 定义左侧：索引映射区
    subgraph Index_Table [Hash数组:索引区/负向偏移]
        direction LR
        idx_n1["Index [-3] 
 (值: 1)"]
        idx_n2["Index [-2] 
 (值: 0)"]
    end

    %% 中间：核心指针
    Anchor((*arData 指针))

    %% 定义右侧：数据存储区
    subgraph Data_Array [Data数组:数据区/正向偏移]
        direction LR
        bucket_0["Bucket [0] 
 'age' => 18 
 Key: 'age' 
 zval: 123 (Long)"]
        bucket_1["Bucket [1] 
 'name' => 'Gemini' 
 Key: 'name' 
 zval: 指针 (Ptr)"]
    end

	subgraph Heap [堆内存]
        zs["zend_string 
 'Gemini' 
 refcount: 1"]
    end

    %% 物理连接关系
    Index_Table --- Anchor --- Data_Array

    %% 逻辑映射关系（带箭头的表示查找过程）
    idx_n2 -.->|指向下标 0| bucket_0
    idx_n1 -.->|指向下标 1| bucket_1

%% 指针跳转  
    bucket_1 -- value.ptr --> zs  

    %% 样式设置
    style Anchor fill:#f96,stroke:#333,stroke-width:2px
    style Index_Table fill:#e1f5fe,stroke:#01579b
    style Data_Array fill:#fff3e0,stroke:#ef6c00

底层数据结构 (C 语言)

PHP 数组的内部由两个核心物理块构成：

  1. HashTable 结构体（中控）
    • 大小固定（1;;56 字节），1;;独立分配。
    • 存储元数据：元素个数（1;;nNumUsed）、容量（1;;nTableSize）、哈希掩码（1;;nTableMask）、指向数据体的指针（1;;arData）等。
    • 管理数组的“状态”：不存数据，仅通过*arData指针握住内存 Body 的“中心原点” ，因此可通过负数下标访问索引表（arData[-1]）
    • 其地址在扩容时保持不变。
  2. Body「Index Table、Bucket 数组」
    • 默认大小（1;;32 + 256 字节），1;;独立分配。
    • emalloc 分配的同一块连续的内存，包含两个逻辑分区：
      • Index Table（索引表）：*arData1;;低地址段(初始32 字节)，1;;uint32_t类型数组，通过哈希值映射到Bucket数组的1;;下标。
      • Bucket 数组（数据区）：*arData 1;;高地址段(初始256 字节)，按插入顺序存储每个元素的1;;Key、1;;Value、1;;哈希值、1;;冲突链指针
        • 顺序维护（物理顺序）： PHP 8 不再使用双向链表指针，
          • 默认按照1;;插入时间顺序将元素填入 Data 数组的 0, 1, 2...n 位置。
          • foreach 遍历时，直接从 *arData[0] 顺序读到 *arData[n]，因此遍历顺序与插入顺序天然一致。
        • 逻辑链表（解决冲突）：
          • 当两个不同的 Key 映射到同一个 Index 位置时，PHP 会利用 zval 内部的 u2.next 字段记录前一个冲突元素的下标，形成一个隐藏的1;;逻辑单向链表。

HashTable「控制器」

typedef struct _zend_array HashTable; // 为结构体 struct _zend_array 取一个别名，叫做 HashTable。

// 引用计数头：总大小 8 字节，用于实现 COW（写时复制）和垃圾回收
typedef struct _zend_refcounted_h {
    uint32_t         refcount;          // 4 字节 | 引用计数数值
    union {
        uint32_t     type_info;         // 4 字节 | 类型信息标志
    } u;
} zend_refcounted_h;

// HashTable 结构：总大小 56 字节 (64-bit 系统)
struct _zend_array {
    zend_refcounted_h gc;               // 8 字节 | 偏移 0  | 垃圾回收与引用计数头
    union {
        struct {
            // 合计 4 字节，用于适配大小端，确保字节布局一致
            ZEND_ENDIAN_LOHI_4(
                uint8_t    flags,           // 1 字节 | 数组标志：如 HASH_FLAG_INITIALIZED
                uint8_t    _unused,         // 1 字节
                uint8_t    nIteratorsCount, // 1 字节 | 当前数组正在被多少个迭代器使用
                uint8_t    _unused2)        // 1 字节
        } v;
        uint32_t flags;                 // 4 字节 | 偏移 8  | 标志位的统一读写视图
    } u;
    uint32_t          nTableMask;       // 4 字节 | 偏移 12 | 💡掩码：用于将 Hash 值映射到索引区。通常为 -nTableSize
    union {
        uint32_t     *arHash;           // 8 字节 | 偏移 16 | 💡指向索引映射区（Index Table）。注意：物理地址在 *arData 之前
        Bucket       *arData;           // 8 字节 | 偏移 16 | 💡指向数据存储区（Bucket 数组）。这是哈希表的基准指针
        zval         *arPacked;         // 8 字节 | 偏移 16 | 💡指向连续数字索引数组的视图（Packed Array）
    };
    uint32_t          nNumUsed;         // 4 字节 | 偏移 24 | 💡Data 数组中已使用的槽位数（含已经删除「IS_UNDEF」的空洞）
    uint32_t          nNumOfElements;   // 4 字节 | 偏移 28 | 实际存储的有效元素个数
    uint32_t          nTableSize;       // 4 字节 | 偏移 32 | 💡数组的总容量（始终为 2 的幂）
    uint32_t          nInternalPointer; // 4 字节 | 偏移 36 | 内部遍历指针（用于 current(), next() 等）
    zend_long         nNextFreeElement; // 8 字节 | 偏移 40 | 下一个可用的数字下标（用于 $arr[] = ...）
    dtor_func_t       pDestructor;      // 8 字节 | 偏移 48 | 元素销毁时的析构函数指针
};
为什么 *arHash 是 8 字节？
成员 类型 变量自身大小 它的作用 指向的内容大小
*arHash uint32_t * 1;;8 字节 (64位系统) 存储索引映射区的末地址 1;;4 字节 (uint32_t)
*arData Bucket * 1;;8 字节 (64位系统) 存储数据存储区的首地址 1;;32 字节 (Bucket)
指针的容器本质：
union 的设计
  1. 语法本质：内存复用，内存大小取决于最1;;大的元素
    • 物理同体：union 强制让 *arHash、*arData 和 arPacked 1;;共享同一个1;;8字节的1;;起始内存地址（当你给其中一个赋值（地址原点）时，另外两个自动获得了1;;相同的地址数值。），在 64 位系统下，这个 union 只占用 1;;8 个字节，而不是 1;;24 个字节。
    • 无需赋值： 不存在 ht->arHash = ht->arData 这样的显式操作。PHP 只需要通过 malloc 计算好偏移量，将 Body 的“中轴线地址”存入这个 union 空间，三者便同时“激活”。
  2. 逻辑分身：多态视图
    虽然物理地址相同，但编译器根据指针类型赋予了它们不同的“观察视角”：
    • *arData 视角：将内存看作 1;;Bucket结构体 数组，用于处理带1;;字符串键名的1;;关联数组。用 Bucket* 步长（32B）访问正向数据区。
    • arPacked 视角：将内存看作1;;连续的 zval数组，用于处理1;;纯数字索引的1;;紧凑数组，跳过哈希计算以提升性能。
    • *arHash 视角：专门用于定位1;;索引映射区（Hash 查找的入口）。用 uint32_t* 步长（4B）访问负偏移索引区。
  3. 逻辑本质： PHP 并不是在三者间做选择题，而是把它们当作 同一原点上的三把不同尺寸的刻度尺。通过这种设计，PHP 在 56 字节的 Header 内，仅靠一个指针地址就远程遥控了整块复杂的 Body 内存。
特殊模式：Packed Array（arPacked）

arPacked 被激活时：

Hash 数组 (Index Table)「数据区」

*arData 之前的1;;负向偏移 1;;整型数组，存放 1;;8 个 1;;int32_t(占用 1;;8×4=32 字节)。通过uint32_t *arHash指针来操作数组。

uint32_t     *arHash;

Data 数组(Bucket 数组)「数据区」

*arData 之后的1;;正向偏移结构体数组，存储真正的 1;;Key、Value，存放 1;;8 个 Bucket，占用 1;;8×32=256 字节。

// 数据桶结构 (32 字节)
typedef struct _Bucket {
    zval              val; // 16 字节：值（或指向大数据的指针）
    zend_ulong        h;   // 8 字节：原始 Hash 值
    zend_string      *key; // 8 字节：字符串键指针（数字索引则为 NULL）
} Bucket;
_zval_struct：变量容器 (16 字节)

这是包装变量的“盒子”：包含值、类型信息、链表「哈希表查找」。

struct _zval_struct {
    zend_value        value;            /* 存储实际的值 (下述 8 字节 union) */
    union {
        uint32_t type_info;             /* 类型信息总和 (可一次性读写 4 字节) */
        struct {
            ZEND_ENDIAN_LOHI_3(         /* 适配大小端序的宏 */
                uint8_t    type,        /* 变量的当前类型 (如 IS_STRING, IS_LONG) */
                uint8_t    type_flags,  /* 类型标记 (如：是否可引用计数, 是否常驻内存) */
                union {
                    uint16_t  extra;    /* 额外信息，未进一步细化 */
                } u)
        } v;
    } u1;                               /* 辅助信息块 1 (4 字节) */
    union {
        uint32_t     next;                 /* 【💡关键】哈希冲突链：指向冲突链中的下一个元素下标 */
        uint32_t     cache_slot;           /* 缓存槽位 (用于参数初始化) */
        uint32_t     opline_num;           /* opline 编号 (用于快速调用) */
        uint32_t     lineno;               /* 行号 (用于 AST 节点) */
        uint32_t     num_args;             /* 参数数量 (用于 EX(This)) */
        uint32_t     fe_pos;               /* foreach 遍历位置 */
        uint32_t     fe_iter_idx;          /* foreach 迭代器索引 */
        uint32_t     guard;                /* 保护位 (防止循环递归和单一属性冲突) */
        uint32_t     constant_flags;       /* 常量标记 */
        uint32_t     extra;                /* 额外空间 */
    } u2;                               /* 辅助信息块 2 (4 字节) */
};
zend_value：数据的实际载体 (8 字节)

这是一个 union，意味着它在内存中只占用 8 字节。根据变量类型的不同，这 8 字节会被解析为不同的含义（直接存1;;值或1;;指针）。

typedef union _zend_value {
    zend_long         lval;             /* 💡长整型值 (Integer) */
    double            dval;             /* 双精度浮点值 (Float) */
    zend_refcounted  *counted;          /* 💡引用计数头指针 (通用) */
    zend_string      *str;              /* 字符串指针 */
    zend_array       *arr;              /* 数组指针 (HashTable) */
    zend_object      *obj;              /* 对象指针 */
    zend_resource    *res;              /* 资源类型指针 */
    zend_reference   *ref;              /* 引用类型指针 (&$var) */
    zend_ast_ref     *ast;              /* 抽象语法树节点指针 */
    zval             *zv;               /* 指向另一个 zval 的指针 */
    void             *ptr;              /* 通用指针 (底层内部使用) */
    zend_class_entry *ce;               /* 类定义指针 */
    zend_function    *func;             /* 函数定义指针 */
    struct {
        uint32_t w1;                    /* 两个 32 位字，用于直接操作 64 位空间 */
        uint32_t w2;
    } ww;
} zend_value;
特性 标量类型 (如 Integer/Float) 复杂类型 (如 String/Array)
8 字节 value 内容 存储真实数值 存储内存指针
内存分配 仅 zval 空间 zval + 堆内存空间
引用计数 不涉及 涉及 (管理内存释放)
寻址次数 0 次 (直接读取) 1 次 (通过指针跳转)

PHP 8.5.3 HashTable 存取全生命周期剖析

假设定义一个容量为 8 的数组，并执行：$a = ["id" => 123, "name" => "Gemini"];

内存申请：一体化连续布局

PHP 不会为索引和数据分别申请内存，而是通过一次 malloc 分配一块完整的物理空间。

数据扭转过程：标量 vs 复杂类型

场景 1：存储标量类型 $a["id"] = 123;
  1. 哈希映射：计算 "id" 的哈希值(DJBX33A 算法处理) h，通过掩码运算 nIndex = h | ht->nTableMask 映射到索引区的 -2 位置。
  2. 获取槽位：从 ht->nNumUsed 获取当前 Data 数组的空闲下标（假设为 0）。
  3. 建立映射：在索引区执行 ((int32_t*)*arData)[nIndex] = 0。
  4. 数据落盘：定位到 *arData[0]。
    • Bucket 填充：存入原始哈希值 h 和键名 "id" 的指针。
    • zval 填充：将 123 直接写入 zval.value.lval。
    • 状态标记：u1.type 设为 IS_LONG。
  5. 专业特征：原地存储。数据流终止于 *arData 块内部，无外部寻址，效率极高。
场景 2：存储复杂类型 $a["name"] = "Gemini";
  1. 外部准备：Zend 内存管理器先在堆（Heap）上申请一块内存，创建 zend_string 结构存储 "Gemini"，并初始化 gc.refcount = 1。
  2. 哈希映射：计算 "name" 的哈希映射位置为 -1。
  3. 建立映射：在 *arData[-1] 处存入下标 1。
  4. 数据落盘：定位到 *arData[1]。
    • zval 填充：zval.value.ptr 存入堆内存中 zend_string 的 8 字节内存地址。
    • 状态标记：u1.type 设为 IS_STRING，并开启 IS_TYPE_REFCOUNTED 标记。
  5. 专业特征：间接寻址。HashTable 仅作为索引网格，通过指针控制堆区的真实数据。
场景 3：读取 $a["name"]

当代码尝试读取变量时，CPU 经历以下精密步骤：

  1. 哈希定位：根据 "name" 再次算出索引区下标 -1。
  2. 获取偏移：从 *arData[-1] 读出 4 字节的 int32_t 数值 1。
  3. 物理跳转：
    • 计算公式：TargetAddress=*arData+(1×32 bytes)。
    • 由于 Bucket 大小固定为 32 字节，CPU 只需通过位移指令即可瞬间定位。
  4. 数据解析：
    • 进入 Bucket[1] 访问 zval。
    • 检查 u1.type 确认是字符串。
    • 读取 value.ptr 拿到 8 字节地址，跳转至堆内存取出 "Gemini"。

核心设计总结：为什么这样最快？

冲突扭转：当 $a["other"] 也映射到 -1 时

如果发生哈希碰撞，扭转过程会增加一个逻辑拉链环节：

  1. 读取旧主：从 *arHash[-1] 取出当前值 1。
  2. 插入新贵：新数据存入 Bucket[2]。
  3. 链条连接：将旧的下标 1 写入 Bucket[2].val.u2.next。
  4. 更新索引：将 *arHash[-1] 更新为 2。
    读取逻辑： 查询 -1 -> 得到 2 -> 检查 Bucket[2] -> Key 不匹配 -> 读取 Bucket[2].val.u2.next 得到 1 -> 检查 Bucket[1] -> Key 匹配 -> 返回数据。

arData 与 arHash：PHP 数组容量极限与索引重建的底层真相

arData 是按插入顺序线性排列的“物理仓库”，而 arHash 只是记录这些物理位置映射关系的“逻辑索引”，冲突通过在 arData 元素内部建立链表来解决。

核心推论：

由于容量受限于物理仓库 arData 的大小，当 arData 满载时，即便 arHash还有空余槽位，也必须触发扩容和同步 Rehash。

C源码 hash 增、改「数字」

/* 静态内联函数：通过数字索引（zend_ulong h）向哈希表中添加或更新数据 */
static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag)
{
    uint32_t nIndex;
    uint32_t idx;
    Bucket *p;
    zval *zv;

    IS_CONSISTENT(ht);     /* 校验哈希表一致性 */
    HT_ASSERT_RC1(ht);     /* 确保引用计数为 1 */

    /* 处理 HASH_ADD_NEXT 标志（如 $arr[] = v），确保下标不溢出 */
    if ((flag & HASH_ADD_NEXT) && h == ZEND_LONG_MIN) {
        h = 0;
    }

    /* --- 第一部分：Packed Array（紧凑模式）逻辑 --- */
    if (HT_IS_PACKED(ht)) {
        /* 如果不是强制追加，且下标 h 落在当前已使用范围内 */
        if ((flag & (HASH_ADD_NEW|HASH_ADD_NEXT)) != (HASH_ADD_NEW|HASH_ADD_NEXT)
         && h < ht->nNumUsed) {
            zv = ht->arPacked + h; /* 直接通过偏移量定位 zval */
            if (Z_TYPE_P(zv) != IS_UNDEF) { /* 如果该位置已有有效数据 */
                if (flag & HASH_LOOKUP) {
                    return zv;
                }
replace:        /* 更新逻辑：替换已有位置的值 */
                if (flag & HASH_ADD) {
                    return NULL; /* 如果是 HASH_ADD 模式且已存在，则返回失败 */
                }
                if (ht->pDestructor) {
                    ht->pDestructor(zv); /* 销毁旧值 */
                }
                ZVAL_COPY_VALUE(zv, pData); /* 拷贝新值 */
                return zv;
            } else { 
                /* 如果该位置是 IS_UNDEF（被 unset 的空洞），为了保持顺序，必须转为 Hash 模式 */
                goto convert_to_hash;
            }
        } 
        /* 如果下标 h 在当前分配的容量范围内，直接追加 */
        else if (EXPECTED(h < ht->nTableSize)) {
add_to_packed:
            zv = ht->arPacked + h;
            /* 增量初始化：如果新下标 h 跳过了中间的位置，将中间位置全部标记为 IS_UNDEF */
            if ((flag & (HASH_ADD_NEW|HASH_ADD_NEXT)) != (HASH_ADD_NEW|HASH_ADD_NEXT)) {
                if (h > ht->nNumUsed) {
                    zval *q = ht->arPacked + ht->nNumUsed;
                    while (q != zv) {
                        ZVAL_UNDEF(q);
                        q++;
                    }
                }
            }
            /* 更新计数器：nNextFreeElement 永远指向最大数字下标 + 1 */
            ht->nNextFreeElement = ht->nNumUsed = h + 1;
            ht->nNumOfElements++;
            if (flag & HASH_LOOKUP) {
                ZVAL_NULL(zv);
            } else {
                ZVAL_COPY_VALUE(zv, pData);
            }
            return zv;
        } 
        /* 判定是否需要对 Packed 数组进行扩容（满足空间效率时继续维持 Packed 模式） */
        else if ((h >> 1) < ht->nTableSize &&
                   (ht->nTableSize >> 1) < ht->nNumOfElements) {
            zend_hash_packed_grow(ht);
            goto add_to_packed;
        } 
        /* 否则：下标太离散，或者容量不足，准备转换模式 */
        else {
            if (ht->nNumUsed >= ht->nTableSize) {
                ht->nTableSize += ht->nTableSize;
            }
convert_to_hash:
            /* 【💡核心转折】：将紧凑数组转为普通的哈希数组（Mixed 模式） */
            zend_hash_packed_to_hash(ht);
        }
    } 
    /* --- 第二部分：未初始化状态处理 --- */
    else if (HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED) {
        /* 如果下标较小，优先初始化为 Packed 模式以节省内存 */
        if (h < ht->nTableSize) {
            zend_hash_real_init_packed_ex(ht);
            goto add_to_packed;
        }
        /* 否则初始化为常规 Hash (Mixed) 模式 */
        zend_hash_real_init_mixed(ht);
    } 
    /* --- 第三部分：常规 Hash (Mixed) 模式逻辑 --- */
    else {
        if ((flag & HASH_ADD_NEW) == 0 || ZEND_DEBUG) {
            /* 在 Hash 索引中寻找是否已有此数字下标 */
            p = zend_hash_index_find_bucket(ht, h);
            if (p) {
                if (flag & HASH_LOOKUP) {
                    return &p->val;
                }
                ZEND_ASSERT((flag & HASH_ADD_NEW) == 0);
                zv = &p->val;
                goto replace; /* 跳回上方的更新逻辑 */
            }
        }
        /* 【💡扩容触发】：Hash 模式下，如果满载，触发 Resize */
        ZEND_HASH_IF_FULL_DO_RESIZE(ht);
    }

    /* --- 第四部分：执行 Hash 模式下的物理插入 --- */
    idx = ht->nNumUsed++; /* 使用新的数据段槽位 */
    /* 💡索引关联：通过哈希值和掩码定位(负数下标)的索引槽位 */
    nIndex = h | ht->nTableMask;
    /* 定位物理 Bucket */
    p = ht->arData + idx;
    /* 💡处理冲突：当前 Bucket 的 next 指向索引槽位(原来)的值「-1：表示无冲突, >=0：表示有冲突,值为数据下标」 */
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);
    /* 💡建立映射：更新索引槽位，使其指向新插入的物理下标 idx */
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

    /* 更新下一个空闲下标计数 */
    if ((zend_long)h >= ht->nNextFreeElement) {
        ht->nNextFreeElement = (zend_long)h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
    }
    ht->nNumOfElements++;
    p->h = h;          /* 数字索引中，h 既是哈希值也是键名 */
    p->key = NULL;     /* 数字索引没有字符串 key */
    
    /* 填充最终的 Value */
    if (flag & HASH_LOOKUP) {
        ZVAL_NULL(&p->val);
    } else {
        ZVAL_COPY_VALUE(&p->val, pData);
    }

    return &p->val;
}

C源码 hash 增、改「字符串」

/* 静态内联函数：通过原始字符串（非 zend_string）添加或更新哈希表元素 */
static zend_always_inline zval *_zend_hash_str_add_or_update_i(HashTable *ht, const char *str, size_t len, zend_ulong h, zval *pData, uint32_t flag)
{
    zend_string *key;       /* 用于存储最终生成的 zend_string 对象指针 */
    uint32_t nIndex;       /* 索引段（负数下标）的槽位 */
    uint32_t idx;          /* 数据段（Bucket 数组）的下标 */
    Bucket *p;             /* 目标桶指针 */

    IS_CONSISTENT(ht);     /* 调试宏：校验哈希表一致性 */
    HT_ASSERT_RC1(ht);     /* 断言：确保哈希表引用计数为 1，无写时拷贝冲突 */

    /* 检查数组状态：如果是未初始化或是 Packed（紧凑数字索引）模式 */
    if (UNEXPECTED(HT_FLAGS(ht) & (HASH_FLAG_UNINITIALIZED|HASH_FLAG_PACKED))) {
        /* 如果未初始化，执行真正的初始化（分配内存并转为混合模式） */
        if (EXPECTED(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) {
            zend_hash_real_init_mixed(ht);
            goto add_to_hash; /* 初始化后直接跳转到末尾的新增逻辑 */
        } else {
            /* 如果是 Packed 模式，由于现在要插入字符串 Key，必须强制转为 Hash 模式 */
            zend_hash_packed_to_hash(ht);
        }
    } else if ((flag & HASH_ADD_NEW) == 0) {
        /* 如果不是强制新增（HASH_ADD_NEW），则先尝试在当前 Hash 表中查找该字符串 */
        p = zend_hash_str_find_bucket(ht, str, len, h);

        if (p) { /* 如果找到了 key 相同的 Bucket */
            zval *data;

            /* 处理 Lookup、Add、Update 等不同 flag 情况下的逻辑（同前一函数） */
            if (flag & HASH_LOOKUP) {
                return &p->val;
            } else if (flag & HASH_ADD) {
                /* 如果是添加模式但 key 已存在，处理间接引用逻辑，否则返回失败（NULL） */
                if (!(flag & HASH_UPDATE_INDIRECT)) {
                    return NULL;
                }
                ZEND_ASSERT(&p->val != pData);
                data = &p->val;
                if (Z_TYPE_P(data) == IS_INDIRECT) {
                    data = Z_INDIRECT_P(data);
                    if (Z_TYPE_P(data) != IS_UNDEF) {
                        return NULL;
                    }
                } else {
                    return NULL;
                }
            } else {
                /* 更新模式：获取原有数据的存储地址 */
                ZEND_ASSERT(&p->val != pData);
                data = &p->val;
                if ((flag & HASH_UPDATE_INDIRECT) && Z_TYPE_P(data) == IS_INDIRECT) {
                    data = Z_INDIRECT_P(data);
                }
            }
            /* 如果存在旧值且有析构函数，先清理旧数据 */
            if (ht->pDestructor) {
                ht->pDestructor(data);
            }
            /* 执行更新：将新数据拷贝到原有的 Bucket 位置 */
            ZVAL_COPY_VALUE(data, pData);
            return data;
        }
    }

    /* 【扩容入口】：如果哈希表已满，在此处触发 zend_hash_do_resize */
    ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /* If the Hash table is full, resize it */

add_to_hash:
    /* 开始物理分配：获取当前可用的数据段下标，并增加元素计数 */
    idx = ht->nNumUsed++;
    ht->nNumOfElements++;
    /* 定位到新增 Bucket 的物理地址 */
    p = ht->arData + idx;

    /* 【关键一步】：将传入的原始 char* 包装成 zend_string 对象，并存入 Bucket */
    /* 根据数组是否是持久化的（如 OpCache 存储），决定字符串的内存分配策略 */
    p->key = key = zend_string_init(str, len, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
#if ZEND_RC_DEBUG
    /* 调试模式下的引用计数处理 */
    if (GC_FLAGS(ht) & GC_PERSISTENT_LOCAL) {
        GC_MAKE_PERSISTENT_LOCAL(key);
    }
#endif
    /* 在 Bucket 中记录哈希值，并将哈希值同步缓存到 zend_string 结构体内 */
    p->h = ZSTR_H(key) = h;
    /* 既然插入了动态生成的 key，标记此哈希表不再仅包含静态 key */
    HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS;

    /* 填充数据段（Bucket）中的实际 Value 值 */
    if (flag & HASH_LOOKUP) {
        ZVAL_NULL(&p->val);
    } else {
        ZVAL_COPY_VALUE(&p->val, pData);
    }

    /* 💡索引关联：通过哈希值和掩码定位负数下标的索引槽位 */
    nIndex = h | ht->nTableMask;
    /* 💡处理冲突：当前 Bucket 的 next 指向索引槽位(原来)的值「-1：表示无冲突, >=0：表示有冲突,值为数据下标」 */
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);
    /* 💡建立映射：更新索引槽位，使其指向新插入的物理下标 idx */
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

    /* 返回新插入元素的地址 */
    return &p->val;
}

C源码「hash 重建、扩容」

/* 静态函数，使用 ZEND_FASTCALL 快速调用约定，负责执行哈希表的调整大小（扩容或重哈希）操作 */
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
    /* 调试宏：确保哈希表结构处于一致且有效的状态 */
    IS_CONSISTENT(ht);
    /* 断言检查：确保引用计数为 1，即只有当前逻辑在持有并修改此数组 */
    HT_ASSERT_RC1(ht);

    /* 断言检查：执行此函数前，数组必须已经不是 Packed（紧凑）模式，而是 Hash 模式 */
    ZEND_ASSERT(!HT_IS_PACKED(ht));

    /* 判断逻辑：如果已使用槽位（含已删除元素）显著多于有效元素（有效元素 + 有效元素的 1/32），
     * 说明数组中存在大量 unset 产生的“空洞”，此时不需要申请更多内存，只需原地清理碎片。
     */
    if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { 
        /* 调用 rehash 函数：通过全量扫描，剔除标记为 IS_UNDEF 的元素并重新构建索引 */
        zend_hash_rehash(ht);
    } 
    /* 如果有效元素确实很多，且当前容量尚未达到最大限制（HT_MAX_SIZE），则进行翻倍扩容 */
    else if (ht->nTableSize < HT_MAX_SIZE) { 
        /* 临时变量：存储新分配的内存地址，以及获取旧数据段的起始地址 */
        void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
        /* 计算新容量：将当前容量翻倍（nSize = nTableSize * 2） */
        uint32_t nSize = ht->nTableSize + ht->nTableSize;
        /* 保存旧的 Bucket 数组指针，用于稍后的数据拷贝 */
        Bucket *old_buckets = ht->arData;

        /* 确保新计算的掩码（Mask）是有效的 */
        ZEND_ASSERT(HT_SIZE_TO_MASK(nSize));

        /* 申请内存：根据新容量计算需要的总内存（索引段 + 数据段）。
         * pemalloc 会根据数组是否是持久化的（IS_ARRAY_PERSISTENT）选择分配方式。
         */
        new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
        
        /* 更新哈希表结构体中的容量值 */
        ht->nTableSize = nSize;
        /* 更新掩码：nTableMask = -nTableSize（用于哈希定位的位掩码） */
        ht->nTableMask = HT_SIZE_TO_MASK(ht->nTableSize);
        
        /* 将哈希表的数据指针指向新分配的内存地址，并自动计算出 arData 的偏移位置 */
        HT_SET_DATA_ADDR(ht, new_data);
        
        /* 【全量拷贝】：将旧 Bucket 数据段中的内容（共 nNumUsed 个）完整地拷贝到新分配的内存中。
         * 此时只是物理移动，索引关联尚未建立。
         */
        memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
        
        /* 释放旧的内存块 */
        pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
        
        /* 【索引重建】：由于容量和掩码变了，旧索引已失效。
         * 调用 zend_hash_rehash 遍历刚才拷贝过来的 Bucket，重新建立索引关联。
         */
        zend_hash_rehash(ht);
    } 
    /* 如果容量已经达到极限无法翻倍，抛出不可恢复的内存溢出错误 */
    else {
        zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
    }
}
重建hash
/* ZEND_API 定义的全局函数：用于重新哈希（重建索引） HashTable */
ZEND_API void ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
    Bucket *p;
    uint32_t nIndex, i;

    /* 调试宏：确保哈希表结构一致性 */
    IS_CONSISTENT(ht);

    /* 情况 1：如果哈希表实际上是空的（有效元素为 0） */
    if (UNEXPECTED(ht->nNumOfElements == 0)) {
        if (!(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) {
            ht->nNumUsed = 0;
            /* 立即重置索引段（清空所有哈希槽） */
            HT_HASH_RESET(ht);
            /* 重置内部指针和遍历器位置 */
            ht->nInternalPointer = 0;
            if (UNEXPECTED(HT_HAS_ITERATORS(ht))) {
                HashTableIterator *iter = EG(ht_iterators);
                HashTableIterator *end  = iter + EG(ht_iterators_used);
                while (iter != end) {
                    if (iter->ht == ht) {
                        iter->pos = 0;
                    }
                    iter++;
                }
            }
        }
        return;
    }

    /* 【核心开始】：立即重置索引表（清空旧映射） */
    HT_HASH_RESET(ht);
    i = 0;
    p = ht->arData;

    /* 💡情况 2：如果没有“空洞”（即没有被 unset 的元素，这是最快路径） */
    if (HT_IS_WITHOUT_HOLES(ht)) {
        do {
            /* 计算新哈希槽位：哈希值 | 掩码 */
            nIndex = p->h | ht->nTableMask;
            /* 头插法：当前 Bucket 的 next 指向索引槽位当前值 */
            Z_NEXT(p->val) = HT_HASH(ht, nIndex);
            /* 更新索引槽位：指向当前 Bucket 的下标 i */
            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
            p++;
        } while (++i < ht->nNumUsed); /* 这里的循环就是“同步重建”的直接证据 */
    } 
    /* 情况 3：存在“空洞”（含有 IS_UNDEF），需要执行“紧缩重排（Compaction）” */
    else {
        uint32_t old_num_used = ht->nNumUsed;
        do {
            /* 发现被删除的元素时开始执行紧缩逻辑 */
            if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
                uint32_t j = i;      /* j 是紧缩后的新下标 */
                Bucket *q = p;      /* q 指向紧缩后的目标位置 */

                /* 优化分支：如果没有外部迭代器，直接快速移动内存 */
                if (EXPECTED(!HT_HAS_ITERATORS(ht))) {
                    while (++i < ht->nNumUsed) {
                        p++;
                        if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
                            /* 将后面的有效 Bucket 拷贝到前面的空洞位置（物理重排） */
                            ZVAL_COPY_VALUE(&q->val, &p->val);
                            q->h = p->h;
                            nIndex = q->h | ht->nTableMask;
                            q->key = p->key;
                            /* 为重排后的 Bucket 重建索引映射 */
                            Z_NEXT(q->val) = HT_HASH(ht, nIndex);
                            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
                            /* 维护内部指针的一致性 */
                            if (UNEXPECTED(ht->nInternalPointer > j && ht->nInternalPointer <= i)) {
                                ht->nInternalPointer = j;
                            }
                            q++;
                            j++;
                        }
                    }
                } 
                /* 慢速分支：如果有迭代器，移动元素的同时还必须更新迭代器的位置指针 */
                else {
                    uint32_t iter_pos = zend_hash_iterators_lower_pos(ht, i + 1);

                    while (++i < ht->nNumUsed) {
                        p++;
                        if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
                            ZVAL_COPY_VALUE(&q->val, &p->val);
                            q->h = p->h;
                            nIndex = q->h | ht->nTableMask;
                            q->key = p->key;
                            Z_NEXT(q->val) = HT_HASH(ht, nIndex);
                            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
                            if (UNEXPECTED(ht->nInternalPointer > j && ht->nInternalPointer <= i)) {
                                ht->nInternalPointer = j;
                            }
                            /* 更新受元素物理位移影响的迭代器 */
                            if (UNEXPECTED(i >= iter_pos)) {
                                do {
                                    zend_hash_iterators_update(ht, iter_pos, j);
                                    iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1);
                                } while (iter_pos < i);
                            }
                            q++;
                            j++;
                        }
                    }
                }
                /* 更新数组已使用的槽位数（缩减了空洞） */
                ht->nNumUsed = j;
                break;
            }
            /* 处理没有发现空洞前的普通元素索引建立 */
            nIndex = p->h | ht->nTableMask;
            Z_NEXT(p->val) = HT_HASH(ht, nIndex);
            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
            p++;
        } while (++i < ht->nNumUsed);

        /* 更新末尾的迭代器位置 */
        if (UNEXPECTED(HT_HAS_ITERATORS(ht))) {
            _zend_hash_iterators_update(ht, old_num_used, ht->nNumUsed);
        }
    }
}

PHP 8.3 HashTable 核心机制：从全量拷贝到同步索引重建的深度溯源

场景设定

假设我们有一个容量为 4 的数组（nTableSize = 4，nTableMask = -4），目前已存入 3 个元素。我们要插入第 4 个元素，并触发扩容。

初始状态（扩容前）

第一阶段：新增元素（执行 _zend_hash_add_or_update_i）

当你执行 $a["key4"] = "value4" 时：

  1. 计算哈希：zend_string_hash_val("key4") 计算出哈希值，假设 h=100。
  2. 检查容量：执行 ZEND_HASH_IF_FULL_DO_RESIZE。此时 nNumUsed(3) < nTableSize(4)，暂不扩容。
  3. 分配槽位：idx = ht->nNumUsed++（得到 3），ht->nNumOfElements++。
  4. 填充数据：在 arData[3] 写入 key4 和 value4。
  5. 建立关联（核心点）：
    • 计算索引位：nIndex = 100 | -4（结果为 -4）。
    • 处理冲突：Z_NEXT(p->val) = HT_HASH(ht, -4)。如果之前 -4 位有数据（比如下标 1），则当前元素的 next 指向 1。
    • 更新索引：HT_HASH(ht, -4) = 3。现在索引槽 -4 指向了新插入的物理下标 3。

第二阶段：触发扩容（执行 zend_hash_do_resize）

当你再尝试插入第 5 个元素时，ZEND_HASH_IF_FULL_DO_RESIZE 发现 nNumUsed(4) == nTableSize(4)，触发扩容：

  1. 判定策略：检查没有空洞（nNumUsed == nNumOfElements），进入 else if 分支。
  2. 分配内存：nSize 翻倍为 8。申请一块能容纳 8 个索引位 + 8 个 Bucket 的连续内存。
  3. 更新掩码：nTableMask 更新为 -8。
  4. 全量拷贝（物理搬运）：
    • 执行 memcpy(ht->arData, old_buckets, sizeof(Bucket) * 4)。
    • 现状：此时 4 个旧 Bucket 已经躺在了新内存的 arData[0...3] 位置，但它们上方的新索引段（Hash表）全是空的（或旧数据）。
  5. 进入重建：调用 zend_hash_rehash(ht)。

第三阶段：重建索引关联（执行 zend_hash_rehash）

这是旧数据与新 Hash 关联的核心过程。函数内部开始 O(n) 循环：

1. 初始化

执行 HT_HASH_RESET(ht)，通过 memset 将 8 个索引槽位全部设为 -1。

2. 同步遍历重建（旧数据重绑定）

程序开始 do...while 循环遍历数据段中拷贝过来的 4 个旧 Bucket：

总结：旧数据是如何关联的？

通过源码我们可以看到，全量拷贝后的关联细节如下：

  1. 物理位置不变：memcpy 保证了数据在 arData 数组里的下标（0, 1, 2, 3）在扩容前后保持一致。
  2. 索引重新计算：由于掩码（Mask）从 -4 变为了 -8，旧的映射逻辑彻底作废。
  3. 强制同步循环：zend_hash_rehash 就像一个“收件员”，它挨个扫描已经搬进新家的 Bucket，查阅它们的哈希值，重新计算出它们在新索引表中的“房间号”，并将这个房间号（负数下标）与 Bucket 的物理下标（正数下标）重新连线。

当这个循环结束时，扩容才算真正完成。 此时，HashTable 已经为接下来的 O(1) 查找做好了全量索引准备。
你想了解如果这 4 个元素中有被 unset 标记为 IS_UNDEF 的元素，zend_hash_rehash 是如何通过“双指针”进行物理位置压缩的吗？

指针原点，左右开弓——PHP HashTable 负偏移寻址的内存哲学

理解 (ht)->arHash 怎么变成“数组”并取出数据，关键在于理解：在 C 语言中，指针和数组在内存寻址上的本质是完全等价的。

1. 物理真相：指针即“基准地址”

uint32_t *arHash 是一个指针（占用 8 字节），存储的是1;;内存地址（0x1000）。
在 C 语言中，编译器会将ptr[idx]翻译为：1;;目标地址=ptr+(idx×sizeof(类型))
执行过程拆解：

2. 内存布局：谁给*arHash准备了数据？

因为[[Hash算法与数据库实现#union 的设计]]，*arHash和*arData 左边的 32 字节是合法分配给这个 HashTable 使用的。*arHash 指针只是这块连续内存的一个“反向访问入口”。

// 1. 申请的总大小 = 索引区(32B) + 数据区(256B)
void *mem = malloc(32 + 256);
// 2. *arData 指向中间位置（跳过索引区）
ht->arData = (Bucket *)((char *)mem + 32);
// 3. 💡因为是 union 共用一块内存，会使变量 *arHash 也指向这里 (0x1020)
ht->arHash = (uint32_t *)ht->arData;

3. C 语言与 Go 语言的语法对比

操作层面 PHP (C 语言实现) Go (Golang 实现)
指针下标 ptr[-1] (合法且常用) 不允许 (指针不支持 [] 运算)
负向寻址 自由偏移，直接物理取数 严禁越过指针起始点往回找
解引用 ((uint32_t*)data)[idx] *(*uint32)(unsafe.Pointer(uintptr(ptr) - 4))
Go 的哲学：如果你想访问内存，必须从 0 开始往后数。
C 的哲学：我给你一个地址（指针），只要你别把系统搞崩，你想往回数（负索引）还是往前数（正索引）随你便。

💡 形象比喻

想象一把尺子：

总结

PHP 的设计是非常 “务实主义” 的：

  1. 用 Index Table 保证了查询是 O(1)。
  2. 用 Data 数组物理顺序 保证了 foreach 的有序性且无需额外指针。
  3. 用 32 字节对齐 保证了 CPU 寻址的高效。

Java：引入红黑树优化

底层结构：Node 数组 + 单向链表/红黑树

Go：紧凑的桶设计

底层结构：hmap 结构体 + bmap (桶) 数组

总结