4
Hash冲突链
source link: https://zhanggq.github.io/post/zgq-c-hash/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
写了一个Hash冲突链。
一、Hash冲突链解释
UPF单节点需要支持大量的用户，每个用户又会建立多条Pdu会话。所以需要一张Hash表用于保存各个用户的会话上下文。Hash索引为用户的SUPI+Dnn+Pdn Type。而Hash索引又存在冲突的可能，且又不可能无限扩展Hash表，所以使用了Hash冲突链，或者叫拉链法。
简单来说模型如下所示，创建一个链表并将其分为2部分，前面N个节点作为Hash表，后面K个节点作为冲突链使用。当Hash索引冲突后，从K中取出一个节点挂到冲突的节点下形成冲突链。
二、代码实现
Hash算法
一个简单的Hash算法，将用户的SUPI+Dnn+Pdn Type合成32位字符串，Hash出UINT16的Hash索引。
链表初始化
申请一块内存，做一个64K+200K的链表。前面64K作为Hash表使用，后面200K作为冲突链使用。
申请节点
申请节点时，先根据Hash出来的索引检查节点是否被占用。如果没被占用就直接使用，如果已经被占用，则从FreeList中取一个节点。
节点挂链
节点挂链时，如果是索引对应的节点，则将NextEntry置为全F即可。否则说明是Freelist中得到的节点，要挂到索引所在节点的冲突链的末尾。
节点新增
对上面两个接口封装一个create接口。
节点释放
节点释放时，要判断该节点是否在冲突链中，如果是冲突链中的，释放节点后要将其挂回Freelist并将冲突链重新排序。
冲突链查找
先根据Hash出来的索引找到入口节点，然后循环匹配该节点及其冲突链下的节点与请求的SUPI+Dnn+Pdn是否匹配。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK