哈希

PostgreSQL 哈希索引先利用哈希码缩小等值查询的候选范围，再回到表中核对原始值。哈希匹配只说明“可能相等”，不能直接证明相等。两个不同值可能具有相同哈希码，不同哈希码也可能映射到同一个桶。正常复核存在时，碰撞和共享桶都不意味着查询会返回错误结果；它们是实现需要处理的普通情况，而不是可以忽略的例外。 桶里究竟保存什么 索引条目包含四字节哈希值和指向表元组的引用，不保存完整的被索引列值。桶映射把查询导向相关索引页面。桶是共享存储空间，并不是给每个不同键单独分配一个专属位置。一个桶的主页装满后，可以继续连接溢出页，查询这个桶时也需要访问这些页面。因此，“一次算出桶”不等于“永远只读取一个页面”。 PostgreSQL 可以在单个索引页内部按哈希码排序，以便加速局部搜索，但这不会提供原始列值的顺序。哈希索引不能满足键范围或有序输出，只支持单列等值访问，不能强制唯一性，也不支持 IS NULL。B-tree 仍然可以服务等值查询，同时支持更广的一组操作，不能因为键看起来适合哈希就自动排除其他候选。 由于条目中没有原始值，哈希扫描是有损候选扫描，需要用表中实际值复核。因此，碰撞可以在执行计划中表现为 Rows Removed by Index Recheck。这说明数据库正确剔除了只在哈希上匹配的候选，而不是把两个碰撞值都当成相等返回。解读这项指标时，应把候选数量与最终答案区分开。 坏掉的样子 把索引键更新描述为“只碰一个桶”，掩盖了实际工作。修改被索引列会改变元组对应的索引值，新条目可能进入另一个桶。PostgreSQL 使用行版本与延后索引清理，旧引用不一定立刻从结构中消失。数据增长还可能触发桶分裂，溢出页也会增加读写。因此不能用一个理想化的哈希表赋值过程来解释数据库的全部更新成本。 高度重复的值、快速增长的表，与近乎唯一而稳定的等值负载，表现可能很不一样。哈希查询不是无条件的恒定延迟承诺。现代 PostgreSQL 的哈希索引支持崩溃恢复，但持久性既不会消除维护成本，也不会让它突然具备唯一性约束能力。读性能、写维护和数据契约必须分别确认。 快速验证 在可丢弃的 PostgreSQL 18 数据库中，用 psql 执行下面代码。它建立二十万个采用 C 排序规则的临时文本键，使用当前服务器自己的 hashtext 找到一组碰撞，再验证等值查询和键更新。实验没有把哈希码当成跨版本稳定的业务标识，最后回滚会移除所有夹具。 \set ON_ERROR_STOP on BEGIN; CREATE TEMP TABLE hash_items (key text COLLATE "C"); INSERT INTO hash_items SELECT 'key-'||g FROM generate_series(1,200000) AS g; CREATE TEMP TABLE collision_pair AS SELECT min(key) AS a,max(key) AS b FROM hash_items GROUP BY hashtext(key) HAVING count(*)>1 ORDER BY hashtext(key) LIMIT 1; SELECT a AS collision_a,b AS collision_b FROM collision_pair \gset SELECT a,b,hashtext(a),hashtext(b) FROM collision_pair; CREATE INDEX hash_items_key ON hash_items USING hash(key); ANALYZE hash_items; EXPLAIN (ANALYZE, BUFFERS, TIMING OFF) SELECT key FROM hash_items WHERE key=:'collision_a'; UPDATE hash_items SET key='changed-'||key WHERE key=:'collision_a'; SELECT count(*) AS old_key_rows FROM hash_items WHERE key=:'collision_a'; SELECT count(*) AS new_key_rows FROM hash_items WHERE key='changed-'||:'collision_a'; DO $$ BEGIN IF (SELECT hashtext(a)=hashtext(b) AND a<>b FROM collision_pair) IS DISTINCT FROM true THEN RAISE EXCEPTION 'fixture did not establish a collision'; END IF; IF (SELECT count(*) FROM hash_items h JOIN collision_pair p ON h.key=p.a) <> 0 OR (SELECT count(*) FROM hash_items h JOIN collision_pair p ON h.key='changed-'||p.a) <> 1 OR (SELECT count(*) FROM hash_items h JOIN collision_pair p ON h.key=p.b) <> 1 THEN RAISE EXCEPTION 'hash lookup or indexed update returned wrong keys'; END IF; END $$; ROLLBACK; PostgreSQL 18.6 中找到的两个键是 key-129539 与 key-7295，哈希码都是 -1960436116。等值计划使用 hash_items_key，最终只返回一行，同时报告一行被索引复核移除。两段字符串虽然哈希相同，却仍然是不同的值。这是反对“哈希码没有碰撞”这一错误假设的实际负向验证，不能用普通的无碰撞点查替代。 ...

一致性哈希限制成员变化时的数据放置变化，但它本身不搬运数据、不让副本达成一致，也不把单个热键的请求自动分散。经典顺时针哈希环把键交给哈希位置之后遇到的第一个节点点位；如果位置恰好相等，就归该点，超过最大点位则绕回最小点位。理解这个查找方向，是判断迁移范围的前提。 先把归属区间画对 一个点拥有的是前驱之后到自身为止的区间，即 (前驱, 当前点]。假设 A 位于 20，B 位于 50，C 位于 80，那么 B 负责大于 20 且不大于 50 的位置；超过 80 的键绕回 A。这不是从 B 到其后继 C 的弧段，左右端点是否包含也不是可以随意改变的细节。 在 35 加入 D，它从顺时针后继 B 手中取得大于 20 到 35 的位置；移除 B，则将 B 原来负责的区间交给 C。未受影响的点位保持原位置及归属，这才是算法有用的性质。仅说“移动一小段弧”还不够，因为原来某段弧可能就占据整个环的很大一部分。 作为对照，直接用 hash(key) 对节点数量取模来选择数组下标，新增节点会改变除数，很多键随之选到别的下标。四个等容量且平衡的节点扩到五个时，理想哈希环大约需要迁移五分之一的键，但真实迁移比例取决于点位与键分布，不能把这个比例当成所有部署都成立的保证。 ...

Redis 哈希把多个字段名及其字节值放在一个键下，适合按属性独立读取或修改的对象，例如拥有姓名和积分的用户资料。HGET 与 HSET 各自都只需要一条命令，并不会因为多了一层字段组织，就天然比字符串多一次网络往返。类型选择的依据是实际访问粒度，而不是把内部结构想象成额外的远程查询。 只读取和更新目标字段 HGET 获取一个字段，HMGET 按请求顺序获取指定字段，HGETALL 则返回所有字段和值。Redis 不会自动把某个字段值解释为嵌套对象，不会把带点的字段名当作对象路径，也不会自动为任意属性组合建立查询索引。字段如何命名、值如何序列化，仍然由应用负责。 HSET 可以在一条命令里写多个字段，未指定的字段不会被替换。它的整数返回值统计新增字段数，而不是所有发生变化的值：更新已有字段即使成功，也可以返回零。HDEL 返回实际删除的字段数；最后一个字段删除后，整个哈希键也会消失。因此，不能用一个没有字段的哈希作为长期存在的占位对象。 字段缺失和空值是两种状态。redis-py 关闭自动解码时，HMGET 对缺失字段返回 None，对已存在但内容为空的字段返回空字节串。直接用真假值判断会混淆两者，应按明确的返回值区分。HGETALL 对小对象很方便，但处理量和响应大小会随整个哈希增长；调用方只需要几个属性时，应该直接读取这些字段，避免每次搬运全部数据。 过期时间分为两层 键级过期会删除整个哈希，HSET 会保留该键已有的截止时间。从 Redis 7.4 开始，还可以通过 HEXPIRE 和 HPEXPIRE 给单个字段设置期限。普通 HSET 覆盖字段时会清除这个字段自己的过期时间，HINCRBY 则保留被修改字段的已有期限。字段 TTL 返回 -1，只表示它没有独立的字段期限，不代表它能逃过父键到期后整体删除。 Redis 8.0 及更新版本提供 HSETEX，可以把字段值与字段期限放在同一条命令里写入；其 KEEPTTL 选项能在替换字段值时保留已有字段截止时间。先 HSET、再 HPEXPIRE 仍然是两条操作，中间失败会产生值已经变更、期限尚未附加的窗口。应根据希望保留、重置还是新建期限来选命令，并在采用字段过期能力前核对实际部署版本，不能把键级与字段级期限混为一谈。 ...