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