哈希表和碰撞算法

水深无声 2023-01-10 14:35 152阅读 0赞

## 线性探测法 ##

**哈希表结构体**

#include<iostream>
    #include<string.h>
    using namespace std;
    
    #define MAX 100
    struct HashTable{
    	int count; //元素个数
    	int p;
    	int data[MAX]={0}; //数据域 
    };

**计算哈希算法，这里采用最常用的求余数法**

int hash(int value,int p){
    	return value%p;
    }

**插入元素，线性探测法**

就是如果发生碰撞，就一直往前寻找空位子，所以P这个参数会影响碰撞的次数

int Insert(HashTable* table,int value)  //线性探测
    {
    	
    	int address = hash(value,table->p);
    	if(table->data[address]==0){
    		table->data[address]=value;
    	}else{
    		if(table->count<MAX){
    			
    			while(table->data[address]!=0){
    				address = (address+1)%MAX;
    			}
    			table->data[address] = value;
    		}else{
    			cout<<"满了"<<endl; 
    		}
    	}	
    }

**寻找元素的索引位置**

int find(HashTable* table,int value) //查找值的位置 不存在返回-1
    {
    	int index = (value%table->p);
    	int count=1;
    	while(table->data[index]!=value && count<=(MAX+1)){
    		count++;
    		index = (index+1)%MAX;
    	} 
    	if(count>MAX){
    		cout<<"找不到"<<endl;
    		return -1;
    	}else{
    		return index;
    	}
    } 
    
    void Delete(HashTable* table,int value){
    	int index = find(table,value);
    	if(index!=-1){
    		table->data[index] = 0;
    	}
    }

**删除元素**

void Delete(HashTable* table,int value){
    	int index = find(table,value);
    	if(index!=-1){
    		table->data[index] = 0;
    	}
    }

**可执行的完整代码**

#include<iostream>
    #include<string.h>
    using namespace std;
    
    #define MAX 100
    struct HashTable{
    	int count; //元素个数
    	int p;
    	int data[MAX]={0}; //数据域 
    };
    
    
    int hash(int value,int p){
    	return value%p;
    }
    
    int Insert(HashTable* table,int value)  //线性探测
    {
    	
    	int address = hash(value,table->p);
    	if(table->data[address]==0){
    		table->data[address]=value;
    	}else{
    		if(table->count<MAX){
    			
    			while(table->data[address]!=0){
    				address = (address+1)%MAX;
    			}
    			table->data[address] = value;
    		}else{
    			cout<<"满了"<<endl; 
    		}
    	}	
    }
    
    int find(HashTable* table,int value) //查找值的位置 不存在返回-1
    {
    	int index = (value%table->p);
    	int count=1;
    	while(table->data[index]!=value && count<=(MAX+1)){
    		count++;
    		index = (index+1)%MAX;
    	} 
    	if(count>MAX){
    		cout<<"找不到"<<endl;
    		return -1;
    	}else{
    		return index;
    	}
    } 
    
    void Delete(HashTable* table,int value){
    	int index = find(table,value);
    	if(index!=-1){
    		table->data[index] = 0;
    	}
    }
     
    
    
    int main(){
    	
    	HashTable* table = new HashTable;
    	table->p = 91;
    	table->count=0;
    	memset(table->data,0,sizeof(int)*MAX);
    	Insert(table,986);
    	Insert(table,1986);
    	Insert(table,286);
    	Insert(table,96);
    	cout<<find(table,986)<<endl;
    	cout<<find(table,1986)<<endl;
    	cout<<find(table,96)<<endl;
    	Delete(table,1986);
    	cout<<find(table,1986)<<endl; 
    	return 0;
    }

--------------------

## 拉链法 ##

**结构体**

**插入元素，如果发生碰撞，就在当前节点的链表上插入**

void Insert(HashTable* table,int value){
    	int index = (value%P);
    	if(table->data[index].value!=0){
    		
    		Node** node = &(table->data[index].next);
    		while((*node)!=NULL)
    			*node = (*node)->next;
    		*node = new Node;
    		(*node)->value = value;
    		(*node)->next = NULL;
    		
    	}else{
    		
    		table->data[index].value = value;
    	}
    }

**寻找元素**

Node* find(HashTable* table,int val){
    	int index = (val%P);
    	if(table->data[index].value==val){
    		return &table->data[index];
    	}else{
    		Node* node = table->data[index].next;
    		while( node!=NULL&&node->value!=val){
    			node = node->next;
    		}
    		return node;
    	}
    }

**删除元素**

如果元素在链表上，那和删除链表节点一样，特殊情况需要考虑的就是头结点

如果是在哈希表上，则如果有链表，则将链表提升，没有的话直接清零

**可执行代码**

#include<iostream>
    #include<string.h>
    using namespace std;
    #define MAX 10
    #define P 7
    struct Node{
    	int value;
    	Node* next;
    };
    
    struct HashTable{
    	int count=0;
    	Node data[MAX]; 
    };
    
    
    void Insert(HashTable* table,int value){
    	int index = (value%P);
    	if(table->data[index].value!=0){
    		
    		Node** node = &(table->data[index].next);
    		while((*node)!=NULL)
    			*node = (*node)->next;
    		*node = new Node;
    		(*node)->value = value;
    		(*node)->next = NULL;
    		
    	}else{
    		
    		table->data[index].value = value;
    	}
    }
    
    Node* find(HashTable* table,int val){
    	int index = (val%P);
    	if(table->data[index].value==val){
    		return &table->data[index];
    	}else{
    		Node* node = table->data[index].next;
    		while( node!=NULL&&node->value!=val){
    			node = node->next;
    		}
    		return node;
    	}
    } 
    
    
    
    
    int main(){
    	HashTable* table = new HashTable;
    	for(int i=0;i<MAX;i++){
    		table->data[i].value=0;
    		table->data[i].next=NULL;
    	}
    	Insert(table,1);
    	Insert(table,8);
    	Insert(table,9);
    	Insert(table,6);
    	Insert(table,2);
    //	
    	cout<<find(table,1)->next->value;
    	
    	
    	return 0;
    }