哈希树的理论基础
【 质数分辨定理 】 简单地说就是： n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等 。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。 （这个定理的证明详见： http://wenku.baidu.com/view/16b2c7abd1f34693daef3e58.html ） 例如： 从2起的连续质数，连续10个质数就可以分辨大约M(10) =2*3*5*7*11*13*17*19*23*29= 6464693230 个数，已经超过计算机中常用整数（32bit）的表达范围。连续100个质数就可以分辨大约M(100) = 4.711930 乘以10的219次方。 而按照目前的CPU水平，100次取余的整数除法操作几乎不算什么难事。在实际应用中，整体的操作速度往往取决于节点将关键字装载内存的次数和时间。一般来说，装载的时间是由关键字的大小和硬件来决定的；在相同类型关键字和相同硬件条件下，实际的整体操作时间就主要取决于装载的次数。他们之间是一个成正比的关系。 我们选择质数分辨算法来建立一棵哈希树。 选择从2开始的连续质数来建立一个十层的哈希树。第一层结点为根结点，根结点下有2个结点；第二层的每个结点下有3个结点；依此类推，即每层结点的子节点数目为连续的质数。到第十层，每个结点下有29个结点。如下图所示： 同一结点中的子结点，从左到右代表不同的余数结果。 例如：第二层结点下有三个子节点。那么从左到右分别代表：除3余0，除3余1，除3余2. 对质数进行取余操作得到的余数决定了处理的路径。 结点：结点的关键字(在整个树中是唯一的)，结点的数据对象，结点是否被占据的标志位(标志位为真时，关键字才被认为是有效的)，和结点的子结点数组。 特点： 1.哈希树的结构是动态的，也不像某些哈希算法那样需要长时间的初始化过程，只需要初始化根结点就可以开始工作。哈希树也没 有必要为不存在的关键字提前分配空间。 2.查找迅速，最多只需要10次取余和比较操作，就可知道这个对象是否存在。哈希树的查找次数和元素个数没有关系。 3.结构不变，哈希树在删除的时候并不做任何结构调整。这也是它的一个非常好的优点。常规树结构在增加元素和删除元素的时候都要做一定的结构调整。 4.非排序性，哈希树不支持排序，没有顺序特性。 需要注意的是：哈希树是一个单向增加的结构，即随着所需要存储的数据量增加而增大。即使数据量减少到原来的数量，但是哈希树的总结点树不会减少。这样做的目的是为了避免结构的调整带来的额外消耗。
代码：
[cpp] view plain copy // HashTree.cpp : 定义控制台应用程序的入口点。 //选择质数分辨算法构造一棵哈希树 #include "stdafx.h" #include <iostream> using namespace std; const int SIZE = 32;//第10个质数为29，余数不可能大于32，所以数组的固定长度设置为32 const int Prime[10] = {2,3,5,7,11,13,17,19,23,29}; //哈希结点类型 template<class T1, class T2> class HashNode { public: HashNode();//默认构造函数 HashNode(T1 key, T2 value);//一般构造函数 ~HashNode(); public: T1 m_key; //结点的关键字 T2 m_value; //结点的数据对象 bool occupied; //结点是否被占据，如果是表示结点的关键字有效 HashNode *child[SIZE]; //结点的子结点数组 }; template<class T1, class T2> HashNode<T1,T2>::HashNode() { occupied=false; memset(child, NULL, SIZE*sizeof(HashNode<T1,T2>*)); } template<class T1, class T2> HashNode<T1,T2>::HashNode(T1 key, T2 value) { this->m_key = key; this->m_value = value; occupied=false; memset(child, NULL, SIZE*sizeof(HashNode<T1,T2>*)); } template<class T1, class T2> HashNode<T1,T2>::~HashNode() { } //哈希树类型 template<class T1, class T2> class HashTree { public: HashTree(); ~HashTree(); void InsertNode(T1 key, T2 value); bool FindNode(T1 key, T2 &value); void DeleteNode(T1 key); private: HashNode<T1,T2> *root; void Insert(HashNode<T1,T2> *hashNode, int level, T1 key, T2 value);//插入结点 bool Find(HashNode<T1,T2> *hashNode, int level, T1 key, T2 value);//查找 void Delete(HashNode<T1,T2> *hashNode, int level,T1 key);//删除结点 }; template<class T1, class T2> HashTree<T1,T2>::HashTree() { root = new HashNode<T1,T2>; } template<class T1, class T2> HashTree<T1,T2>::~HashTree() { } template<class T1, class T2> void HashTree<T1,T2>::InsertNode(T1 key, T2 value) { Insert(root,0,key,value); } template<class T1, class T2> void HashTree<T1,T2>::Insert(HashNode<T1, T2> *hashNode, int level, T1 key, T2 value)//插入结点 { if(hashNode->occupied == false) { hashNode->m_key = key; hashNode->m_value = value; hashNode->occupied = true; return; } int index = key%Prime[level]; if (hashNode->child[index] == NULL) { hashNode->child[index] = new HashNode<T1,T2>; } level += 1; Insert(hashNode->child[index], level, key, value); } template<class T1, class T2> bool HashTree<T1,T2>::FindNode(T1 key, T2 &value) { return Find(root, 0, key, value); } template<class T1, class T2> bool HashTree<T1,T2>::Find(HashNode<T1,T2> *hashNode, int level, T1 key, T2 value)//查找 { if (hashNode->occupied == true) { if (hashNode->m_key == key) { value = hashNode->m_value; return true; } } int index = key%Prime[level]; if (hashNode->child[index] == NULL) { return false; } level += 1; return Find(hashNode->child[index], level, key, value); } template<class T1, class T2> void HashTree<T1,T2>::DeleteNode(T1 key) { Delete(root, 0, key); } template<class T1, class T2> void HashTree<T1,T2>::Delete(HashNode<T1,T2> *hashNode, int level, T1 key)//删除结点 { if (hashNode->occupied == true) { if (hashNode->m_key == key) { hashNode->occupied = false; cout << "关键字为" << key << "结点已被删除！" << endl; return; } } int index = key%Prime[level]; if (hashNode->child[index] == NULL) { cout << "该关键字不存在！" << endl; return; } level += 1; Delete(hashNode->child[index], level, key); } int _tmain(int argc, _TCHAR* argv[]) { HashTree<int, int> ht; ht.InsertNode(1, 8); ht.InsertNode(2, 0); ht.InsertNode(3, 4); ht.InsertNode(4, 7); ht.InsertNode(5, 4); ht.InsertNode(6, 3); ht.InsertNode(7, 8); int nvalue = 0; cout << ht.FindNode(5,nvalue) << endl; cout << ht.FindNode(9,nvalue) << endl; ht.DeleteNode(4); ht.DeleteNode(10); cout<<"baasdfas"<<endl; system("pause"); return 0; }
