哈希表的C++实现(转)

2023-01-18 09:09:48

哈希表的几个概念：

映像：由哈希函数得到的哈希表是一个映像。

冲突：如果两个关键字的哈希函数值相等，这种现象称为冲突。

处理冲突的几个方法：

1、开放地址法：用开放地址处理冲突就是当冲突发生时，形成一个地址序列，沿着这个序列逐个深测，直到找到一个“空”的开放地址，将发生冲突的关键字值存放到该地址中去。

例如：hash(i)=(hash(key)+d(i)) MOD m (i=1,2,3,......,k(k<m-1)) d为增量函数，d(i)=d1,d2,d3,...,dn-1

根据增量序列的取法不同，可以得到不同的开放地址处理冲突探测方法。

有线性探测法、二次方探测法、伪随机探测法。

2、链地址法：把所有关键字为同义词的记录存储在一个线性链表中，这个链表成为同义词链表，即把具有相同哈希地址的关键字值存放在同义链表中。

3、再哈希表：费时间的一种方法

下面是代码：

文件"myhash.h"

  1. #include<iostream>
  2. using namespace std;
  3. typedef int KeyType; //设关键字域为整形,需要修改类型时，只需修改这里就可以
  4. const int NULLKEY=0; //NULLKEY表示该位置无值
  5. int c=0; //用来统计冲突次数
  6. struct Elemtype //数据元素类型
  7. {
  8. KeyType key;
  9. int ord;
  10. };
  11. int hashsize[]={11,19,29,37,47}; //hash表容量递增表
  12. int Hash_length=0;//hash表表长
  13. class HashTable
  14. {
  15. private:
  16. Elemtype *elem; //数据元素数组,动态申请
  17. int count;// 当前数据元素个数
  18. int size; //决定hash表的容量为第几个,hashsize[size]为当前hash容量
  19. public:
  20. int Init_HashTable() //构造一个空hash表
  21. {
  22. int i;
  23. count=0;
  24. size=0; //初始化容量为hashsize[0]=11
  25. Hash_length=hashsize[0];
  26. elem=new Elemtype[Hash_length];
  27. if(!elem)
  28. {
  29. cout<<"内存申请失败"<<endl;
  30. exit(0);
  31. }
  32. for(i=0;i<Hash_length;i++)
  33. elem[i].key=NULLKEY;
  34. return 1;
  35. }
  36. void Destroy_HashTable()
  37. {
  38. delete[]elem;
  39. elem=NULL;
  40. count=0;
  41. size=0;
  42. }
  43. unsigned Hash(KeyType k) //hash函数的一种(取模法)
  44. {
  45. return k%Hash_length;
  46. }
  47. void Collision(int &p,int d) //解决冲突
  48. {
  49. p=(p+d)%Hash_length; //采用开放地址法里的线性探测
  50. }
  51. bool Search_Hash(KeyType k,int &p) //查找
  52. {
  53. //在开放地址hash表中查找关键字等于k的元素
  54. //若找到用p表示待查数据,查找不成功时，p指向的是可插入地址
  55. c=0;
  56. p=Hash(k); //求hash地址
  57. while(elem[p].key!=NULLKEY && elem[p].key!=k)
  58. {
  59. c++;
  60. if(c<Hash_length)
  61. Collision(p,c);
  62. else
  63. return 0; //表示查找不成功
  64. }
  65. if(elem[p].key==k)
  66. return 1;
  67. else
  68. return 0;
  69. }
  70. int Insert_Hash(Elemtype e) //插入
  71. {
  72. //在查找不成功的情况下将k插入到hash表中
  73. int p;
  74. if(Search_Hash(e.key,p))
  75. return -1; //表示该元素已在hash表中
  76. else if(c<hashsize[size]/2) //冲突次数未达到上限
  77. {
  78. //插入e
  79. elem[p]=e;
  80. count++;
  81. return 1;
  82. }
  83. else
  84. ReCreate_HashTable(); // 重建hash表
  85. return 0; //插入失败
  86. }
  87. void ReCreate_HashTable() //重建hash表
  88. {
  89. int i,count2=count;
  90. Elemtype *p,*elem2=new Elemtype[count];
  91. p=elem2;
  92. cout<<"____重建hash表_____"<<endl;
  93. for(i=0;i<Hash_length;i++) //将原有元素暂存到elem2中
  94. if(elem[i].key!=NULLKEY)
  95. *p++=*(elem+i);
  96. count=0;
  97. size++; //hash容量增大
  98. Hash_length=hashsize[size];
  99. p=new Elemtype[Hash_length];
  100. if(!p)
  101. {
  102. cout<<"空间申请失败"<<endl;
  103. exit(0);
  104. }
  105. elem=p;
  106. for(i=0;i<Hash_length;i++)
  107. elem[i].key=NULLKEY;
  108. for(p=elem2;p<elem2+count2;p++) //将原有元素放回新表
  109. Insert_Hash(*p);
  110. }
  111. void Traverse_HashTable()
  112. {
  113. cout<<"哈希地址0->"<<Hash_length-1<<endl;
  114. for(int i=0;i<Hash_length;i++)
  115. if(elem[i].key!=NULLKEY)
  116. cout<<"元素的关键字值和它的标志分别是："<<elem[i].key<<"  "<<elem[i].ord<<endl;
  117. }
  118. void Get_Data(int p)
  119. {
  120. cout<<"元素的关键字值和它的标志分别是："<<elem[p].key<<"  "<<elem[p].ord<<endl;
  121. }
  122. };

测试函数"main.cpp"

  1. #include"myhash.h"
  2. int main()
  3. {
  4. Elemtype r[12]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{5,9},{6,10},{7,11},{8,12}};
  5. HashTable H;
  6. int i,p,j;
  7. KeyType k;
  8. H.Init_HashTable();
  9. for(i=0;i<11;i++) //插入前11个记录
  10. {
  11. j=H.Insert_Hash(r[i]);
  12. if(j==-1)
  13. cout<<"表中已有关键字为"<<r[i].key<<"  "<<r[i].ord<<"的记录"<<endl;
  14. }
  15. cout<<"按哈希地址顺序遍历哈希表"<<endl;
  16. H.Traverse_HashTable();
  17. cout<<endl;
  18. cout<<"输入要查找的记录的关键字：";
  19. cin>>k;
  20. j=H.Search_Hash(k,p);
  21. if(j==1)
  22. H.Get_Data(p);
  23. else
  24. cout<<"无此记录"<<endl;
  25. j=H.Insert_Hash(r[11]); //插入最后一个元素
  26. if(j==0)
  27. {
  28. cout<<"插入失败"<<endl;
  29. cout<<"需要重建哈希表才可以插入"<<endl;
  30. cout<<"____重建哈希表____"<<endl;
  31. H.Insert_Hash(r[i]); //重建后重新插入
  32. }
  33. cout<<"遍历重建后的哈希表"<<endl;
  34. H.Traverse_HashTable();
  35. cout<<endl;
  36. cout<<"输入要查找的记录的关键字：";
  37. cin>>k;
  38. j=H.Search_Hash(k,p);
  39. if(j==1)
  40. H.Get_Data(p);
  41. else
  42. cout<<"该记录不存在"<<endl;
  43. cout<<"____销毁哈希表____"<<endl;
  44. H.Destroy_HashTable();
  45. return 0;
  46. }

测试结果：

  1. 按哈希地址顺序遍历哈希表
  2. 哈希地址0->10
  3. 元素的关键字值和它的标志分别是：5  9
  4. 元素的关键字值和它的标志分别是：1  5
  5. 元素的关键字值和它的标志分别是：2  6
  6. 元素的关键字值和它的标志分别是：3  7
  7. 元素的关键字值和它的标志分别是：4  8
  8. 元素的关键字值和它的标志分别是：60  2
  9. 元素的关键字值和它的标志分别是：17  1
  10. 元素的关键字值和它的标志分别是：29  3
  11. 元素的关键字值和它的标志分别是：38  4
  12. 元素的关键字值和它的标志分别是：6  10
  13. 元素的关键字值和它的标志分别是：7  11
  14. 输入要查找的记录的关键字：5
  15. 元素的关键字值和它的标志分别是：5  9
  16. ____重建hash表_____
  17. 插入失败
  18. 需要重建哈希表才可以插入
  19. ____重建哈希表____
  20. 遍历重建后的哈希表
  21. 哈希地址0->18
  22. 元素的关键字值和它的标志分别是：38  4
  23. 元素的关键字值和它的标志分别是：1  5
  24. 元素的关键字值和它的标志分别是：2  6
  25. 元素的关键字值和它的标志分别是：3  7
  26. 元素的关键字值和它的标志分别是：4  8
  27. 元素的关键字值和它的标志分别是：5  9
  28. 元素的关键字值和它的标志分别是：60  2
  29. 元素的关键字值和它的标志分别是：6  10
  30. 元素的关键字值和它的标志分别是：7  11
  31. 元素的关键字值和它的标志分别是：8  12
  32. 元素的关键字值和它的标志分别是：29  3
  33. 元素的关键字值和它的标志分别是：17  1
  34. 输入要查找的记录的关键字：7
  35. 元素的关键字值和它的标志分别是：7  11
  36. ____销毁哈希表____
  37. Press any key to continue
上一篇：padding下中英文左右两端对齐


下一篇：AutoLayout框架Masonry使用心得