Hash表操作
# Memcached源码阅读十 Hash表操作
Memcached
的Hash表用来提高数据访问性能,通过链接法来解决Hash冲突,当Hash表中数据多余Hash表容量的1.5倍时,Hash表就会扩容,Memcached的Hash表操作没什么特别的,我们这里简单介绍下Memcached里面的Hash表操作。
//hash表插入元素
int assoc_insert(item *it, const uint32_t hv) {
unsigned int oldbucket;
//如果已经开始扩容,且扩容的桶编号大于目前的item所在桶的编号
if (expanding &&
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
{
//这里是类似单链表的,按单链表的操作进行插入
it->h_next = old_hashtable[oldbucket];
old_hashtable[oldbucket] = it;
} else {
//已经扩容,则按新的Hash规则进行路由
it->h_next = primary_hashtable[hv & hashmask(hashpower)];
//这里在新的Hash表中执行单链表插入
primary_hashtable[hv & hashmask(hashpower)] = it;
}
hash_items++;//元素个数+1
if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
//开始扩容
assoc_start_expand();//唤醒扩容条件变量
}
MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey, hash_items);
return 1;
}
//hash表删除元素
void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
item **before = _hashitem_before(key, nkey, hv);
//获得item对应的桶的前一个元素
if (*before) {
item *nxt;
hash_items--;//元素个数-1
MEMCACHED_ASSOC_DELETE(key, nkey, hash_items);
nxt = (*before)->h_next;//执行单链表的删除操作
(*before)->h_next = 0;
*before = nxt;
return;
}
assert(*before != 0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
像Hash表的扩容,初始化等已经在其他博客中介绍过了,这里就不在阐述。
编辑 (opens new window)
上次更新: 2023/12/11, 22:32:09