欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Hash Tables(chaining)

程序员文章站 2022-04-24 12:45:06
...

Hash Table,叫做哈希表,也叫做散列表。
概念:通过某种对应关系h,使得每一个元素和储存位置一一对应。这种对应关系称为哈希函数。它最大的优点就是插入、搜索和删除得很快(O(1))。
碰撞(Collision):不同的关键字对应同一个哈希地址
本文主要介绍的是解决碰撞的方法之一:chaining

原理:
In chainning,wo palce all the elements that hash to the same plot into the same list.
如果不同的key通过hash function得到的相同结果,那么就将他们放在同一个list中。如下图:
Hash Tables(chaining)

操作:
1.查找:
先找到key的索引:index=hashFunction(key)
然后遍历这个链表:

  // get the hash index of key
  int index = hashFunction(key);

  // find the key in (inex)th list
  list <int> :: iterator i;
  for (i = table[index].begin();
           i != table[index].end(); i++) {
    if (*i == key)
      break;
  }

2.插入:

void Hash::insertItem(int key)
{
    int index = hashFunction(key);
    table[index].push_back(key);
}

3.删除:
首先先查找这个元素,如果找到的话,则删除

void Hash::deleteItem(int key)
{
  // get the hash index of key
  int index = hashFunction(key);

  // find the key in (inex)th list
  list <int> :: iterator i;
  for (i = table[index].begin();
           i != table[index].end(); i++) {
    if (*i == key)
      break;
  }

  // if key is found in hash table, remove it
  if (i != table[index].end())
    table[index].erase(i);
}

完整代码:

// CPP program to implement hashing with chaining
#include<iostream>
#include <list>
using namespace std;

class Hash
{
    int BUCKET;    // No. of buckets

    // Pointer to an array containing buckets
    list<int> *table;
public:
    Hash(int V);  // Constructor

    // inserts a key into hash table
    void insertItem(int x);

    // deletes a key from hash table
    void deleteItem(int key);

    // hash function to map values to key
    int hashFunction(int x) {
        return (x % BUCKET);
    }

    void displayHash();
};

Hash::Hash(int b)
{
    this->BUCKET = b;
    table = new list<int>[BUCKET];
}

void Hash::insertItem(int key)
{
    int index = hashFunction(key);
    table[index].push_back(key);
}

void Hash::deleteItem(int key)
{
  // get the hash index of key
  int index = hashFunction(key);

  // find the key in (inex)th list
  list <int> :: iterator i;
  for (i = table[index].begin();
           i != table[index].end(); i++) {
    if (*i == key)
      break;
  }

  // if key is found in hash table, remove it
  if (i != table[index].end())
    table[index].erase(i);
}

// function to display hash table
void Hash::displayHash() {
  for (int i = 0; i < BUCKET; i++) {
    cout << i;
    for (auto x : table[i])
      cout << " --> " << x;
    cout << endl;
  }
}

// Driver program
int main()
{
  // array that contains keys to be mapped
  int a[] = {15, 11, 27, 8, 12};
  int n = sizeof(a)/sizeof(a[0]);

  // insert the keys into the hash table
  Hash h(7);   // 7 is count of buckets in
               // hash table
  for (int i = 0; i < n; i++)
    h.insertItem(a[i]);

  // delete 12 from hash table
  h.deleteItem(12);

  // display the Hash table
  h.displayHash();

  return 0;
}
相关标签: 哈希表