数据结构（哈希函数）

#pragma once//之前已经学完的顺序表链表等 他们总是有一个共有的特征数据和其存储之间是没有任何关系的//现在的需求 让查找函数的时间复杂度达到O(1);//让数据和其存储位置之间产生某种函数映射关系 这就是哈希//6种哈希函数的构建方法//除留取余法//折叠法//平方取中法//数组分析法//直接定址法//随机数法 散列哈希//如果出现了哈希冲突 怎么解决//4个解决哈希冲突的方法 哈希冲突 不同的关键字却//开发地址法 存储位置f(关键字)// // 1 开发指针法// f1(key)(f(key)d1)MODm (d11,2,3,4,,.....)线性探测法// 二次探针法// 随机探测法//再散列函数法//公共区溢出法// 通过哈希函数的计算得到的哈希地址 先去与基本表来对比 如果等于 则成功 如果不等于 则对其溢出表进行顺序表查找// 使用场景 冲突的数据表很小时//链地址法//#define MAXSIZE 12typedef struct LA_Node{int date;struct LA_Node* next;}LA_Node;typedef struct LinkADDress{LA_Node LA_arr[MAXSIZE];}LinkAddress;//0 哈希函数调用int Get_HashAddress(int key);//1 初始化void Init_LA(LinkAddress* pla);//2 插入bool Insert_LA(LinkAddress* pla, int key);//3 查找LA_Node* search_LA(LinkAddress* pla, int key);//4 打印void Show(LinkAddress* pla);//5 删除bool Delete_LA(LinkAddress* p#define _CRT_SECURE_NO_WARNINGS#include stdio.h#include stdlib.h#include string.h#include assert.h#include memory.h#include Link_Address.h//0.计算哈希地址函数int Get_HashAddress(int key){return key % MAXSIZE;}//1.初始化void Init_LA(LinkAddress* pla){for (int i 0; i MAXSIZE; i){//pla-LA_arr[i].data;//数据域不使用 不用赋值pla-LA_arr[i].next NULL;//pla-LA_arr[i].nextNULL;}}//2.插入bool Insert_LA(LinkAddress* pla, int key){LA_Node* p Search_LA(pla, key);if (p ! NULL){return true;}int index Get_HashAddress(key);LA_Node* pnewnode (LA_Node*)malloc(sizeof(LA_Node));if (pnewnode NULL)exit(EXIT_FAILURE);pnewnode-date key;pnewnode-next pla-LA_arr[index].next;pla-LA_arr[index].next pnewnode;return true;/* LA_Node* p Search_LA(pla, key);if (p ! NULL){return true;}int index Get_HashAddress(key);LA_Node* pnewnode (LA_Node*)malloc(sizeof(LA_Node));if (pnewnode NULL)exit(EXIT_FAILURE);pnewnode-data key;pnewnode-next pla-LA_arr[index].next;pla-LA_arr[index].next pnewnode;return true;*/}//3.查找LA_Node* Search_LA(LinkAddress* pla, int key){int index Get_HashAddress(key);for (LA_Node* p pla-LA_arr[index].next; p ! NULL; p p-next){if (p-date key){return p;}}return NULL;//int index Get_HashAddress(key);//for (LA_Node* p pla-LA_arr[index].next; p ! NULL; p p-next)//{// if (p-data key)// return p;//}}//4.打印void Show(LinkAddress* pla){for (int i 0; i MAXSIZE; i){printf(第%d行, i);for (LA_Node* p pla-LA_arr[i].next; p ! NULL; p p-next){printf(%d-, p-date);}printf(\n);}//for (int i 0; i MAXSIZE; i)//{// printf(第%d行; , i);// for (LA_Node* p pla-LA_arr[i].next; p ! NULL; p p-next)// {// printf(%d-, p-data);// }// printf(\n);//}}//5.删除bool Delete_LA(LinkAddress* pla, int key){//作业int index Get_HashAddress(key);LA_Node* q Search_LA(pla, key);if (NULL q)return false;LA_Node* p pla-LA_arr[index];for (; p-next ! q; p p-next);p-next q-next;free(q);return true;/*int index Get_HashAddress(key);LA_Node* q Search_LA(pla, key);if(q!NULL)return true;LA_Node* p pla-LA_arr[index];for (; p-next ! q; p p-next);p-next q-next;free(q);return true;*/}//int main()//{// LinkAddress head;// Init_LA(head);//// Insert_LA(head, 12);// Insert_LA(head, 67);// Insert_LA(head, 56);// Insert_LA(head, 16);// Insert_LA(head, 25);// Insert_LA(head, 37);// Insert_LA(head, 22);// Insert_LA(head, 29);// Insert_LA(head, 15);// Insert_LA(head, 47);// Insert_LA(head, 48);// Insert_LA(head, 34);//// Show(head);//// return 0;//}//哈希扩展技术//一致性哈希//虚拟节点//布隆过滤器//1 一致性哈希// 一致性哈希就是解决数据受影响太大的问题// 一个服务器管理一段数据 减少变化引起的数据影响// 虚拟节点// 增加一堆与主服务器相同的虚拟服务器 将数据分的很细 减少变化引起的数据影响// 布隆过滤器// 在海量数据中确定一个值是否存在// 布隆过滤器 一个特别大的二进制矢量数组若干个哈希函数 占700W~800W个格子 800W100W字节 约等于 1000K 约等于 1MB// 布隆过滤器 存在一定的误判率// 优点 1 简单 体积小 2 确定一个人不在 则一定不在 3 保密性特别好// 缺点 1 缺点一个人不在 不一定不在 2 只能插入不能删除//Java 需要一个参数 你能接受的误判率大小la, int key);