本文介绍在共享内存中自建hash的一种方法。
下图所示的共享内存有一个writer和多个reader,为了提高数据存取效率,共享内存中的数据需要按hash组织。
注:本文不讨论writer和和reader之间的同步问题,具体可由信号量、文件锁等方式实现。
初步想法是将整块共享内存划分成一个下标为0~n的数组,如下图所示。数据Record的key经过Hash计算后得到hashcode,然后将该值映射为数组的下标,直接通过下标访问数组,将Record的key和value存储在对应的位置。
但是Hash存在冲突的情况,即两个不同的Record经过Hash映射,得到的下标可能是相同的。
为了处理这种情况,需要将共享内存分区,一部分作为常规的Hash索引区,另一部分作为冲突预留区,用来保存hash冲突的Record。如下图所示,具体比例可以根据业务的数据情况调整,如果冲突较多就保留较大的预留区,否则预留区可以小一点,比如按1:1划分或者2:1划分。
注:冲突较多的时候,可以考虑换hash函数。
数据写入流程如下:
最终建立了下图所示的链接关系:
说明:
从上面的介绍可以看出,其实最终整个数组被划分成了下图所示几个链表:
数据读取过程:把key做hash映射,得到对应的数组下标,也就知道了该在哪个链表中找数据,依次遍历对应的链表,比较key是否一致,如果一致就找到了对应的记录。
数据删除过程: