- 论坛徽章:
- 0
|
线段Hash算法
线段Hash算法原理是：通过Hash算法把Key转换成一个int类型的数字，然后按照每次比较2个bit来定位到一个内存块。结构图如图1-1：
图1-1
图1-1中的每个节点成为bucket，而每个bucket有4个元素。我们可以使用以下结构体定义：
struct bucket {
int elems[4];
};
因为每个元素可能指向下一个节点或者一个数据块，所以我们必须有个标志指定元素指向的是下一个节点还是数据块。那么，我们把bucket的定义修改成：
struct bucket {
unsigned char flags[4];
int elems[4];
};
如果flags是1表示指向的是数据块，如果是-1表示指向的是下一个节点，0就表示指向NULL。
因为2个bit可以确定4个位置，所以第一层比较Hash值的最后两个bit，可以使用以下方式访问：
hvl = hash(key);
pos = hvl & 3;
那么第二层就是比较3、4位bit，所以可以使用以下方式取得：
hvl = hash(key);
pos = (hvl >> 2) & 3;
第三、四、五…层以此类推。
我们可以总结成一个公式：
int getPosition(int hvl, int level)
{
return (hvl >> (level – 1) * 2) & 3;
}
1. 搜索算法：
有了以上的数据结构，那么搜索算法是很简单的。首先根据Key来计算出Hash值，然后把根节点作为第一层向下搜索，直到找到一个元素的flags值为1（找到）或者0（找不到）的元素，搜索结束。算法如下：
void *SegmentHash_Find(SegmetHash *ht, char *key) {
int hvl = hash(key);
int level = 1;
HashNode *node = ht->root;
while (true)
{
int pos = getPosition(hvl, level);
if (node->flags[pos] == 1) {
return node->elems[pos];
} else if (node->flags[pos] == 0) {
return NULL;
} else {
node = node->elems[pos];
level++;
}
}
}
2. 插入算法：
插入算法与搜索算法类似，首先使用搜索算法定位到其中一个层的一个元素，然后比较此元素的flags值是否为NULL，如果是NULL就直接新建一个数据块，让此元素指向此数据块。如果flags值是1，表示此位置已经有数据，那么我们就新建一个层，把旧数据和新数据插入到这个新层中，如果继续碰撞，就继续新建层，直到不碰撞为止。插入完成后，我们需要修改flags的值。
3. 删除算法：
找到要删除的记录，然后直接把flags设置为0即可。如果整个bucket的flags都是0，那么我们可以把这个bucket删除。然后设置上一级的flags值为0。并递归此操作，直到到达根节点为止。
解决冲突：
原理上看，int可以保存4394967295个元素，所以基本不会发生两个Hash值一样的Key。不过随着数据增多，Hash值有可能会一样，那么我们怎么处理呢？
我们可以设置一个溢出区，如果到最后一层也有数据，那么我们就可以把新数据保存到溢出区中。搜索的时候，如果到最后一层也不是我们要找的数据，那么就在溢出区中找。如果还是找不到，就说明此数据不存在。溢出区可以使用链表或者数组来保存。
效率：
因为每层使用2个bit来定位，所以32bit的int最多只需要16次的搜索。所以效率比平衡二叉树要快（最多搜索32次）。另外普通的HashTable算法原理时间复杂度是O(1)，不过由于不能保证冲突链的长度，所以线段Hash算法更稳定。 |
|
免费注册
发表于 2011-08-30 21:08
