c ++哈希表_用C和C ++哈希

柔光的暖阳◎ 2022-12-07 13:56 209阅读 0赞

![30048229bf62437c989bab740f53dfcf.png][]

c ++哈希表

In this tutorial you will learn about Hashing in C and C++ with program example. You will also learn various concepts of hashing like hash table, hash function, etc.

在本教程中，您将通过程序示例了解C和C ++中的哈希。 您还将学习哈希的各种概念，例如哈希表，哈希函数等。

## 散列数据结构 **(**Hashing in Data Structure**)** ##

Searching is dominant operation on any data structure. Most of the cases for inserting, deleting, updating all operations required searching first. So searching operation of particular data structure determines it’s time complexity. If we take any data structure the best time complexity for searching is O (log n) in AVL tree and sorted array only. Most of the cases it will take O (n) time. To solve this searching problem hashing concept introduced which will take O (1) time for searching. It’s constant time.

搜索是任何数据结构上的主要操作。 大多数情况下，插入，删除，更新所有操作都需要先搜索。 因此，搜索特定数据结构的操作将确定其时间复杂度。 如果我们采用任何数据结构，则用于搜索的最佳时间复杂度仅是AVL树和排序数组中的O(log n)。 在大多数情况下，将需要O(n)时间。 为了解决这个搜索问题，引入了哈希概念，这将花费O(1)的时间进行搜索。 这是恒定的时间。

### 哈希表和哈希函数 **(**Hash Table and Hash Function**)** ###

Earlier when this concept introduced programmers used to create “Direct address table”. Direct address table means, when we have “n” number of unique keys we create an array of length “n” and insert element “i” at ith index of the array. That array is called **Hash Table**. But due to this method even we have 10 elements of each range 1 lack, we should create table of size 1 lack for only 10 elements. Which is going to be waste of memory.

早在此概念引入时，程序员就创建了“直接地址表”。 直接地址表意味着，当我们有“ n”个唯一键时，我们创建一个长度为“ n”的数组，并在该数组的第i个索引处插入元素“ i”。 该数组称为**哈希表** 。 但是由于这种方法，即使我们每个缺少1范围的元素都有10个，我们也应该只为10个元素创建大小为1的表。 这将浪费内存。

To avoid this problem we fix the size of hash table (array) and map our elements into that table using a function, called **Hash function**. This function decides where to put a given element into that table. If we want to search also first apply hash function decide whether the element present in hash table or not.

为了避免这个问题，我们固定了哈希表(数组)的大小，并使用一个称为**哈希函数**的函数将元素映射到该表中。 该函数决定将给定元素放入该表的位置。 如果我们也想搜索，则首先应用哈希函数，确定元素是否存在于哈希表中。

**Example**

**例**

We have numbers from 1 to 100 and hash table of size 10. Hash function is mod 10. That means number 23 will be mapped to (23 mod 10 = 3) 3rd index of hash table.

我们有从1到100的数字，哈希表的大小为10。哈希函数是mod10。这意味着数字23将映射到哈希表的第3个索引(23 mod 10 = 3)。

![Hashing, Hash Table, Hash Function][Hashing_ Hash Table_ Hash Function]

But problem is if elements (for example) 2, 12, 22, 32, elements need to be inserted then they try to insert at index 2 only. This problem is called **Collision**. To solve this collision problem we use different types of hash function techniques. Those are given below.

但是问题是，如果需要插入元素(例如2、12、22、32)，那么它们将尝试仅插入索引2。 这个问题叫做**Collision** 。 为了解决这个冲突问题，我们使用了不同类型的哈希函数技术。 这些在下面给出。

1.  Chaining
    
    链式
2.  Open addressing
    
    开放式寻址
    
    1.  Linear probing
        
        线性探测
    2.  Quadratic probing
        
        二次探测
    3.  Double hashing
        
        双重哈希

These also called collision resolution techniques.

这些也称为冲突解决技术。

#### **链式** **(****Chaining****)** ####

In hash table instead of putting one element in index we maintain a linked list. When collision happened we place that element in corresponding linked list. Here some space is wasted because of pointers.

在哈希表中，而不是将一个元素放入索引中，我们维护一个链表。 当发生碰撞时，我们将该元素放在相应的链表中。 这里由于指针浪费了一些空间。

![Hashing 1][]

#### **开放式寻址** **(****Open Addressing****)** ####

In case if we have collision we again calculate the hash value using corresponding hash function. But this time we do some minor modifications to that input. This process of searching for empty space to insert element in called **Probing**.

万一发生碰撞，我们再次使用相应的哈希函数计算哈希值。 但是这次我们对输入做了一些小的修改。 这种搜索空白空间以在**Probing中**插入元素的过程。

![Hashing 2][]

Probing hash function is: **h (k, i)**

探测哈希函数为： **h(k，i)**

here k is the key value which is to be inserted. And i is number of collision with that element.

在此，k是要插入的键值。 我是与该元素发生碰撞的次数。

Example: If we are inserting 2, we find its hash value using h (2, 0) because it’s first collision. Suppose the answer (index) to this function index already occupied we again need to apply h (2, 1) to hash function.

示例：如果要插入2，我们将使用h(2，0)查找其哈希值，因为它是第一次冲突。 假设该函数索引的答案(索引)已被占用，我们再次需要将h(2，1)应用于哈希函数。

**Linear Probing**

**线性探测**

Let hash function is h, hash table contains  0 to n-1 slots.

设哈希函数为h，哈希表包含0到n-1个时隙。

Now we want to insert an element k. Apply h (k). If it results “x” and the index “x” already contain a value then we again apply hash function that h (k, 1) this equals to (h (k) + 1) mod n.

现在我们要插入元素k。 应用h(k)。 如果结果为“ x”并且索引“ x”已经包含一个值，则我们再次应用哈希函数h(k，1)等于(h(k)+1)mod n。

General form: h1 (k, j) = (h (k) + j) mod n

通用形式：h1(k，j)=(h(k)+ j)mod n

Example: Let hash table of size 5 which has function is mod 5 has already filled at positions 0, 2, 3.

示例：让具有功能为mod 5的大小为5的哈希表已经填充在位置0、2、3处。

Now new element 10 will try to insert. 10 mod 5 = 0. But index 0 already occupied. So it checks (probes) next (index 1) position. So 10 will insert at index 1.

现在，新元素10将尝试插入。 10 mod 5 =0。但是索引0已被占用。 因此，它检查(探测)下一个(索引1)位置。 因此，将在索引1处插入10。

Now element 11 will try to insert. 11 mod 5 = 1. But index 1 already occupied, check index 2 it also occupied (data given), 3 also occupied. So it will insert at index 4 which is empty.

现在，元素11将尝试插入。 11 mod 5 =1。但是索引1已经被占用，检查索引2也被占用(给定数据)，索引3也被占用。 因此它将插入到索引4为空。

We can observe that it linearly checking for next empty position. So it’s called linear probing.

我们可以观察到它线性检查下一个空位置。 因此，这称为线性探测。

**Problems with linear probing:**

**线性探测的问题：**

*  **Primary clustering:** There is a chance that continuous cells occupied, then the probability of new element insertion will get reduced. This problem is called primary clustering
    
    **一次聚类：**连续单元有可能被占用，然后新元素插入的可能性将降低。 此问题称为主群集
 *  **Secondary clustering:** If two elements get same value at first hash function, they follow same probe sequence.
    
    **二级聚类：**如果两个元素在第一个哈希函数中获得相同的值，则它们遵循相同的探测序列。

**Quadratic Probing**

**二次探测**

It is same as linear probing. But when collision occurs we use different function. If collision happened that element try to occupy at quadratic distance instead of linear distance.

它与线性探测相同。 但是当发生碰撞时，我们使用不同的功能。 如果发生碰撞，则该元素尝试占据二次距离而不是线性距离。

Due to this “Primary clustering” will be reduced. But secondary clustering won’t be eliminated.

因此，“主群集”将减少。 但是二级集群不会被消除。

**Double Hashing**

**双重散列**

Here we use two hash functions.

在这里，我们使用两个哈希函数。

h1 (k) = (h1 (k) + i h2 (k)) mod n. Here h1 and h2 are two hash functions.

h1(k)=(h1(k)+ i h2(k))mod n。 h1和h2是两个哈希函数。

Here the next prob position will depend on two functions h1 and h2 also.

在这里，下一个概率位置还将取决于两个函数h1和h2。

Advantages by this method are there is no chance of primary clustering. And also Secondary clustering also eliminated.

这种方法的优点是没有机会进行主要聚类。 并且也消除了辅助群集。

#### **链接与开放式寻址** **(****Chaining vs Open Addressing****)** ####

<table> 
 <tbody> 
  <tr> 
   <td><strong>Chaining</strong></td> 
   <td><strong>Open Addressing</strong></td> 
  </tr> 
  <tr> 
   <td>Elements can be stored at outside of the table</td> 
   <td>In open addressing elements should be stored inside the table only</td> 
  </tr> 
  <tr> 
   <td>In chaining at any time the number of elements in the hash table may greater than the size of the hash table</td> 
   <td>In open addressing the number of elements present in the hash table will not exceed to number of indices in hash table.</td> 
  </tr> 
  <tr> 
   <td>In case of deletion chaining is the best method</td> 
   <td>If deletion is not required. Only inserting and searching is required open addressing is better</td> 
  </tr> 
  <tr> 
   <td>Chaining requires more space</td> 
   <td>Open addressing requires less space than chaining.</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td> <strong>链式</strong> </td> 
   <td> <strong>开放式寻址</strong> </td> 
  </tr> 
  <tr> 
   <td> 元素可以存储在表的外部 </td> 
   <td> 在开放式寻址中，元素仅应存储在表中 </td> 
  </tr> 
  <tr> 
   <td> 在任何时候链接时，哈希表中的元素数量可能大于哈希表的大小 </td> 
   <td> 在开放式寻址中，哈希表中存在的元素数量将不超过哈希表中索引的数量。 </td> 
  </tr> 
  <tr> 
   <td> 在删除链接的情况下，最好的方法是 </td> 
   <td> 如果不需要删除。 仅要求插入和搜索，打开地址更好 </td> 
  </tr> 
  <tr> 
   <td> 链接需要更多空间 </td> 
   <td> 开放寻址比链接需要更少的空间。 </td> 
  </tr> 
 </tbody> 
</table>

## C散列程序 **(**Program for Hashing in C**)** ##

Below is the implementation of hashing or hash table in C.

以下是C语言中哈希或哈希表的实现。

#include<stdio.h>
    #include<limits.h>
     
    /*
    This is code for linear probing in open addressing. If you want to do quadratic probing and double hashing which are also
    open addressing methods in this code when I used hash function that (pos+1)%hFn in that place just replace with another function.
    */
     
    void insert(int ary[],int hFn, int size){
        int element,pos,n=0;
     
    	printf("Enter key element to insert\n");
    	scanf("%d",&element);
     
    	pos = element%hFn;
     
    	while(ary[pos]!= INT_MIN) {  // INT_MIN and INT_MAX indicates that cell is empty. So if cell is empty loop will break and goto bottom of the loop to insert element
    		if(ary[pos]== INT_MAX)
                break;
    		pos = (pos+1)%hFn;
    		n++;
    		if(n==size)
    		break;      // If table is full we should break, if not check this, loop will go to infinite loop.
    	}
     
    	if(n==size)
            printf("Hash table was full of elements\nNo Place to insert this element\n\n");
    	else
            ary[pos] = element;    //Inserting element
    }
     
    void delete(int ary[],int hFn,int size){
    	/*
    	very careful observation required while deleting. To understand code of this delete function see the note at end of the program
    	*/
    	int element,n=0,pos;
     
    	printf("Enter element to delete\n");
    	scanf("%d",&element);
     
    	pos = element%hFn;
     
    	while(n++ != size){
    		if(ary[pos]==INT_MIN){
    			printf("Element not found in hash table\n");
    			break;
    		}
    		else if(ary[pos]==element){
    			ary[pos]=INT_MAX;
    			printf("Element deleted\n\n");
    			break;
    		}
    		else{
    			pos = (pos+1) % hFn;
    		}
    	}
    	if(--n==size)
            printf("Element not found in hash table\n");
    }
     
    void search(int ary[],int hFn,int size){
    	int element,pos,n=0;
     
    	printf("Enter element you want to search\n");
    	scanf("%d",&element);
     
    	pos = element%hFn;
     
    	while(n++ != size){
    		if(ary[pos]==element){
    			printf("Element found at index %d\n",pos);
    			break;
    		}
    		else
                if(ary[pos]==INT_MAX ||ary[pos]!=INT_MIN)
                    pos = (pos+1) %hFn;
    	}
    	if(--n==size) printf("Element not found in hash table\n");
    }
     
    void display(int ary[],int size){
    	int i;
     
    	printf("Index\tValue\n");
     
    	for(i=0;i<size;i++)
            printf("%d\t%d\n",i,ary[i]);
    }
    int main(){
    	int size,hFn,i,choice;
     
    	printf("Enter size of hash table\n");
    	scanf("%d",&size);
     
    	int ary[size];
     
    	printf("Enter hash function [if mod 10 enter 10]\n");
    	scanf("%d",&hFn);
     
    	for(i=0;i<size;i++)
            ary[i]=INT_MIN; //Assigning INT_MIN indicates that cell is empty
     
    	do{
    		printf("Enter your choice\n");
    		printf(" 1-> Insert\n 2-> Delete\n 3-> Display\n 4-> Searching\n 0-> Exit\n");
    		scanf("%d",&choice);
     
    		switch(choice){
    			case 1:
    				insert(ary,hFn,size);
    				break;
    			case 2:
    				delete(ary,hFn,size);
    				break;
    			case 3:
    				display(ary,size);
    				break;
    			case 4:
    				search(ary,hFn,size);
    				break;
    			default:
    				printf("Enter correct choice\n");
    				break;
    		}
    	}while(choice);
     
    	return 0;
    }
     
    /*
    Note: Explanation for delete function and search function
    suppose hash table contains elements 22, 32, 42 at index positions 2, 3, 4.
    Now delete(22) applied. As per hash function defined we first check for index 2. Found, so deleted. And make that index to nill.
    Next apply delete(32). This time also it first check at index 2, but found that its nothing.Then we stop and say element 32 not
    found in hash table. But it's present at index 3. But how should we know whether to check to other index or not? For this
    when we delete any element we flag that with INT_MAX which indicates that in that position previously some element is there now
    it's deleted. So don't stop here your required element may present at next index.
    */

**Output**

**输出量**

*Enter size of hash table*

*输入哈希表的大小*

*10*

*Enter hash function \[if mod 10 enter 10\]*

*输入哈希函数\[如果mod 10输入10\]*

*10*

*Enter your choice*

*输入您的选择*

* 1-> Insert*

*1->插入*

* 2-> Delete*

*2->删除*

* 3->Display*

*3->显示*

* 4->Searching*

*4->搜索*

* 0->Exit*

*0->退出*

*1*

*1个*

*Enter key element to insert*

*输入要插入的关键元素*

*12*

*Enter your choice*

*输入您的选择*

* 1-> Insert*

*1->插入*

* 2-> Delete*

*2->删除*

* 3->Display*

*3->显示*

* 4->Searching*

*4->搜索*

* 0->Exit*

*0->退出*

*1*

*1个*

*Enter key element to insert*

*输入要插入的关键元素*

*22*

*Enter your choice*

*输入您的选择*

* 1-> Insert*

*1->插入*

* 2-> Delete*

*2->删除*

* 3->Display*

*3->显示*

* 4->Searching*

*4->搜索*

* 0->Exit*

*0->退出*

*1*

*1个*

*Enter key element to insert*

*输入要插入的关键元素*

*32*

*Enter your choice*

*输入您的选择*

* 1-> Insert*

*1->插入*

* 2-> Delete*

*2->删除*

* 3->Display*

*3->显示*

* 4->Searching*

*4->搜索*

* 0->Exit*

*0->退出*

*3*

*Index   Value*

*指数值*

*0       -2147483648*

*0 -2147483648*

*1       -2147483648*

*1 -2147483648*

*2       12*

*2 12*

*3       22*

*3 22*

*4       32*

*4 32*

*5       -2147483648*

*5 -2147483648*

*6       -2147483648*

*6 -2147483648*

*7       -2147483648*

*7 -2147483648*

*8       -2147483648*

*8 -2147483648*

*9       -2147483648*

*9 -2147483648*

*Enter your choice*

*输入您的选择*

* 1-> Insert*

*1->插入*

* 2-> Delete*

*2->删除*

* 3->Display*

*3->显示*

* 4->Searching*

*4->搜索*

* 0->Exit*

*0->退出*

*2*

*Enter element to delete*

*输入要删除的元素*

*12*

*Element deleted*

*元素已删除*

*Enter your choice*

*输入您的选择*

* 1-> Insert*

*1->插入*

* 2-> Delete*

*2->删除*

* 3->Display*

*3->显示*

* 4->Searching*

*4->搜索*

* 0->Exit*

*0->退出*

*4*

*Enter element you want to search*

*输入您要搜索的元素*

*32*

*Element found at index 4*

*在索引4找到元素*

*Enter your choice*

*输入您的选择*

* 1-> Insert*

*1->插入*

* 2-> Delete*

*2->删除*

* 3->Display*

*3->显示*

* 4->Searching*

*4->搜索*

* 0->Exit*

*0->退出*

*0*

## C ++中的哈希程序 **(**Program for Hashing in C++**)** ##

Below is the implementation of hashing or hash table in C++.

下面是C ++中哈希或哈希表的实现。

#include<iostream>
    #include<limits.h>
     
    using namespace std;
     
    /*
    This is code for linear probing in open addressing. If you want to do quadratic probing and double hashing which are also
    open addressing methods in this code when I used hash function that (pos+1)%hFn in that place just replace with another function.
    */
     
    void Insert(int ary[],int hFn, int Size){
        int element,pos,n=0;
     
    	cout<<"Enter key element to insert\n";
    	cin>>element;
     
    	pos = element%hFn;
     
    	while(ary[pos]!= INT_MIN) {  // INT_MIN and INT_MAX indicates that cell is empty. So if cell is empty loop will break and goto bottom of the loop to insert element
    		if(ary[pos]== INT_MAX)
                break;
    		pos = (pos+1)%hFn;
    		n++;
    		if(n==Size)
                break;      // If table is full we should break, if not check this, loop will go to infinite loop.
    	}
     
    	if(n==Size)
            cout<<"Hash table was full of elements\nNo Place to insert this element\n\n";
    	else
            ary[pos] = element;    //Inserting element
    }
     
    void Delete(int ary[],int hFn,int Size){
    	/*
    	very careful observation required while deleting. To understand code of this delete function see the note at end of the program
    	*/
    	int element,n=0,pos;
     
    	cout<<"Enter element to delete\n";
    	cin>>element;
     
    	pos = element%hFn;
     
    	while(n++ != Size){
    		if(ary[pos]==INT_MIN){
    			cout<<"Element not found in hash table\n";
    			break;
    		}
    		else if(ary[pos]==element){
    			ary[pos]=INT_MAX;
    			cout<<"Element deleted\n\n";
    			break;
    		}
    		else{
    			pos = (pos+1) % hFn;
    		}
    	}
    	if(--n==Size)
            cout<<"Element not found in hash table\n";
    }
     
    void Search(int ary[],int hFn,int Size){
    	int element,pos,n=0;
     
    	cout<<"Enter element you want to search\n";
    	cin>>element;
     
    	pos = element%hFn;
     
    	while(n++ != Size){
    		if(ary[pos]==element){
    			cout<<"Element found at index "<<pos<<"\n";
    			break;
    		}
    		else
                if(ary[pos]==INT_MAX ||ary[pos]!=INT_MIN)
                    pos = (pos+1) %hFn;
    	}
    	if(--n==Size)
            cout<<"Element not found in hash table\n";
    }
     
    void display(int ary[],int Size){
    	int i;
     
    	cout<<"Index\tValue\n";
     
    	for(i=0;i<Size;i++)
            cout<<i<<"\t"<<ary[i]<<"\n";
    }
     
    int main(){
    	int Size,hFn,i,choice;
     
    	cout<<"Enter size of hash table\n";
    	cin>>Size;
     
    	int ary[Size];
     
        cout<<"Enter hash function [if mod 10 enter 10]\n";
    	cin>>hFn;
     
    	for(i=0;i<Size;i++)
            ary[i]=INT_MIN; //Assigning INT_MIN indicates that cell is empty
     
    	do{
    		cout<<"Enter your choice\n";
    		cout<<" 1-> Insert\n 2-> Delete\n 3-> Display\n 4-> Searching\n 0-> Exit\n";
    		cin>>choice;
     
    		switch(choice){
    			case 1:
    				Insert(ary,hFn,Size);
    				break;
    			case 2:
    				Delete(ary,hFn,Size);
    				break;
    			case 3:
    				display(ary,Size);
    				break;
    			case 4:
    				Search(ary,hFn,Size);
    				break;
    			default:
    				cout<<"Enter correct choice\n";
    				break;
    		}
    	}while(choice);
     
    	return 0;
    }
     
    /*
    Note: Explanation for delete function and search function
    suppose hash table contains elements 22, 32, 42 at index positions 2, 3, 4.
    Now delete(22) applied. As per hash function defined we first check for index 2. Found, so deleted. And make that index to nill.
    Next apply delete(32). This time also it first check at index 2, but found that its nothing.Then we stop and say element 32 not
    found in hash table. But it's present at index 3. But how should we know whether to check to other index or not? For this
    when we delete any element we flag that with INT_MAX which indicates that in that position previously some element is there now
    it's deleted. So don't stop here your required element may present at next index.
    */

Comment below if have queries or found anything incorrect in above tutorial for Hashing in C and C++.

如果在上面的C和C ++哈希教程中有疑问或发现任何不正确之处，请在下面评论。

> 翻译自: [https://www.thecrazyprogrammer.com/2017/06/hashing.html][https_www.thecrazyprogrammer.com_2017_06_hashing.html]

c ++哈希表

[30048229bf62437c989bab740f53dfcf.png]: /images/20221123/19f4c617dd9a496889c49ac920af8e85.png
[Hashing_ Hash Table_ Hash Function]: /images/20221123/a1f2d3a5d84b43609fbe752778b0f24d.png
[Hashing 1]: /images/20221123/4fbbe891d47b4651b2a9e534c894d8fd.png
[Hashing 2]: /images/20221123/08802de10c494eb9b3c77febb63a12fa.png
[https_www.thecrazyprogrammer.com_2017_06_hashing.html]: https://www.thecrazyprogrammer.com/2017/06/hashing.html