我会使用五个并行的哈希表，对应于可能搜索的五个前缀。每个哈希表槽位将包含零个或多个引用，每个引用都包含该特定键值对的前缀长度、该键前缀的哈希以及指向实际键和数据结构的指针。
对于删除操作，实际的键和数据结构将包含所有五个前缀长度和相应的哈希，以及键和值的字符数据。
例如：
#define PARTS 5
struct hashitem {
size_t hash[PARTS];
size_t hlen[PARTS];
char *data;
char key[];
};
struct hashref {
size_t hash;
size_t hlen;
struct hashitem *item;
};
struct hashrefs {
size_t size;
size_t used;
struct hashref ref[];
};
struct hashtable {
size_t size[PARTS];
struct hashrefs **slot[PARTS];
};
在一个
struct hashitem中，如果
key是
k1k2k3k4k5，那么
hlen[0]=2，
hash[0]=hash("k1")，
hlen[1]=4，
hash[1]=hash("k1k2")，以此类推，直到
hlen[4]=10，
hash[4]=hash("k1k2k3k4k5")。
插入新的键值对时，首先要找出前缀长度(
hlen[])及其对应的哈希值(
hash[])，然后调用一个类似于辅助函数的函数。
static int insert_pair(struct hashtable *ht,
const char *key,
const size_t hash[PARTS],
const size_t hlen[PARTS],
const char *data,
const size_t datalen)
else
if (ht->entry[i].used >= ht->entry[i].size)
ht->entry[i].ref[ht->entry[i].used].hash = hash[p];
ht->entry[i].ref[ht->entry[i].used].hlen = plen[p];
ht->entry[i].ref[ht->entry[i].used].item = item;
ht->entry[i].used++;
}
return 0; /* Success, no errors */
}
前缀查找与使用完整键的哈希表查找相同：
int lookup_filter(struct hashtable *ht,
const size_t hash,
const size_t hashlen,
const size_t parts,
const char *key,
int (*func)(struct hashitem *, void *),
void *custom)
{
const struct hashrefs *refs = ht->entry[parts][hash % ht->size[parts]];
int retval = -1;
size_t i;
if (!refs)
return retval;
for (i = 0; i < refs->used; i++)
if (refs->ref[i].hash == hash &&
refs->ref[i].hlen == hashlen &&
!strncmp(refs->ref[i].item->key, key, hashlen)) {
if (func) {
retval = func(refs->ref[i].item, custom);
if (retval)
return retval;
} else
retval = 0;
}
return retval;
}
请注意所使用的回调函数风格，以允许单个查找匹配所有前缀。假设键是唯一的，则完全键匹配会稍微简单一些：
struct hashitem *lookup(struct hashtable *ht,
const size_t hash,
const size_t hashlen,
const char *key)
{
const struct hashrefs *refs = ht->entry[PARTS-1][hash % ht->size[PARTS-1]];
size_t i;
if (!refs)
return NULL;
for (i = 0; i < refs->used; i++)
if (refs->ref[i].hash == hash &&
refs->ref[i].hlen == hashlen &&
!strncmp(refs->ref[i].item->key, key, hashlen))
return refs->ref[i].item;
return NULL;
}
删除将利用查找，但匹配项可以通过将匹配条目替换为同一引用数组中的最终项来删除；或者如果该项是引用数组中唯一的项，则完全释放整个数组。
使用引用数组（每个哈希表条目多个数据项）的原因是可接受的，因为当前处理器以块缓存数据（cacheline是最小的缓存块）。因为每个哈希表槽包含一个或多个匹配项，具有代码的完整哈希和哈希长度，实际冲突需要逐字节比较才能确定实际匹配的情况极为罕见，即使是快速简单的哈希函数也是如此。（我预计每个匹配项会有1.05到1.10个字符串比较，即使使用像DJB2哈希这样简单的东西。）
换句话说，这种方法试图最小化访问以找到所需的一对或多对的缓存行数。
由于初始部分将具有大量重复的哈希（相对较少的唯一前缀哈希）和哈希长度，因此将它们的哈希表变小可能更有效率。（引用数组将更大。）因为哈希和哈希长度不会改变，所以可以在任何时候调整任何哈希表的大小，而无需重新计算任何哈希。
请注意，除了
PARTS-1哈希表之外的所有哈希表都用于扫描项目集，因此它们的引用数组可能会变得非常长，并不是一件坏事：这些数组几乎完全包含了人们正在查找的项目！（换句话说，如果一个引用数组增长到比如说10,000个条目长，如果它被用来查找所需的大约9,750个条目，那么这并不是一个问题。）
我个人也考虑过某种类型的表格，例如每个关键部分都是表格中的一个附加级别。然而，查找具有给定前缀的条目集涉及到表格遍历和相当分散的内存访问。我相信，但尚未通过微基准测试比较这两种方法，具有潜在大型引用数组的哈希表在运行时更有效率。
