資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 雜湊錶鏈地址法程式
雜湊是一種將任意長度的資料元素對映到固定大小鍵的方法。雜湊的工作原理是鍵值對。
雜湊函式是雜湊對映中執行對映的函式。作為雜湊函式輸入給出的資料元素可能獲得相同的雜湊鍵。在這種情況下，元素可能會重疊。為了避免具有相同雜湊鍵的元素重疊，引入了鏈地址法的概念。
建立雜湊對映
為了建立雜湊對映，我們需要雜湊函式來定義資料元素的索引值。
我們有一個包含 n 個桶的雜湊表。要將節點插入雜湊表，我們給出一個雜湊函式為
hashIndex = key % noOfBuckets
現在，我們將使用此雜湊函式並計算每個插入到雜湊對映中的值的雜湊索引。
插入元素並計算給定鍵值的雜湊索引，然後將新節點插入到列表的末尾。
要刪除節點，我們將計算雜湊索引，並在對應於雜湊索引的桶中搜索桶中的元素並將其刪除。
示例
#include<iostream>
#include <list>
using namespace std;
class Hash{
int BUCKET;
list < int >*table;
public:
Hash (int V);
void insertItem (int x);
void deleteItem (int 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){
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 Hash::displayHash (){
for (int i = 0; i < BUCKET; i++){
cout << i;
for (auto x:table[i])
cout << " --> " << x;
cout << endl;
}
}
int main (){
int a[] = { 5, 12, 67, 9, 16 };
int n = 5;
Hash h (7);
for (int i = 0; i < n; i++)
h.insertItem (a[i]);
h.deleteItem (12);
h.displayHash ();
return 0;
}輸出
0 1 2 --> 9 --> 16 3 4 --> 67 5 --> 5 6
更新於: 2019年9月19日
2K+ 瀏覽量
廣告