哈希表
- 哈希表基本概念:哈希表是一种使用键值对存储数据的数据结构,每个键对应一个独一无二的索引,值是与键相关联的数据。
- 哈希函数和冲突:哈希表中使用哈希函数将键转换为数组索引。当多个键映射到同一索引时,会发生哈希冲突,可以通过链式冲突解决或开放寻址(如线性探测、二次探测、双重哈希)来解决。
- 哈希表的应用:哈希表广泛应用于需要快速数据查找和插入的场景,如数据库索引、缓存实现、加密算法等。
哈希表数据结构以键值对的形式存储元素,其中
- 键 - 用于索引值的唯一整数
- 值 - 与键相关联的数据。
哈希(哈希函数)
在哈希表中,使用键处理新索引。然后,将与该键对应的元素存储在索引中。这个过程称为哈希。
假设 k
是一个键,h(x)
是一个哈希函数。
在这里,h(k)
将给我们提供一个存储与 k
关联的元素的新索引。
哈希冲突
当哈希函数为多个键生成相同的索引时,将会发生冲突(在该索引中存储哪个值)。这称为哈希冲突。
我们可以使用以下技术解决哈希冲突。
- 链式冲突解决
- 开放寻址:线性/二次探测和双重哈希
1. 链式冲突解决
在链式冲突中,如果哈希函数为多个元素生成相同的索引,这些元素将使用双向链表存储在同一索引中。
如果 j
是多个元素的槽位,它包含指向元素链表头的指针。如果没有元素存在,则 j
包含 NIL
。
操作的伪代码
chainedHashSearch(T, k)
return T[h(k)]
chainedHashInsert(T, x)
T[h(x.key)] = x //插入到链表头
chainedHashDelete(T, x)
T[h(x.key)] = NIL
2. 开放寻址
与链式冲突解决不同,开放寻址不会将多个元素存储在同一个槽位中。在这里,每个槽位要么填充有一个键,要么为空(NIL
)。
在开放寻址中使用的不同技术包括:
i. 线性探测
在线性探测中,冲突通过检查下一个槽位来解决。
h(k, i) = (h′(k) + i) mod m
其中
i = {0, 1, ….}
h'(k)
是一个新的哈希函数
如果在 h(k, 0)
处发生冲突,则会检查 h(k, 1)
。通过这种方式,递增 i
的值。
线性探测的问题在于会填充相邻的槽位。当插入新元素时,必须遍历整个簇。这会增加执行哈希表操作所需的时间。
ii. 二次探测
它与线性探测类似,但槽位之间的间距增加(大于1),使用以下关系。
h(k, i) = (h′(k) + c``1``i + c``2``i``2``) mod m
其中,
c``1
和c``2
是正的辅助常数,i = {0, 1, ….}
iii. 双重哈希
如果在应用哈希函数 h(k)
后发生冲突,那么会为查找下一个槽位计算另一个哈希函数。
h(k, i) = (h``1``(k) + ih``2``(k)) mod m
良好的哈希函数
良好的哈希函数可能不能完全防止冲突,但它可以减少冲突的数量。
在这里,我们将研究不同的方法来找到良好的哈希函数
1. 除法法
如果 k
是一个键,m
是哈希表的大小,则哈希函数 h()
计算如下:
h(k) = k mod m
例如,如果哈希表的大小是 10
,k = 112
,则 h(k) = 112
mod 10 = 2
。m
的值不得是 2
的幂次方。这是因为在二进制格式中,2
的幂次方是 10, 100, 1000, …
。当我们找到 k mod m
时,我们将始终获得低阶 p 位。
如果 m = 22,k = 17,那么 h(k) = 17 mod 22 = 10001 mod 100 = 01
如果 m = 23,k = 17,那么 h(k) = 17 mod 22 = 10001 mod 100 = 001
如果 m = 24,k = 17,那么 h(k) = 17 mod 22 = 10001 mod 100 = 0001
如果 m = 2p,则 h(k) = m 的 p 个低位
2. 乘法法
h(k) = ⌊m(kA mod 1)⌋
其中,
kA mod 1
给出了kA
的小数部分,⌊ ⌋
给出了向下取整的值A
是任意常数。A
的值介于0
和1
之间。但是,Knuth 建议的最佳选择是≈ (√5-1)/2
。
3. 通用哈希
在通用哈希中,哈希函数是独立于键值而随机选择的。
Python、Java 和 C/C++ 示例
# Python program to demonstrate working of HashTable
hashTable = [[],] * 10
def checkPrime(n):
if n == 1 or n == 0:
return 0
for i in range(2, n//2):
if n % i == 0:
return 0
return 1
def getPrime(n):
if n % 2 == 0:
n = n + 1
while not checkPrime(n):
n += 2
return n
def hashFunction(key):
capacity = getPrime(10)
return key % capacity
def insertData(key, data):
index = hashFunction(key)
hashTable[index] = [key, data]
def removeData(key):
index = hashFunction(key)
hashTable[index] = 0
insertData(123, "apple")
insertData(432, "mango")
insertData(213, "banana")
insertData(654, "guava")
print(hashTable)
removeData(123)
print(hashTable)
// Java program to demonstrate working of HashTable
import java.util.*;
class HashTable {
public static void main(String args[])
{
Hashtable<Integer, Integer>
ht = new Hashtable<Integer, Integer>();
ht.put(123, 432);
ht.put(12, 2345);
ht.put(15, 5643);
ht.put(3, 321);
ht.remove(12);
System.out.println(ht);
}
}
// Implementing hash table in C
#include <stdio.h>
#include <stdlib.h>
struct set
{
int key;
int data;
};
struct set *array;
int capacity = 10;
int size = 0;
int hashFunction(int key)
{
return (key % capacity);
}
int checkPrime(int n)
{
int i;
if (n == 1 || n == 0)
{
return 0;
}
for (i = 2; i < n / 2; i++)
{
if (n % i == 0)
{
return 0;
}
}
return 1;
}
int getPrime(int n)
{
if (n % 2 == 0)
{
n++;
}
while (!checkPrime(n))
{
n += 2;
}
return n;
}
void init_array()
{
capacity = getPrime(capacity);
array = (struct set *)malloc(capacity * sizeof(struct set));
for (int i = 0; i < capacity; i++)
{
array[i].key = 0;
array[i].data = 0;
}
}
void insert(int key, int data)
{
int index = hashFunction(key);
if (array[index].data == 0)
{
array[index].key = key;
array[index].data = data;
size++;
printf("\n Key (%d) has been inserted \n", key);
}
else if (array[index].key == key)
{
array[index].data = data;
}
else
{
printf("\n Collision occured \n");
}
}
void remove_element(int key)
{
int index = hashFunction(key);
if (array[index].data == 0)
{
printf("\n This key does not exist \n");
}
else
{
array[index].key = 0;
array[index].data = 0;
size--;
printf("\n Key (%d) has been removed \n", key);
}
}
void display()
{
int i;
for (i = 0; i < capacity; i++)
{
if (array[i].data == 0)
{
printf("\n array[%d]: / ", i);
}
else
{
printf("\n key: %d array[%d]: %d \t", array[i].key, i, array[i].data);
}
}
}
int size_of_hashtable()
{
return size;
}
int main()
{
int choice, key, data, n;
int c = 0;
init_array();
do
{
printf("1.Insert item in the Hash Table"
"\n2.Remove item from the Hash Table"
"\n3.Check the size of Hash Table"
"\n4.Display a Hash Table"
"\n\n Please enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter key -:\t");
scanf("%d", &key);
printf("Enter data -:\t");
scanf("%d", &data);
insert(key, data);
break;
case 2:
printf("Enter the key to delete-:");
scanf("%d", &key);
remove_element(key);
break;
case 3:
n = size_of_hashtable();
printf("Size of Hash Table is-:%d\n", n);
break;
case 4:
display();
break;
default:
printf("Invalid Input\n");
}
printf("\nDo you want to continue (press 1 for yes): ");
scanf("%d", &c);
} while (c == 1);
}
// Implementing hash table in C++
#include <iostream>
#include <list>
using namespace std;
class HashTable
{
int capacity;
list<int> *table;
public:
HashTable(int V);
void insertItem(int key, int data);
void deleteItem(int key);
int checkPrime(int n)
{
int i;
if (n == 1 || n == 0)
{
return 0;
}
for (i = 2; i < n / 2; i++)
{
if (n % i == 0)
{
return 0;
}
}
return 1;
}
int getPrime(int n)
{
if (n % 2 == 0)
{
n++;
}
while (!checkPrime(n))
{
n += 2;
}
return n;
}
int hashFunction(int key)
{
return (key % capacity);
}
void displayHash();
};
HashTable::HashTable(int c)
{
int size = getPrime(c);
this->capacity = size;
table = new list<int>[capacity];
}
void HashTable::insertItem(int key, int data)
{
int index = hashFunction(key);
table[index].push_back(data);
}
void HashTable::deleteItem(int key)
{
int index = hashFunction(key);
list<int>::iterator i;
for (i = table[index].begin();
i != table[index].end(); i++)
{
if (*i == key)
break;
}
if (i != table[index].end())
table[index].erase(i);
}
void HashTable::displayHash()
{
for (int i = 0; i < capacity; i++)
{
cout << "table[" << i << "]";
for (auto x : table[i])
cout << " --> " << x;
cout << endl;
}
}
int main()
{
int key[] = {231, 321, 212, 321, 433, 262};
int data[] = {123, 432, 523, 43, 423, 111};
int size = sizeof(key) / sizeof(key[0]);
HashTable h(size);
for (int i = 0; i < size; i++)
h.insertItem(key[i], data[i]);
h.deleteItem(12);
h.displayHash();
}
哈希表的应用
哈希表在以下场景中得到应用:
- 需要常数时间的查找和插入
- 加密应用
- 需要对数据进行索引