哈希树

缘起

哈希树缘起于如下质数分辨定理

1
2
质数分辨定理：n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能
有完全相同的余数序列。

分析

哈希树的结构如下图所示

下图表示顺次插入

7807、249、1073、658、930、2272、8544、1878、8923、8709 产生的哈希树.

从上图就不难写出哈希树算法（和trie很相似，可以说几乎和trie一样——几乎常数时间定位一个元素）

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include "stdafx.h"
#include <stdio.h>
#include <string.h>

int a[]={7807,249,1073,1878, 658,930,2272,7807, 8544,1878,8923,8709, 249};

const int MAX_N = 10005,SIZE = 29, PRIMES[SIZE]={2,3,5,7,11,13,17,19,23,29}; // 采用分辨的质数数组

typedef struct HTNode
{
	int val;
	bool occupy; // 是否被占用(因为哈希树打算采用懒惰删除)
	HTNode *next[SIZE];
	HTNode(){occupy = true;memset(next, 0, sizeof(next));val = -1;}
	
}HTNode, *HTree;

HTNode nodes[MAX_N]; // 这里使用数组替代指针new, 提高速度
HTree root = nodes;
int nodescount; // 节点个数

HTNode *insert(int x) // 往本节点插入x,返回0表示不存在, 否则返回指向节点的指针
{
	HTNode *p = root; // 下探指针
	for (int i = 0,r; i<SIZE; i++) // 开始使用SIZE个质数分辨这个x
	{
		r = x%PRIMES[i];
		if (!p->next[r])
		{
			p->next[r] = &nodes[++nodescount];
			p->next[r]->val = x;
			return 0; // 没找到
		}
		p = p->next[r];
		if (p->val == x && p->occupy) return p; // 找到了(而且没有被惰性删除)
	}
	return 0; // 其实只要不超过这SIZE个质数的乘积, 都不会走到这里
}

HTNode *del(int x) // 惰性删除x(其实只有root会调用这个方法), 一旦惰性删除, 此节点就再也不用了(不然的话, 如果还用, 则设想x和y 模掉前几个质数余数相同,但是x先加入， 然后惰性删除x, 然后再加入y 就可以加入到x的位置了,我们希望整棵哈希树没有重复元素)
{
	HTNode *p = root; // 下探指针
	for (int i = 0,r; i<SIZE; i++)
	{
		r = x%PRIMES[i];
		if (!p->next[r]) return 0; // 已经无路可走, 则没找到
		if (p->next[r]->val == x && p->next[r]->occupy) // 如果存在并且尚未被惰性删除
		{
			p->next[r]->occupy = false; // 惰性删除
			return p->next[r];
		}
		p = p->next[r];
	}
	return 0; // 没发现, 就返回0
}

int main()
{
	for (int i = 0; i<sizeof(a)/sizeof(int); i++)
	{
		if (insert(a[i]))
		{
			printf("元素 a[%d]=%d 已存在, 插入失败!\n", i, a[i]);
		}
	}
	for (int i = 0; i<sizeof(a)/sizeof(int); i++)
	{
		if (i==7)
		{
			puts("");
		}
		if (!del(a[i]))
		{
			printf("元素 a[%d]=%d 不存在, 删除失败!\n", i, a[i]);
		}
	}
	return 0;
}

不过很遗憾——没找到oj题目可以提交的.