哈希表

提示

1. 哈希表基本概念：哈希表是一种使用键值对存储数据的数据结构，每个键对应一个独一无二的索引，值是与键相关联的数据。
2. 哈希函数和冲突：哈希表中使用哈希函数将键转换为数组索引。当多个键映射到同一索引时，会发生哈希冲突，可以通过链式冲突解决或开放寻址（如线性探测、二次探测、双重哈希）来解决。
3. 哈希表的应用：哈希表广泛应用于需要快速数据查找和插入的场景，如数据库索引、缓存实现、加密算法等。

哈希表数据结构以键值对的形式存储元素，其中

• 键 - 用于索引值的唯一整数
• 值 - 与键相关联的数据。

哈希（哈希函数）

在哈希表中，使用键处理新索引。然后，将与该键对应的元素存储在索引中。这个过程称为哈希。

假设 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 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();
}

哈希表的应用

哈希表在以下场景中得到应用：

• 需要常数时间的查找和插入
• 加密应用
• 需要对数据进行索引