用线性哈希逐桶扩展动态对象索引
OpenSSL 的 LHASH 以分裂位置 p 记录扩展进度，逐桶重新分配节点；动态 ASN.1 对象注册使用这个通用容器。
工程问题#
应用可在运行时注册对象标识符及名称，需要按不同键查找；对象数量增长时，固定桶数会让冲突链变长，而一次搬迁全部节点会集中放大插入成本。
实际实现#
对象注册把类型不同的 ADDED_OBJ 包装放入同一个 LHASH。插入前检查负载，达到阈值则 expand 分裂 p 对应的桶：已有节点按保存的 hash 留在原桶或转入 p+pmax。getrn 根据桶是否已分裂选择取模范围，使扩展中的查询仍能定位正确桶。
处理流程#
- 动态对象注册先持写锁检查名称、数据和 NID 冲突
- 插入前按负载阈值决定是否分裂下一桶
- 只重排分裂桶的冲突链，并推进分裂位置
- 查找时依据 p 选择当前映射，再比较 hash 与实际对象键
源码片段#
固定版本 · 原文摘录793 if (!ossl_obj_write_lock()) {794 ERR_raise(ERR_LIB_OBJ, ERR_R_UNABLE_TO_GET_WRITE_LOCK);795 goto err2;796 }797798 for (i = ADDED_DATA; i <= ADDED_NID; i++) {799 if (ao[i] == NULL)800 continue;801 ao[i]->type = i;802 ao[i]->obj = o;803 if ((aop[i] = lh_ADDED_OBJ_retrieve(added, ao[i])) != NULL)804 dup = aop[i]->obj;805 }动态索引更新在对象写锁下进行，并先检查各类键冲突。
823 for (i = ADDED_DATA; i <= ADDED_NID; i++) {824 if (ao[i] == NULL)825 continue;826 (void)lh_ADDED_OBJ_insert(added, ao[i]);827 if (lh_ADDED_OBJ_error(added)) {828 while (i-- > ADDED_DATA) {829 if (ao[i] != NULL)830 lh_ADDED_OBJ_delete(added, ao[i]);831 }832 ERR_raise(ERR_LIB_OBJ, ERR_R_CRYPTO_LIB);833 goto err;834 }835 }836 o->flags &= ~(ASN1_OBJECT_FLAG_DYNAMIC | ASN1_OBJECT_FLAG_DYNAMIC_STRINGS | ASN1_OBJECT_FLAG_DYNAMIC_DATA);837838 ossl_obj_unlock();839 return o->nid;同一 ASN.1 对象建立多个类型的索引包装；插入失败会回滚此前登记。
117void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)118{119 unsigned long hash;120 OPENSSL_LH_NODE *nn, **rn;121 void *ret;122123 lh->error = 0;124 if ((lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)) && !expand(lh))125 return NULL; /* 'lh->error++' already done in 'expand' */126127 rn = getrn(lh, data, &hash);128129 if (*rn == NULL) {130 if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) {131 lh->error++;132 return NULL;133 }134 nn->data = data;135 nn->next = NULL;136 nn->hash = hash;137 *rn = nn;插入前检查负载并调用 expand，随后寻找桶内位置。
248 nni = lh->num_alloc_nodes;249 p = lh->p;250 pmax = lh->pmax;251 if (p + 1 >= pmax) {252 j = nni * 2;253 n = OPENSSL_realloc_array(lh->b, j, sizeof(OPENSSL_LH_NODE *));254 if (n == NULL) {255 lh->error++;256 return 0;257 }258 lh->b = n;259 memset(n + nni, 0, sizeof(*n) * (j - nni));260 lh->pmax = nni;261 lh->num_alloc_nodes = j;262 lh->p = 0;263 } else {264 lh->p++;265 }推进分裂轮次；到轮次边界仍需扩大桶指针数组。
267 lh->num_nodes++;268 n1 = &(lh->b[p]);269 n2 = &(lh->b[p + pmax]);270 *n2 = NULL;271272 for (np = *n1; np != NULL;) {273 hash = np->hash;274 if ((hash % nni) != p) { /* move it */275 *n1 = (*n1)->next;276 np->next = *n2;277 *n2 = np;278 } else279 n1 = &((*n1)->next);280 np = *n1;281 }只处理当前分裂桶，根据保存的 hash 将节点留在原链或移至新桶。
329 *rhash = hash;330331 nn = hash % lh->pmax;332 if (nn < lh->p)333 nn = hash % lh->num_alloc_nodes;334335 ret = &(lh->b[(int)nn]);336 for (n1 = *ret; n1 != NULL; n1 = n1->next) {337 if (n1->hash != hash) {338 ret = &(n1->next);339 continue;340 }341342 if (lh->compw != NULL) {343 if (lh->compw(n1->data, data, lh->comp) == 0)344 break;345 } else {346 if (lh->comp(n1->data, data) == 0)347 break;348 }349 ret = &(n1->next);先使用 pmax 取模；桶已分裂时再使用更大的范围，最后比较实际键。
摘录分别保留调用入口、核心机制及边界；完整上下文见各段源码链接。
收益与取舍#
工程分析带来的收益
- 分裂时复用节点中保存的 hash，不必重新计算全部对象的散列值
- 查询由分裂进度决定桶位置，不需要在两张完整表之间逐个尝试
付出的代价
- 单桶分裂仍要遍历整条冲突链，不能保证每次插入固定耗时
- 一轮分裂完成附近会 realloc 桶指针数组并清零新增区域；逐桶搬迁不等于完全消除扩容停顿
- LHASH 自身不是并发容器，对象注册路径的同步由外层锁提供
可比较的选择
一次性重新散列结构简单，但扩容操作集中遍历并搬迁全部条目。
双表渐进式迁移可分批迁移，但查询和删除必须处理新旧两张表；与此处按 p 推导桶位置不同。
版本与适用范围#
固定到提交 b86f4c163100。只分析通用 LHASH 扩展和动态对象注册，不涉及密码算法或常数时间安全保证。完整源码还含收缩逻辑；此例未把扩展流程推广为删除路径。
参考来源#
源码、官方文档与原始论文crypto/objects/obj_dat.c · add_object
crypto/lhash/lhash.c · OPENSSL_LH_insert
相关实现与比较#
4 个相关案例Redis 7.2.0 的字典扩缩容保留新旧两张哈希表，逐桶迁移，降低一次性搬迁全部条目的停顿。
QEMU TCG 用 QHT 保存 TranslationBlock 索引，帮助复用与当前客体执行状态一致的翻译结果。
libvirt 为 Domain 对象维护 UUID 与名称两个哈希索引，两个入口指向同一个对象。
把上下文身份编码进块哈希，让重复请求共享已经计算的 KV cache。