溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了c#如何實現(xiàn)哈希表線性探測，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
HashTable-散列表/哈希表，是根據(jù)關(guān)鍵字（key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。
它通過一個關(guān)鍵值的函數(shù)將所需的數(shù)據(jù)映射到表中的位置來訪問數(shù)據(jù)，這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
哈希沖突/哈希碰撞
不同的Key值經(jīng)過哈希函數(shù)Hash(Key)處理以后可能產(chǎn)生相同的值哈希地址，我們稱這種情況為哈希沖突。任意的散列函數(shù)都不能避免產(chǎn)生沖突。
我給大家介紹的是哈希表的線性探測，線性探測的基本思路：
1.用一個數(shù)據(jù)除以散列表的長度，余數(shù)是多少，就把這個數(shù)放在散列表下標(biāo)相同的地方。
2.如果發(fā)生哈希沖突，就看下一個位置是否有數(shù)據(jù)，一直到?jīng)]有哈希沖突，就把這個數(shù)據(jù)放在此位置。
3.如果已經(jīng)試探到最后一個位置，但前面還有位置沒有試探，那么我們就從開始位置繼續(xù)試探，直到全部位置試探成功。
實現(xiàn)代碼：
Hash.h中
//哈希表中存放數(shù)據(jù)的狀態(tài)
enum State
{
EMPTY,//沒有數(shù)據(jù)
DELETE,//刪除數(shù)據(jù)后
EXIST//有數(shù)據(jù)
};
template <class K>
class HashTable
{
public:
//構(gòu)造函數(shù)
HashTable()
:_table(NULL)
, state(NULL)
, _size(0)
, _capatity(0)
{}
//構(gòu)造函數(shù)
HashTable(size_t size)
:_table(new K[size])
, _state(new State[size])
, _capatity(size)
, _size(0)
{
for (int i = 0; i < _capatity; i++)
{
_state[i] = EMPTY;
}
}
//插入數(shù)據(jù)
bool Insert(const K& key)
{
//檢測靜態(tài)哈希表是否已滿
if (_size == _capatity)
{
cout << "哈希表已滿!" << endl;
return false;
}
int index = _HashFunc(key);
while (_state[index] == EXIST)
{
index++;//哈希沖突，找下一個位置
//最后一個位置有數(shù)據(jù)，從頭開始找位置
if (index == _capatity)
{
index = 0;
}
}
//哈希不沖突，直接放數(shù)據(jù)
_table[index] = key;
_state[index] = EXIST;
_size++;
return true;
}
//查找
int Find(const K& key)
{
int index = _HashFunc(key);
while (_state[index] != EMPTY)
{
//找到元素
if (_table[index] == key&&_state[index] == EXIST)
{
return index;
}
//如果算出的位置，不是要找的元素，index++;
index++;
//最后一個位置不是，就從頭開始找
if (index == _capatity)
{
index = 0;
}
}
return -1;
}
void print()
{
for (int i = 0; i < _capatity; i++)
{
if (_state[i] == EXIST)
{
printf("[%d]EXIST:%d\n",i, _table[i]);
}
else if (_state[i] == DELETE)
{
printf("[%d]DELETE:NULL\n", i, _table[i]);
}
else
{
printf("[%d]EMPTY:NULL\n", i);
}
}
}
//刪除某一位置元素
bool Remove(const K& key)
{
int index = Find(key);//找到這個元素
//刪除這個元素
if (index != -1)
{
_state[index] = DELETE;
_size--;
return true;
}
return false;
}
protected:
//算出數(shù)據(jù)在哈希表中的位置（哈希不沖突）
int _HashFunc(const K& key)
{
return key%_capatity;
}
protected:
K* _table;//數(shù)組
State* _state;//狀態(tài)數(shù)組
size_t _size;//數(shù)組大小
size_t _capatity;//數(shù)組的容量
};test.cpp中
#include <iostream>
using namespace std;
#include "Hash.h"
void Test()
{
HashTable<int> ht(10);
ht.Insert(24);
ht.Insert(20);
ht.Insert(36);
ht.Insert(23);
ht.Insert(30);
ht.print();
int ret = ht.Find(30);
cout << "下標(biāo)為："<<ret << endl;
ht.Remove(30);
ht.print();
}
int main()
{
Test();
system("pause");
return 0;
}上面的代碼有不完善的地方，我們在處理哈希問題是，有這樣的問題存在。散列表載荷因子的問題。
載荷因子=填入表中的元/散列表的長度
載荷因子與“填在表中元素的個數(shù)”成正比，載荷因子越大，填入表中的元素越多，產(chǎn)生沖突的可能性越大。反之，則相反。
載荷因子應(yīng)該限制在0.7—0.8以下，超過0.8，查找CPU緩存不命中，效率就比較低，所以一般載荷因子為0.8就應(yīng)該擴(kuò)容。
所以上面的檢查容量應(yīng)該稍微改一下
代碼：
bool Insert(const K& key)
{
//檢測靜態(tài)哈希表是否已滿
/*if (_size == _capatity)
{
cout << "哈希表已滿!" << endl;
return false;
}*/
//考慮到載荷因子在0.7~0.8一下比較好，這樣檢查容量比較好
if (10 * _size >= 8 * _capatity)
{
_CheckCapatity();
}
int index = _HashFunc(key);
while (_state[index] == EXIST)
{
index++;//哈希沖突，找下一個位置
//最后一個位置有數(shù)據(jù)，從頭開始找位置
if (index == _capatity)
{
index = 0;
}
}
//哈希不沖突，直接放數(shù)據(jù)
_table[index] = key;
_state[index] = EXIST;
_size++;
return true;
}
//交換
void _Swap(HashTable<K> tmp)
{
swap(_size, tmp._size);
swap(_capatity, tmp._capatity);
swap(_state, tmp._state);
swap(_table, tmp._table);
}
//檢查容量
void _CheckCapatity()
{
HashTable<K> tmp(2 * _capatity);
for (int i = 0; i < _capatity; i++)
{
tmp.Insert(_table[i]);
}
_Swap(tmp);
}上面只能存儲數(shù)據(jù)，如果是字符串，怎么辦哪？所以我們想處理字符串，可以寫一個自定義類型，然后利用特化來處理字符串。
代碼如下：
#include <string>
//哈希表中存放數(shù)據(jù)的狀態(tài)
enum State
{
EMPTY,//沒有數(shù)據(jù)
DELETE,//刪除數(shù)據(jù)后
EXIST//有數(shù)據(jù)
};
template <class K>
//處理
struct DefaultFunc
{
size_t operator()(const K& key)
{
return key;
}
};
//自定義類型
template<>
struct DefaultFunc<string>//特化
{
size_t value = 0;
size_t operator()(const string& str)
{
for (int i = 0; i < str.size(); i++)
{
value += str[i];
}
return value;
}
};
template <class K, template <class>class HashFunc = DefaultFunc>
class HashTable
{
public:
//構(gòu)造函數(shù)
HashTable()
:_table(NULL)
, state(NULL)
, _size(0)
, _capatity(0)
{}
//構(gòu)造函數(shù)
HashTable(size_t size)
:_table(new K[size])
, _state(new State[size])
, _capatity(size)
, _size(0)
{
for (int i = 0; i < _capatity; i++)
{
_state[i] = EMPTY;
}
}
//插入數(shù)據(jù)
bool Insert(const K& key)
{
//檢測靜態(tài)哈希表是否已滿
/*if (_size == _capatity)
{
cout << "哈希表已滿!" << endl;
return false;
}*/
//考慮到載荷因子在0.7~0.8一下比較好，這樣檢查容量比較好
if (10 * _size >= 8 * _capatity)
{
_CheckCapatity();
}
int index = _HashFunc(key);
while (_state[index] == EXIST)
{
index++;//哈希沖突，找下一個位置
//最后一個位置有數(shù)據(jù)，從頭開始找位置
if (index == _capatity)
{
index = 0;
}
}
//哈希不沖突，直接放數(shù)據(jù)
_table[index] = key;
_state[index] = EXIST;
_size++;
return true;
}
//查找
int Find(const K& key)
{
int index = _HashFunc(key);
while (_state[index] != EMPTY)
{
//找到元素
if (_table[index] == key&&_state[index] == EXIST)
{
return index;
}
//如果算出的位置，不是要找的元素，index++;
index++;
//最后一個位置不是，就從頭開始找
if (index == _capatity)
{
index = 0;
}
}
return -1;
}
void print()
{
/*for (int i = 0; i < _capatity; i++)
{
if (_state[i] == EXIST)
{
printf("[%d]EXIST:%d\n",i, _table[i]);
}
else if (_state[i] == DELETE)
{
printf("[%d]DELETE:NULL\n", i, _table[i]);
}
else
{
printf("[%d]EMPTY:NULL\n", i);
}
}*/
for (int i = 0; i < _capatity; i++)
{
if (_state[i] == EXIST)
{
cout << i <<"-"<< "EXIST:" << _table[i] << endl;
}
else if (_state[i] == DELETE)
{
cout << i <<"-"<< "DELETE:" << "NULL" << endl;
}
else
{
cout << i <<"-"<< "EMPTY:" << "NULL" << endl;
}
}
}
//刪除某一位置元素
bool Remove(const K& key)
{
int index = Find(key);//找到這個元素
//刪除這個元素
if (index != -1)
{
_state[index] = DELETE;
_size--;
return true;
}
return false;
}
protected:
//算出數(shù)據(jù)在哈希表中的位置（哈希不沖突）
/*int _HashFunc(const K& key)
{
return key%_capatity;
}*/
int _HashFunc(const K& key)
{
HashFunc<K> ht;
return ht(key) % _capatity;
}
//交換
void _Swap(HashTable<K> tmp)
{
swap(_size, tmp._size);
swap(_capatity, tmp._capatity);
swap(_state, tmp._state);
swap(_table, tmp._table);
}
//檢查容量
void _CheckCapatity()
{
HashTable<K> tmp(2 * _capatity);
for (int i = 0; i < _capatity; i++)
{
tmp.Insert(_table[i]);
}
_Swap(tmp);
}
protected:
K* _table;//數(shù)組
State* _state;//狀態(tài)數(shù)組
size_t _size;//數(shù)組大小
size_t _capatity;//數(shù)組的容量
};test.cpp中
#include <iostream>
using namespace std;
#include "Hash.h"
//void Test()
//{
// HashTable<int> ht(10);
// ht.Insert(24);
// ht.Insert(20);
// ht.Insert(36);
// ht.Insert(23);
// ht.Insert(30);
// ht.print();
//
// int ret = ht.Find(30);
// cout << "下標(biāo)為："<<ret << endl;
//
// ht.Remove(30);
// ht.print();
//
//}
void Test1()
{
HashTable<string> ht(10);
ht.Insert("杭哥");
ht.Insert("張哥");
ht.Insert("詹姐");
ht.Insert("亮哥");
ht.Insert("蛋蛋");
ht.print();
int ret = ht.Find("蛋蛋");
cout << "下標(biāo)為：" << ret << endl;
ht.Remove("亮哥");
ht.print();
}
int main()
{
//Test();
Test1();
system("pause");
return 0;
}感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“c#如何實現(xiàn)哈希表線性探測”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼