Hash树

2023-11-20 16:52:28

我们选择质数分辨算法来建立一棵哈希树。
选择从2开始的连续质数来建立一个十层的哈希树。第一层结点为根结点，根结点下有2个结点；第二层的每个结点下有3个结点；依此类推，即每层结点的子节点数目为连续的质数。到第十层，每个结点下有29个结点。如下图所示：
Hash树


同一结点中的子结点，从左到右代表不同的余数结果。
例如：第二层结点下有三个子节点。那么从左到右分别代表：除3余0，除3余1，除3余2.
对质数进行取余操作得到的余数决定了处理的路径。
结点：结点的关键字(在整个树中是唯一的)，结点的数据对象，结点是否被占据的标志位(标志位为真时，关键字才被认为是有效的)，和结点的子结点数组。
  
特点：
1.哈希树的结构是动态的，也不像某些哈希算法那样需要长时间的初始化过程，只需要初始化根结点就可以开始工作。哈希树也没 有必要为不存在的关键字提前分配空间。
2.查找迅速，最多只需要10次取余和比较操作，就可知道这个对象是否存在。哈希树的查找次数和元素个数没有关系。
3.结构不变，哈希树在删除的时候并不做任何结构调整。这也是它的一个非常好的优点。常规树结构在增加元素和删除元素的时候都要做一定的结构调整。
4.非排序性，哈希树不支持排序，没有顺序特性。
需要注意的是：哈希树是一个单向增加的结构，即随着所需要存储的数据量增加而增大。即使数据量减少到原来的数量，但是哈希树的总结点树不会减少。这样做的目的是为了避免结构的调整带来的额外消耗。

代码：

[cpp] view plaincopy
  1. // HashTree.cpp : 定义控制台应用程序的入口点。  
  2. //选择质数分辨算法构造一棵哈希树  
  3. #include "stdafx.h"  
  4. #include <iostream>  
  5. using namespace std;  
  6.   
  7. const int SIZE = 32;//第10个质数为29，余数不可能大于32，所以数组的固定长度设置为32  
  8. const int Prime[10] = {2,3,5,7,11,13,17,19,23,29};  
  9. //哈希结点类型  
  10. template<class T1, class T2>  
  11. class HashNode  
  12. {  
  13. public:   
  14.     HashNode();//默认构造函数  
  15.     HashNode(T1 key, T2 value);//一般构造函数  
  16.     ~HashNode();  
  17.   
  18. public:  
  19.     T1 m_key;  //结点的关键字  
  20.     T2 m_value; //结点的数据对象  
  21.     bool occupied; //结点是否被占据，如果是表示结点的关键字有效  
  22.     HashNode *child[SIZE];  //结点的子结点数组  
  23. };  
  24.   
  25. template<class T1, class T2>  
  26. HashNode<T1,T2>::HashNode()  
  27. {  
  28.     occupied=false;  
  29.     memset(child, NULL, SIZE*sizeof(HashNode<T1,T2>*));  
  30. }  
  31.   
  32. template<class T1, class T2>  
  33. HashNode<T1,T2>::HashNode(T1 key, T2 value)  
  34. {  
  35.     this->m_key = key;  
  36.     this->m_value = value;  
  37.     occupied=false;  
  38.     memset(child, NULL, SIZE*sizeof(HashNode<T1,T2>*));  
  39. }  
  40.   
  41. template<class T1, class T2>  
  42. HashNode<T1,T2>::~HashNode()  
  43. {  
  44.   
  45. }  
  46.   
  47. //哈希树类型  
  48. template<class T1, class T2>  
  49. class HashTree  
  50. {  
  51. public:  
  52.     HashTree();   
  53.     ~HashTree();  
  54.     void InsertNode(T1 key, T2 value);  
  55.     bool FindNode(T1 key, T2 &value);  
  56.     void DeleteNode(T1 key);  
  57.       
  58.       
  59. private:  
  60.     HashNode<T1,T2> *root;  
  61.     void Insert(HashNode<T1,T2> *hashNode, int level, T1 key, T2 value);//插入结点  
  62.     bool Find(HashNode<T1,T2> *hashNode, int level, T1 key, T2 value);//查找  
  63.     void Delete(HashNode<T1,T2> *hashNode, int level,T1 key);//删除结点  
  64. };  
  65.   
  66. template<class T1, class T2>  
  67. HashTree<T1,T2>::HashTree()  
  68. {  
  69.     root = new HashNode<T1,T2>;      
  70. }  
  71.   
  72. template<class T1, class T2>  
  73. HashTree<T1,T2>::~HashTree()  
  74. {  
  75.   
  76. }  
  77.   
  78. template<class T1, class T2>  
  79. void HashTree<T1,T2>::InsertNode(T1 key, T2 value)  
  80. {  
  81.     Insert(root,0,key,value);  
  82. }  
  83.   
  84. template<class T1, class T2>  
  85. void HashTree<T1,T2>::Insert(HashNode<T1, T2> *hashNode, int level, T1 key, T2 value)//插入结点  
  86. {  
  87.      if(hashNode->occupied == false)  
  88.      {  
  89.          hashNode->m_key = key;  
  90.          hashNode->m_value = value;  
  91.          hashNode->occupied = true;  
  92.          return;  
  93.      }  
  94.   
  95.      int index = key%Prime[level];  
  96.   
  97.      if (hashNode->child[index] == NULL)  
  98.      {  
  99.           hashNode->child[index] = new HashNode<T1,T2>;  
  100.      }  
  101.   
  102.      level += 1;  
  103.      Insert(hashNode->child[index], level, key, value);  
  104.   
  105. }  
  106.   
  107. template<class T1, class T2>  
  108. bool HashTree<T1,T2>::FindNode(T1 key, T2 &value)  
  109. {  
  110.      return Find(root, 0, key, value);  
  111. }  
  112.   
  113. template<class T1, class T2>  
  114. bool HashTree<T1,T2>::Find(HashNode<T1,T2> *hashNode, int level, T1 key, T2 value)//查找  
  115. {  
  116.      if (hashNode->occupied == true)  
  117.      {  
  118.          if (hashNode->m_key == key)  
  119.          {  
  120.              value = hashNode->m_value;  
  121.              return true;  
  122.          }  
  123.      }  
  124.   
  125.      int index = key%Prime[level];  
  126.      if (hashNode->child[index] == NULL)  
  127.      {  
  128.          return false;  
  129.      }  
  130.   
  131.      level += 1;  
  132.      return Find(hashNode->child[index], level, key, value);       
  133. }  
  134.   
  135. template<class T1, class T2>  
  136. void HashTree<T1,T2>::DeleteNode(T1 key)  
  137. {  
  138.     Delete(root, 0, key);  
  139. }  
  140.   
  141. template<class T1, class T2>  
  142. void HashTree<T1,T2>::Delete(HashNode<T1,T2> *hashNode, int level, T1 key)//删除结点  
  143. {  
  144.    if (hashNode->occupied == true)  
  145.    {  
  146.        if (hashNode->m_key == key)  
  147.        {  
  148.            hashNode->occupied = false;  
  149.            cout << "关键字为" << key << "结点已被删除！" << endl;  
  150.            return;  
  151.        }  
  152.    }  
  153.   
  154.    int index = key%Prime[level];  
  155.    if (hashNode->child[index] == NULL)  
  156.    {  
  157.        cout << "该关键字不存在！" << endl;  
  158.        return;  
  159.    }  
  160.   
  161.    level += 1;  
  162.    Delete(hashNode->child[index], level, key);  
  163. }  
  164.   
  165. int _tmain(int argc, _TCHAR* argv[])  
  166. {  
  167.     HashTree<int, int> ht;  
  168.     ht.InsertNode(1, 8);  
  169.     ht.InsertNode(2, 0);  
  170.     ht.InsertNode(3, 4);  
  171.     ht.InsertNode(4, 7);  
  172.     ht.InsertNode(5, 4);  
  173.     ht.InsertNode(6, 3);  
  174.     ht.InsertNode(7, 8);  
  175.   
  176.     int nvalue = 0;  
  177.     cout << ht.FindNode(5,nvalue) << endl;  
  178.     cout << ht.FindNode(9,nvalue) << endl;  
  179.       
  180.     ht.DeleteNode(4);  
  181.     ht.DeleteNode(10);  
  182.    
  183.     cout<<"baasdfas"<<endl;  
  184.     system("pause");  
  185.     return 0;  
  186. }  

Hash树

上一篇：android之location01


下一篇：完美解决android显示gif