8.4散列表查找

散列存储中使用的函数H(key)称为散列函数或哈希函数，它实现关键字到存储地址的映射（或称转换）。

删除、插入都很不方便

查找最方便O(1)

C++实现散列表查找

 1 #include "Hash.h"
 2 #include "Hashnode.h"
 3 
 4 template<class T>
 5 int Hash<T>::myhash(int key)//求余
 6 {
 7     return key%n;
 8 }
 9 
10 template<class T>
11 void Hash<T>::init(T *pt, int nt)//初始化
12 {
13     for (int i = 0; i < 10; i++)
14     {
15         p[i].key = i;
16         p[i].t = pt[i];
17         p[i].cn = 0;
18     }
19 }
20 
21 template<class T>
22 bool Hash<T>::isin(int key, T t)//是否存在
23 {
24     int res = myhash(key);
25     if (p[res].t == t)
26     {
27         return true;
28     }
29     else
30     {
31         return false;
32     }
33 }
34 
35 template<class T>
36 Hashnode<T> *Hash<T>::find(int key)//查找
37 {
38     int res = myhash(key);
39     return p + res;
40 }
41 
42 template<class T>
43 Hash<T>::Hash()//构造函数
44 {
45     this->n = 10;
46     this->p = new Hashnode<T>[this->n];
47 }
48 
49 template<class T>
50 Hash<T>::~Hash()//析构函数
51 {
52     delete[]p;
53 }