哈希表的C++实现

客官°小女子只卖身不卖艺 2022-08-04 12:35 123阅读 0赞

哈希表的几个概念：

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

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

处理冲突的几个方法：

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"

Cpp代码

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

测试函数"main.cpp"

Cpp代码

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

测试结果：

Cpp代码

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. 
15. 输入要查找的记录的关键字：5 
16. 元素的关键字值和它的标志分别是：5 9 
17. \_\_\_\_重建hash表\_\_\_\_\_ 
18. 插入失败 
19. 需要重建哈希表才可以插入 
20. \_\_\_\_重建哈希表\_\_\_\_ 
21. 遍历重建后的哈希表 
22. 哈希地址0->18 
23. 元素的关键字值和它的标志分别是：38 4 
24. 元素的关键字值和它的标志分别是：1 5 
25. 元素的关键字值和它的标志分别是：2 6 
26. 元素的关键字值和它的标志分别是：3 7 
27. 元素的关键字值和它的标志分别是：4 8 
28. 元素的关键字值和它的标志分别是：5 9 
29. 元素的关键字值和它的标志分别是：60 2 
30. 元素的关键字值和它的标志分别是：6 10 
31. 元素的关键字值和它的标志分别是：7 11 
32. 元素的关键字值和它的标志分别是：8 12 
33. 元素的关键字值和它的标志分别是：29 3 
34. 元素的关键字值和它的标志分别是：17 1 
35. 
36. 输入要查找的记录的关键字：7 
37. 元素的关键字值和它的标志分别是：7 11 
38. \_\_\_\_销毁哈希表\_\_\_\_ 
39. Press any key to **continue**