声明：本文的部分内容参考了他人的文章。在编写过程中，我们尊重他人的知识产权和学术成果，力求遵循合理使用原则，并在适用的情况下注明引用来源。
本文主要参考了 OpenGauss1.1.0 的开源代码和《OpenGauss数据库源码解析》一书以及OpenGauss社区学习文档。
在对源码的不断学习中，经常可以看到一个名为 hash_search 的函数，该函数用于在哈希表中查找键并执行相应操作。先前一直没有仔细看过该函数的内部逻辑，本文则来详细的学习一下吧。
hash_search 函数是用于在哈希表中进行通用的查找、插入和删除操作的实现。通过调用 hash_search_with_hash_value 函数，该函数提供了对哈希表中元素的查找、插入和删除的支持，具体操作由传入的 action 参数决定。action 参数可以取值为 HASH_FIND（查找）、HASH_ENTER（插入）、HASH_ENTER_NULL（插入，返回 NULL 如果内存不足）和 HASH_REMOVE（删除）。函数返回 找到/插入/删除 的元素的指针，或者如果没有找到匹配项则返回 NULL。此函数通过提供通用的哈希表操作，实现了对哈希表中数据的灵活管理，支持不同应用场景的需求。函数源码如下所示：（路径：src/common/backend/utils/hash/dynahash.cpp）
/*
* hash_search -- 在哈希表中查找键并执行相应操作
* hash_search_with_hash_value -- 在哈希表中查找键并执行相应操作，提供预先计算的哈希值
*
* action 的取值包括：
* HASH_FIND: 在表中查找键
* HASH_ENTER: 在表中查找键，如果不存在则创建新条目
* HASH_ENTER_NULL: 在表中查找键，如果不存在则创建新条目，如果内存不足则返回 NULL
* HASH_REMOVE: 在表中查找键，如果存在则删除条目
*
* 返回值是找到/插入/删除的元素的指针，如果没有找到匹配项则返回 NULL。
* (注意：在 REMOVE 操作中，结果是一个悬空指针，不应该被解引用！)
*
* 如果 foundPtr 不为 NULL，则 *foundPtr 被设置为 TRUE，表示在表中找到现有条目，为 FALSE 则表示没有找到。
* 这对于 HASH_ENTER 操作是必需的，但在其他情况下与返回值重复。
*
* 对于 hash_search_with_hash_value，hashvalue 参数必须先使用 get_hash_value() 计算。
*/
void* hash_search(HTAB* hashp, const void* keyPtr, HASHACTION action, bool* foundPtr)
{
// 调用 hash_search_with_hash_value 函数，传递哈希值参数为使用哈希函数计算得到的哈希值
return hash_search_with_hash_value(hashp, keyPtr, hashp->hash(keyPtr, hashp->keysize), action, foundPtr);
}
函数 hash_search 的入参如下：
- HTAB* hashp：指向哈希表的指针，是哈希表的控制结构。
- const void* keyPtr：指向要查找、插入或删除的键值的指针。
- HASHACTION action：指定要执行的操作，可以取以下值：
- HASH_FIND：查找键值。
- HASH_ENTER：查找键值，如果不存在则创建新条目。
- HASH_ENTER_NULL：查找键值，如果不存在则创建新条目，如果内存不足则返回 NULL。
- HASH_REMOVE：查找键值，如果存在则删除条目。
- bool* foundPtr：指向一个布尔型变量的指针，用于接收是否找到现有条目的信息。如果不关心此信息，可以将其设置为 NULL。
hash_search_with_hash_value 函数是一个通用的哈希表查找、插入和删除元素的核心函数，根据给定的哈希值和键值，它在哈希表中进行查找，如果元素存在则返回指向元素的指针，如果不存在则根据操作类型进行相应的处理。支持的操作类型包括查找（HASH_FIND）、插入（HASH_ENTER）、插入并返回 NULL（HASH_ENTER_NULL）和删除（HASH_REMOVE）。函数内部通过哈希值定位到对应的哈希桶，再在哈希桶的冲突链上进行查找或执行插入和删除操作。在插入时，如果哈希表满了，会进行自动扩展。函数同时考虑哈希表的分区模式、冻结状态和哈希表顺序扫描的情况，确保操作的正确性和高效性。函数源码如下所示：（路径：src/common/backend/utils/hash/dynahash.cpp）
/*
* 根据哈希值进行哈希表的查找、插入和删除操作，支持不同的操作和返回结果。
*
* 入参：
* - hashp: 指向哈希表的指针，包含哈希表的属性和方法。
* - keyPtr: 要查找、插入或删除的键值的指针。
* - hashvalue: 已经计算好的键值的哈希值。
* - action: 操作类型，可以是 HASH_FIND、HASH_ENTER、HASH_ENTER_NULL 或 HASH_REMOVE。
* - foundPtr: 用于接收是否找到元素的指针，如果不关心，可以设置为 NULL。
*
* 返回值：
* - 查找操作（HASH_FIND）返回找到的元素的指针，如果未找到则返回 NULL。
* - 插入操作（HASH_ENTER 或 HASH_ENTER_NULL）返回新插入的元素的指针，如果出错或内存不足则返回 NULL。
* - 删除操作（HASH_REMOVE）返回被删除的元素的指针，如果未找到或出错则返回 NULL。
*
* 注意：该函数对哈希表进行查找、插入和删除操作，同时考虑了哈希表的扩展和元素的内存管理。
*/
void* hash_search_with_hash_value(HTAB* hashp, const void* keyPtr, uint32 hashvalue, HASHACTION action, bool* foundPtr)
{
HASHHDR* hctl = hashp->hctl; // 哈希表的控制信息
Size keysize; // 键值的大小
uint32 bucket; // 哈希桶的编号
long segment_num; // 哈希段的编号
long segment_ndx; // 哈希段内的索引
HASHSEGMENT segp; // 哈希段
HASHBUCKET currBucket; // 当前哈希桶
HASHBUCKET* prevBucketPtr = NULL; // 前一个哈希桶的指针
HashCompareFunc match = NULL; // 键值比较函数
int freelist_idx = FREELIST_IDX(hctl, hashvalue); // 自由链表的索引
// 统计哈希表的访问次数
#if HASH_STATISTICS
hash_accesses++;
hctl->accesses++;
#endif
/*
* 如果是插入操作，检查是否需要拓展哈希表的桶数量。
*/
if (action == HASH_ENTER || action == HASH_ENTER_NULL) {
/*
* 如果哈希表是分区模式、冻结状态、或者有活跃的哈希表顺序扫描，就不能进行拓展。
* 此处顺序检查的次序是为了先检查成本较低的条件。
*/
if (!IS_PARTITIONED(hctl) && !hashp->frozen &&
hctl->freeList[0].nentries / (long)(hctl->max_bucket + 1) >= hctl->ffactor && !has_seq_scans(hashp)) {
(void)expand_table(hashp);
}
}
/*
* 进行初始查找
*/
bucket = calc_bucket(hctl, hashvalue);
segment_num = bucket >> hashp->sshift;
segment_ndx = MOD(bucket, hashp->ssize);
segp = hashp->dir[segment_num];
if (segp == NULL) {
hash_corrupted(hashp);
}
prevBucketPtr = &segp[segment_ndx];
currBucket = *prevBucketPtr;
/*
* 跟随冲突链查找匹配的键值
*/
match = hashp->match; // 保存一次键值比较函数的调用
keysize = hashp->keysize; // 保存一次键值的大小
while (currBucket != NULL) {
if (currBucket->hashvalue == hashvalue && match(ELEMENTKEY(currBucket), keyPtr, keysize) == 0) {
break;
}
prevBucketPtr = &(currBucket->link);
currBucket = *prevBucketPtr;
#if HASH_STATISTICS
hash_collisions++;
hctl->collisions++;
#endif
}
// 将是否找到元素的信息写入 foundPtr
if (foundPtr != NULL) {
*foundPtr = (bool)(currBucket != NULL);
}
// 根据不同的操作类型进行处理
switch (action) {
case HASH_FIND: {
// 查找操作，返回找到的元素指针，未找到返回 NULL
if (currBucket != NULL) {
return (void*)ELEMENTKEY(currBucket);
}
return NULL;
}
case HASH_REMOVE: {
// 删除操作，返回被删除的元素指针，未找到返回 NULL
if (currBucket != NULL) {
// 如果是分区模式，需要锁定以修改 nentries 和 freeList
if (IS_PARTITIONED(hctl)) {
SpinLockAcquire(&(hctl->freeList[freelist_idx].mutex));
}
Assert(hctl->freeList[freelist_idx].nentries > 0);
hctl->freeList[freelist_idx].nentries--;
// 从哈希桶链表中移除记录
*prevBucketPtr = currBucket->link;
// 将记录添加到哈希表的自由链表中
currBucket->link = hctl->freeList[freelist_idx].freeList;
hctl->freeList[freelist_idx].freeList = currBucket;
// 如果是分区模式，释放锁
if (IS_PARTITIONED(hctl)) {
SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
}
/*
* 注意：最好确保调用者在这个元素上同步访问，因为其他代码将会
* 在下一次插入时重新使用它。
*/
return (void*)ELEMENTKEY(currBucket);
}
return NULL;
}
case HASH_ENTER_NULL: {
// 插入并返回新插入的元素指针，如果失败返回 NULL
// ENTER_NULL 无法与基于 palloc 的分配器一起使用
Assert(hashp->alloc != DynaHashAlloc || hashp->alloc != DynaHashAllocNoExcept);
/* FALL THRU */
}
case HASH_ENTER: {
// 插入并返回新插入的元素指针，如果失败返回 NULL
// 如果已经存在元素，则返回找到的元素的指针
if (currBucket != NULL) {
return (void*)ELEMENTKEY(currBucket);
}
// 如果是冻结状态，则不能插入
if (hashp->frozen) {
if (hashp->alloc == DynaHashAllocNoExcept) {
write_stderr("cannot insert into frozen hashtable \"%s\"", hashp->tabname);
return NULL;
}
ereport(ERROR,
(errcode(ERRCODE_INVALID_OPERATION),
errmsg("cannot insert into frozen hashtable \"%s\"", hashp->tabname)));
}
// 从哈希表的自由链表中获取一个新的哈希桶
currBucket = get_hash_entry(hashp, freelist_idx);
if (currBucket == NULL) {
// 内存不足，返回 NULL
if (action == HASH_ENTER_NULL) {
return NULL;
}
// libcomm 永久线程不能使用 elog
if (hashp->alloc == DynaHashAllocNoExcept || t_thrd.comm_cxt.LibcommThreadType != LIBCOMM_NONE) {
return NULL;
}
// 报告通用错误消息
if (hashp->isshared) {
ereport(ERROR, (errcode(ERRCODE_OUT_OF_MEMORY), errmsg("out of shared memory")));
} else {
ereport(ERROR, (errcode(ERRCODE_OUT_OF_MEMORY), errmsg("out of memory")));
}
}
// 将新元素链接到哈希桶链表中
*prevBucketPtr = currBucket;
currBucket->link = NULL;
// 将键值复制到记录中
currBucket->hashvalue = hashvalue;
if (hashp->keycopy == memcpy) {
errno_t errorno = EOK;
errorno = memcpy_s(ELEMENTKEY(currBucket), keysize, keyPtr, keysize);
securec_check(errorno, "\0", "\0");
} else {
hashp->keycopy(ELEMENTKEY(currBucket), keyPtr, keysize);
}
/*
* 调用者应该在返回后填充数据字段。
* 不要在这里插入可能引发错误的代码，因为这样会导致记录不完整，
* 从而损坏调用者的数据结构。
*/
return (void*)ELEMENTKEY(currBucket);
}
default:
break;
}
// 未识别的操作类型，报错
if (hashp->alloc == DynaHashAllocNoExcept) {
write_stderr("unrecognized hash action code: %d", (int)action);
} else {
ereport(ERROR, (errcode(ERRCODE_INVALID_OPERATION), errmsg("unrecognized hash action code: %d", (int)action)));
}
return NULL; // 保持编译器静默
}
内联函数 calc_bucket 用于将给定的哈希值转换为哈希表中的桶号。通过使用哈希表控制结构中的 high_mask 和 low_mask 进行按位与运算，确保计算得到的桶号在哈希表的有效范围内。该函数旨在实现将哈希值映射到哈希表桶的过程，以便在哈希表中查找、插入或删除元素时能够有效地定位到对应的桶。函数源码如下所示：（路径：src/common/backend/utils/hash/dynahash.cpp）
/*
* 描述: 将哈希值转换为桶号的内联函数。
* 参数:
* @in hctl: 哈希表控制结构。
* @in hash_val: 待转换为桶号的哈希值。
* 返回值: uint32 - 计算得到的桶号。
*/
static inline uint32 calc_bucket(HASHHDR* hctl, uint32 hash_val)
{
uint32 bucket;
// 使用 high_mask 获取初始桶号。
bucket = hash_val & hctl->high_mask;
// 如果初始桶号超过最大桶号，使用 low_mask 进行调整。
if (bucket > hctl->max_bucket) {
bucket = bucket & hctl->low_mask;
}
// 返回最终计算得到的桶号。
return bucket;
}
get_hash_entry 函数用于从哈希表的自由列表中获取一个新的哈希表元素。函数根据给定的自由列表索引和哈希表控制结构，尝试从自由列表中获取一个元素。如果自由列表中没有空闲元素，则根据哈希表的分区策略尝试从其他分区借用元素。如果所有尝试都失败，函数返回 NULL。如果成功获取到元素，函数会从自由列表中移除该元素，并增加相应的计数。如果是分区哈希表，函数在操作自由列表时会使用自旋锁确保线程安全。函数源码如下所示：（路径：src/common/backend/utils/hash/dynahash.cpp）
/*
* 描述：如果可能，创建一个新的哈希表元素。
* 参数：
* @in hashp: 哈希表的控制结构。
* @in freelist_idx: 自由列表的索引，用于确定从哪个自由列表中获取元素。
* 返回值：HASHBUCKET - 新创建的哈希表元素，如果创建失败返回NULL。
*/
static HASHBUCKET get_hash_entry(HTAB* hashp, int freelist_idx)
{
HASHHDR* hctl = hashp->hctl; // 获取哈希表的控制结构
HASHBUCKET newElement; // 新的哈希表元素指针
int borrow_from_idx; // 用于在分区哈希表中从其他分区借用元素的自由列表索引
for (;;) {
// 如果使用分区哈希表，必须锁定以操作 nentries 和 freeList
if (IS_PARTITIONED(hctl)) {
SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);
}
// 尝试从自由列表中获取一个元素
newElement = hctl->freeList[freelist_idx].freeList;
if (newElement != NULL) {
break; // 成功获取元素，退出循环
}
// 如果使用分区哈希表，释放锁并尝试从其他分区借用元素
if (IS_PARTITIONED(hctl)) {
SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
}
// 自由列表中没有空闲元素，分配一个新的元素块
if (!element_alloc(hashp, hctl->nelem_alloc, freelist_idx)) {
if (!IS_PARTITIONED(hctl)) {
return NULL; // 内存不足，返回NULL
}
// 尝试从其他分区借用元素
borrow_from_idx = freelist_idx;
for (;;) {
borrow_from_idx = (borrow_from_idx + 1) % NUM_FREELISTS;
// 尝试获取其他分区的元素
SpinLockAcquire(&(hctl->freeList[borrow_from_idx].mutex));
newElement = hctl->freeList[borrow_from_idx].freeList;
if (newElement != NULL) {
// 成功从其他分区获取元素，更新自由列表和 nentries
hctl->freeList[borrow_from_idx].freeList = newElement->link;
SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));
SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);
hctl->freeList[freelist_idx].nentries++;
SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
break; // 成功获取元素，退出循环
}
SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));
}
return newElement;
}
}
// 从自由列表中移除元素，增加 nentries
hctl->freeList[freelist_idx].freeList = newElement->link;
hctl->freeList[freelist_idx].nentries++;
// 如果使用分区哈希表，释放锁
if (IS_PARTITIONED(hctl)) {
SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
}
return newElement; // 返回新创建的哈希表元素指针
}