哈希表

哈希表是一种数据结构,以键值对的形式表示数据。每个键都映射到哈希表中的一个值。这些键用于索引值/数据。关联数组也采用了类似的方法。

数据借助键在键值对中表示,如下图所示。每个数据都与一个键相关联。键是一个指向数据的整数。

1.直接地址表

当程序使用的空间量不是问题时,将使用直接地址表。在这里,我们假设

一个整数池被称为Universe U = {0, 1, ……., n-1}。

直接地址表的每个插槽都T[0...n-1]包含一个指向与数据相对应的元素的指针。

数组的索引T是键本身,其内容T是指向集合的指针[key, element]。如果没有键的元素,则保留为NULL

有时,关键本身就是数据。

伪代码用于操作
directAddressSearch(T, k)
  return T[k]
directAddressInsert(T, x)
  T[x.key] = x
directAddressDelete(T, x)
  T[x.key] = NIL
直接地址表的局限性

2.哈希表

在哈希表中,将对键进行处理以产生映射到所需元素的新索引。此过程称为哈希

让我们h(x)成为一个哈希函数,k成为一个键。h(k)计算得出,并用作元素的索引。

哈希表的局限性

但是,我们还有其他解决冲突的技术

哈希表优于直接地址表的优点:

直接地址表的主要问题是数组的大小和键的可能很大的值。哈希函数减小了索引的范围,因此数组的大小也减小了。

例如,如果为k = 9845648451321,则h(k) = 11(使用某种哈希函数)。这有助于节省浪费的内存,同时提供9845648451321数组的索引

链接解决冲突

在这种技术中,如果哈希函数为多个元素生成相同的索引,则使用双向链表将这些元素存储在相同的索引中

如果j是多个元素的插槽,则它包含一个指向元素列表头部的指针。如果不存在任何元素,则j包含NIL

伪代码用于操作
chainedHashSearch(T, k)
  return T[h(k)]
chainedHashInsert(T, x)
  T[h(x.key)] = x //insert at the head
chainedHashDelete(T, x)
  T[h(x.key)] = NIL
Python代码
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代码
// 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); 
  } 
} 
C代码
// 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);
}

良好的哈希函数

良好的哈希函数具有以下特征。

  1. 它不应生成太大且存储桶空间小的密钥。空间被浪费了。
  2. 生成的密钥应该既不紧密也不在范围内。
  3. 必须尽可能减少碰撞。

用于散列的一些方法是:

如果k是键,并且m是哈希表的大小,则哈希函数h()的计算公式为:

h(k) = k mod m

例如,如果一个哈希表的大小10和k = 112然后h(k) = 112国防部10 = 2。的价值m一定不是的力量2。这是因为2二进制格式的幂是10, 100, 1000, …。当找到时k mod m,我们将始终获得较低阶的p位。

if m = 22, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 01
if m = 23, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 001
if m = 24, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 0001
if m = 2p, then h(k) = p lower bits of m

乘法的方法

h(k) = ⌊m(kA mod 1)⌋

通用散列

在通用哈希中,哈希函数是独立于密钥随机选择的。

开放式寻址

多个值可以存储在普通哈希表的单个插槽中。

通过使用开放式寻址,每个插槽都可以用单个键填充或使用left键NIL。所有元素都存储在哈希表本身中。

与链接不同,多个元素不能放入同一插槽。开放式寻址基本上是一种冲突解决技术。开放式寻址使用的一些方法是:

线性探测

在线性探测中,通过检查下一个插槽来解决冲突。

h(k, i) = (h′(k) + i) mod m

如果在发生碰撞>h(k, 0),则h(k, 1)进行检查。这样,的值i线性增加。 线性探测的问题是相邻槽的簇被填充。插入新元素时,必须遍历整个群集。这增加了对哈希表执行操作所需的时间。

二次探测

在二次探测中,通过使用以下关系,可以增大槽之间的间距(大于1)

h(k, i) = (h′(k) + c1i + c2i2) mod m

双重哈希

如果在应用哈希函数之后发生冲突h(k),则将计算另一个哈希函数以查找下一个时隙。

h(k, i) = (h1(k) + ih2(k)) mod m

哈希表应用

哈希表在以下位置实现