【cpp|哈希表(散列表)】1.为什么有哈希表？
因为哈希表的优点：常数时间的插入、查找、删除操作；调节内存和空间，结合了数组和链表的优点；以“键值对”存储数据；

//线性探测 #include 2 #include 3 4 #define SUCCESS (int)1 5 #define UNSUCCESS (int)0 6 #define HASHSIZE 12 /* 哈希表长度 */ 7 #define NULLKEY -32768 8 9 typedef struct HashTable 10 { 11int *elem; /* 哈希表元素存储地址，动态分配数组 */ 12int count; /* 当前数据元素的个数 */ 13 }HashTable; 14 15 int m=0; 16 17 /* 初始化哈希表 */ 18 int InitHashTable(HashTable *H) 19 { 20int i; 21m=HASHSIZE; 22H->count=m; 23H->elem=(int*)malloc(m*sizeof(int)); 24for(i=0; ielem[i]=NULLKEY; 26} 27return SUCCESS; 28 } 29 30 /* 哈希函数 */ 31 int Hash(int key) 32 { 33return key%m; 34 } 35 36 /* 将关键字插入散列函数 */ 37 void InsertHash(HashTable *H,int key) 38 { 39int addr=Hash(key); /* 求插入key的哈希地址 */ 40while(H->elem[addr]!=NULLKEY){ 41addr=(addr+1)%m; /* 如果不为空，发生冲突, 线性探测 */ 42} 43H->elem[addr]=key; /* 直到有空位后插入关键字 */ 44 } 45 46/* 查找 */ 47 int SearchHash(HashTable H,int key, int *addr) 48 { 49*addr=Hash(key); 50while(H.elem[*addr]!=key){ /* 如果H[*addr]不等于key, 则冲突,线性探测 */ 51*addr=(*addr+1)%m; 52if(H.elem[*addr]=NULLKEY || *addr==Hash(key)){ /* 找不到或循环回到原点 */ 53return UNSUCCESS; 54} 55} 56return SUCCESS; 57 }

//平方探测 #include #include #include #include #include using namespace std; #define MAX_TABLESIZE 10000 /* 允许开辟最大散列表长度 */ typedef int ElementType; enum EntryType{Legitimate,Empty,Deleted}; /* 散列单元的状态类型 */ typedef struct HashEntry { ElementType data; //存放元素 enum EnTryType state; //单元状态 }; typedef struct HashEntry Cell; typedef struct TblNode { int tablesize; //表的最大长度 Cell *cell; //存放散列单元数据的数据 }TblNode,*HashTable; /* 返回大于n且不超过MAXTABLESIZE的最小素数 */ int NextPrime(int n) { int p=(n%2)?n+2:n+1; // 大于n的第一个奇数 int i; while(p<=MAX_TABLESIZE){ for(i=(int)sqrt(p); i>2; i--){ if(p%i==0) break; } if(i==2){ break; }else{ p+=2; } } return p; }/* 创建哈希表 */ HashTable CreatTable(int table_size) { HashTable h=(HashTable)malloc(sizeof(TblNode)); h->tablesize=NextPrime(table_size); h->cell=(Cell*)malloc(h->tablesize*sizeof(Cell)); for(int i=0; itablesize; i++){ h->cell[i].state=Empty; } return h; }/* 查找数据的初始位置，取余法确定散列函数 */ int Hash(ElementType key) { return key%11; //除留取余法 }/* 如果key不在Hash表中,函数也会返回一个地址,这是不应该的; 那该怎么处理呢? * 不对不对,这个函数查找key是否已经在表中被占用,而是说key在Hash表中应该有 * 一席之地,即一定有位置可以存储key * */ int Find(HashTable h,ElementType key) { int current_pos, new_pos; int collision_num=0; //记录冲突次数 new_pos=current_pos=Hash(key); while(h->cell[new_pos].state!=Empty&&h->cell[new_pos].data!=key){ collision_num++; if(collision_num%2){ //处理奇数冲突 new_pos=current_pos+(collision_num+1)*(collision_num+1)/4; if(new_pos>=h->tablesize){ new_pos=new_pos%h->tablesize; } }else{ //处理偶数冲突 new_pos=current_pos-(collision_num)*(collision_num)/4; while(new_pos<0){ new_pos+=h->tablesize; } } } return new_pos; }bool Insert(HashTable h,ElementType key) { int pos=Find(h,key); if(h->cell[pos].state!=Legitimate){ h->cell[pos].state=Legitimate; h->cell[pos].data=https://www.it610.com/article/key; return true; }else{ cout<<"key已经被占用"<