哈希表实现（c/C++) |
您所在的位置：网站首页 › 哈希表的实现与简单应用课程设计 › 哈希表实现（c/C++) |
哈希表实现（c/C++)
|
哈希表的基本概念
哈希表也叫散列表，哈希表是一种数据结构，它提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1) 哈希表的核心在于使用哈希函数对数据进行特征化，再通过特征值对数据进行分类存储，求特征值的函数被称为哈希函数。 哈希函数 定义哈希函数不是一个特定的函数，哈希函数来自于自定义，不同的哈希函数对同一组数据进行处理将会得出不同的结果。 如下是一种常用的哈希函数 int hashfx(int num) //这里直接用和10取余数作为哈希函数(这个哈希函数仅限在int型数据类型时成立，其余数据类型可以考虑截断或者ASCII码） { return num % 10; } 哈希冲突基于上述的函数我们将会发现 2，12，22，32，42.等数在哈希函数处理下得到的特征值是完全相同的，这样的情况被称为哈希冲突。对于哈希冲突的处理方式是多样的，主要从两个角度对这个问题进行处理 选取新的哈希函数，但是这种方法可以减少哈希冲突但是不能完全避免 寻找合适的存储方式存储哈希冲突的数据 哈希表的存储PS：所有的构造都是基于上述的哈希函数 链式存储使用链表的方式构建哈希表 链表的方式对空间的操作更加灵活但是在数据量确定的情况下所需的空间更大，遍历操作的时间更长。 
出现哈希冲突直接在链表后续插入即可。 hashmap* Createhash_1() //这里使用了一个指针数组，即指向hashmap数据类型的指针，即指向指针的指针 { hashmap* p = (hashmap*)malloc(sizeof(hashmap) * 10); //这个二级指针实际上是指向存储空间的首位。 for (int i = 0; i < 10; i++) { p[i] = NULL; //指针加中括号 a[i]相当于*(a+i) } return p; } 线性存储结构线性存储结构在于使用线性表存储相应的数据。 typedef struct Hash { type* Hashmap; //指向哈希表存储的基址 int* Every; //用于存储每一个函数值对应的数据的数量（哈希冲突） int count; //哈希表中数据的总数 int Listsize; }*hashmap; 哈希表的构建 链式实际在创建链表存储结构的同时已经完成了哈希表的构建 线性 void hashInit(hashmap hash) { hash->Hashmap = (int*)malloc(sizeof(type) * MAXSIZE); //为哈希表的存储分配初始空间 hash->Every = (int*)malloc(sizeof(int) * 10); //分配每一个结点的存储空间,并初始化为0 for (int i = 0; i < 10; i++) { hash->Every[i] = 0; } hash->count = 0; hash->Listsize = MAXSIZE; } 向哈希表中插入数据 链式 void insert(hashmap* p) { cout n; if (n == 0) { middle->people = MAN; } else { middle->people = WOMAN; } cin.get(); //丢弃数据中的分隔字符 check = middle->old % 10; //开始插入哈希表中 if (p[check] == NULL) { p[check] = (hashmap)malloc(sizeof(hashd)); p[check]->next = NULL; p[check]->a = *middle; } else { hashmap H; H = p[check]; while (H->next != NULL) { H = H->next; } H->next= (hashmap)malloc(sizeof(hashd)); H = H->next; H->a = *middle; H->next = NULL; } } while (count>=0); } 线性在线性存储时需要考虑数据是否超限 void hashInsert(hashmap hash) //向哈希表中插入数据 { type node; std::cin >> node; int mid; int count_2 = 0; if (node == '#') //使用#作为终止结点 { do { mid = hashfx(node); for (int i = 0; i < mid; i++) { count_2 += hash->Every[i]; } hash->count += 1; if (hash->count >= MAXSIZE) //如果出现空间超限就扩展空间 { hash->Hashmap = (int*)realloc(hash->Hashmap, sizeof(type) * (hash->Listsize + INCREANT)); //注意只能使用malloc才能在后续任意拓展空间 hash->Listsize += INCREANT; } for (int i = hash->count - 1; i >= count_2; i--) //将插入位置的移出（对哈希冲突的处理） { hash->Hashmap[i] = hash->Hashmap[i - 1]; } hash->Hashmap[count_2] = node; std::cin >> node; } while (node != '#'); } } 哈希表的查找实际上就是通过哈希函数来减小查找次数 以链表为例 bool searchhash(stu b, hashmap* p, int n) //从哈希表中查找数据(注意自定义的指针要限制防止越界）(即查询数据是否存在（GTA5黑历史）） { int check; check = b.old % 10; hashmap middle=NULL; if (check < n) { middle = p[check]; } int CK = 0; while (middle->next != NULL) { if (middle->a.old == b.old) { if (middle->a.people == b.people) { int i = 0; while (middle->a.name[i] != '#') { if (middle->a.name[i] != b.name[i]) { break; } i += 1; } } } } if (middle->a.old == b.old) { if (middle->a.people == b.people) { int i = 0; while (middle->a.name[i] != '#') { if (middle->a.name[i] != b.name[i]) { break; } i += 1; } } cout old % 10; //开始插入哈希表中 if (p[check] == NULL) { p[check] = (hashmap)malloc(sizeof(hashd)); p[check]->next = NULL; p[check]->a = *middle; } else { hashmap H; H = p[check]; while (H->next != NULL) { H = H->next; } H->next= (hashmap)malloc(sizeof(hashd)); H = H->next; H->a = *middle; H->next = NULL; } } while (count>=0); } bool searchhash(stu b, hashmap* p, int n) //从哈希表中查找数据(注意自定义的指针要限制防止越界）(即查询数据是否存在（GTA5黑历史）） { int check; check = b.old % 10; hashmap middle=NULL; if (check < n) { middle = p[check]; } int CK = 0; while (middle->next != NULL) { if (middle->a.old == b.old) { if (middle->a.people == b.people) { int i = 0; while (middle->a.name[i] != '#') { if (middle->a.name[i] != b.name[i]) { break; } i += 1; } } } } if (middle->a.old == b.old) { if (middle->a.people == b.people) { int i = 0; while (middle->a.name[i] != '#') { if (middle->a.name[i] != b.name[i]) { break; } i += 1; } } cout Listsize = MAXSIZE; } void hashInsert(hashmap hash) //向哈希表中插入数据 { type node; std::cin >> node; int mid; int count_2 = 0; if (node == '#') //使用#作为终止结点 { do { mid = hashfx(node); for (int i = 0; i < mid; i++) { count_2 += hash->Every[i]; } hash->count += 1; if (hash->count >= MAXSIZE) //如果出现空间超限就扩展空间 { hash->Hashmap = (int*)realloc(hash->Hashmap, sizeof(type) * (hash->Listsize + INCREANT)); //注意只能使用malloc才能在后续任意拓展空间 hash->Listsize += INCREANT; } for (int i = hash->count - 1; i >= count_2; i--) //将插入位置的移出（对哈希冲突的处理） { hash->Hashmap[i] = hash->Hashmap[i - 1]; } hash->Hashmap[count_2] = node; std::cin >> node; } while (node != '#'); } } bool hashfind(hashmap hash, type n) { int mid; int count0 = 0; int check = 0; mid = hashfx(n); for (int i = 0; i < mid; i++) { count0 += hash->Every[i]; } for (int i = count0; i Every[mid]; i++) { if (hash->Hashmap[i] == n) { check += 1; break; } } if (check > 0) { return true; } else { return false; } } int main() { } |
【本文地址】