哈希表/散列表-創(chuàng)新互聯(lián)
哈希表/散列表，是根據(jù)關(guān)鍵字（key）直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。
構(gòu)造哈希表的常用方法：
直接地址法---取關(guān)鍵字的某個線性函數(shù)為散列地址，Hash(Key) = Key或Hash(key) = A*Key + B,
A,B為常數(shù)。
除留余數(shù)法---取關(guān)鍵值被某個不大于散列表長m的數(shù)p除后的所得的余數(shù)為散列地址。
Hash(key) = key % p。
若采用直接地址法（Hash(Key) = Key）存在一定的缺陷。
當Key值特別大時，而Key之前的數(shù)很少，就會造成空間浪費。大多時候采取除留余數(shù)法。
哈希沖突/哈希碰撞
不同的Key值經(jīng)過哈希函數(shù)Hash(Key)處理以后可能產(chǎn)生相同的哈希地址，我們稱這種情況為哈希沖突。任何的散列函數(shù)都不能避免產(chǎn)生沖突。
散列表的載荷因子定義為a = 填入表中元素的個數(shù)/散列表的長度
載荷因子越大，沖突的可能性就越大。
解決沖突的辦法：
（1）線性探測
（2）二次探測
#pragma once
#include <iostream>
#include <string>
using namespace std;
enum State
{
EMPTY,
DELETE,
EXITS,
};
//以key形式實現(xiàn)線性探測
template <class T>
class HashTable
{
public:
HashTable(T capacity = 10)
:_tables(new T[capacity])
,_states(new State[capacity])
,_capacity(capacity)
,_size(0)
{
for(size_t i=0;i < _capacity;++i)
{
_states[i] = EMPTY;
}
}
~HashTable()
{
delete[] _tables;
delete[] _states;
_tables = NULL;
_states = NULL;
}
HashTable(const HashTable<T>& ht) //拷貝構(gòu)造
{
_tables = new T[ht._capacity];
_states = new State[ht._capacity];
for(size_t i=0;i<ht._capacity;++i)
{
if(ht._tables[i] != EMPTY)
{
_tables[i] = ht._tables[i];
_states[i] = ht._states[i];
}
}
_capacity = ht._capacity;
_size = ht._size;
}
//HashTable<T>& operator=(const HashTable<T>& ht) //賦值操作符重載
//{
// if(this != &ht)
// {
// delete[] _tables;
// delete[] _states;
// _tables = new T[ht._capacity];
// _states = new State[ht._capacity];
// for(size_t i=0;i<ht._capacity;++i)
// {
// if(ht._tables[i] != EMPTY)
// {
// _tables[i] = ht._tables[i];
// _states[i] = ht._states[i];
// }
// }
// _capacity = ht._capacity;
// _size = ht._size;
// }
// return *this;
//}
//現(xiàn)代寫法
HashTable<T>& operator=(HashTable<T> ht) //賦值操作符重載
{
this->Swap(ht);
return *this;
}
public:
bool Insert(const T& key) //插入
{
_CheckCapacity();
size_t index = HashFunc(key);
while(_states[index] == EXITS)
{
if(_tables[index] == key) //冗余
{
return false;
}
++index;
if(index == _capacity) //到達哈希表尾部
{
index = 0;
}
}
_tables[index] = key;
_states[index] = EXITS;
++_size;
return true;
}
bool Find(const T& key) //查找
{
size_t index = HashFunc(key);
size_t start = index;
while(_states[index] == EXITS)
{
if(_tables[index] == key)
{
return true;
}
++index;
if(index == _capacity)
{
index = 0;
}
if(start == index) //哈希表查完
{
return false;
}
}
return false;
}
bool Remove(const T& key) //刪除
{
size_t index = HashFunc(key);
size_t start = index;
while(_states[index] == EXITS)
{
if(_tables[index] == key)
{
_states[index] = DELETE;
return true;
}
++index;
if(index == _capacity) //到達哈希表的尾部
{
index = 0;
}
if(start == index) //哈希表查完
{
return false;
}
}
return false;
}
public:
size_t HashFunc(const T& key) //哈希函數(shù)
{
return key%10;
}
void _CheckCapacity() //檢查容量
{
if(_size*10 % _capacity == 7) //載荷因子
{
HashTable<T> tmp(2*_capacity);
for(size_t i=0;i<_capacity;++i)
{
if(_states[i] == EXITS)
{
tmp.Insert(_tables[i]);
}
}
Swap(tmp);
}
}
void Swap(HashTable<T>& ht)
{
swap(_tables,ht._tables);
swap(_states,ht._states);
swap(_size,ht._size);
swap(_capacity,ht._capacity);
}
void Print()
{
for(size_t i=0;i<_capacity;++i)
{
cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<" ";
}
cout<<endl;
}
private:
T* _tables; //哈希表
State* _states; //狀態(tài)表
size_t _size; //數(shù)據(jù)的個數(shù)
size_t _capacity; //容量
};
//以key形式實現(xiàn)二次探測
//enum State
//{
// EMPTY,
// DELETE,
// EXITS,
//};
//template <class T>
//class HashTableSecond
//{
//public:
// HashTableSecond(T capacity = 10)
// :_tables(new T[capacity])
// ,_states(new State[capacity])
// ,_capacity(capacity)
// ,_size(0)
// {
// for(size_t i=0;i < _capacity;++i)
// {
// _states[i] = EMPTY;
// }
// }
//
// ~HashTableSecond()
// {
// delete[] _tables;
// delete[] _states;
// _tables = NULL;
// _states = NULL;
// }
//
// HashTableSecond(const HashTableSecond& ht) //拷貝構(gòu)造
// {
// _tables = new T[ht._capacity];
// _states = new State[ht._capacity];
// for(size_t i=0;i<ht._capacity;++i)
// {
// if(ht._tables[i] != EMPTY)
// {
// _tables[i] = ht._tables[i];
// _states[i] = ht._states[i];
// }
// }
// _capacity = ht._capacity;
// _size = ht._size;
// }
//
// HashTableSecond& operator=(const HashTableSecond& ht) //賦值操作符重載
// {
// if(this != &ht)
// {
// delete[] _tables;
// delete[] _states;
// _tables = new T[ht._capacity];
// _states = new State[ht._capacity];
// for(size_t i=0;i<ht._capacity;++i)
// {
// if(ht._tables[i] != EMPTY)
// {
// _tables[i] = ht._tables[i];
// _states[i] = ht._states[i];
// }
// }
// _capacity = ht._capacity;
// _size = ht._size;
// }
// return *this;
// }
//
//public:
// bool Insert(const T& key) //插入
// {
// _CheckCapacity();
// size_t start = HashFunc(key);
// size_t index = start;
// size_t i = 1;
// while(_states[index] == EXITS)
// {
// if(_tables[index] == key)
// {
// return false;
// }
// index = start + i * i;
// ++i;
// index %= _capacity;
// }
// _tables[index] = key;
// _states[index] = EXITS;
// ++_size;
// return true;
// }
// bool Find(const T& key) //查找
// {
// size_t start = HashFunc(key);
// size_t index = start;
// size_t i = 1;
// while(_states[index] == EXITS)
// {
// if(_tables[index] == key)
// {
// return true;
// }
// index = start + i * i;
// ++i;
// index %= _capacity;
// }
// return false;
// }
// bool Remove(const T& key) //刪除
// {
// size_t start = HashFunc(key);
// size_t index = start;
// size_t i = 1;
// while(_states[index] == EXITS)
// {
// if(_tables[index] == key)
// {
// _states[index] = DELETE;
// return true;
// }
// index = start + i * i;
// ++i;
// index %= _capacity;
// }
// return false;
// }
//public:
// size_t HashFunc(const T& key) //哈希函數(shù)
// {
// return key%10;
// }
//
// void _CheckCapacity() //檢測容量
// {
// if(_size*10 % _capacity == 7)
// {
// HashTableSecond<T> tmp(2*_capacity);
// for(size_t i=0;i<_capacity;++i)
// {
// if(_states[i] == EXITS)
// {
// tmp.Insert(_tables[i]);
// }
// }
// Swap(tmp);
// }
// }
//
// void Swap(HashTableSecond<T>& ht)
// {
// swap(_tables,ht._tables);
// swap(_states,ht._states);
// swap(_size,ht._size);
// swap(_capacity,ht._capacity);
// }
//
// void Print()
// {
// for(size_t i=0;i<_capacity;++i)
// {
// cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<" ";
// }
// cout<<endl;
// }
//private:
// T* _tables; //哈希表
// State* _states; //狀態(tài)表
// size_t _size; //數(shù)據(jù)的個數(shù)
// size_t _capacity; //容量
//};
//以key/value形式實現(xiàn)二次探測，支持字典查詢
//enum State
//{
// EMPTY,
// DELETE,
// EXITS,
//};
template <class T,class K>
struct HashTableNode //節(jié)點
{
T key;
K value;
};
template <class T>
struct __HashFunc //重載()
{
size_t operator()(const T& key)
{
return key;
}
};
template<>
struct __HashFunc<string> //特化
{
size_t operator()(const string& key)
{
size_t hash = 0;
for(size_t i=0;i<key.size();++i)
{
hash += key[i];
}
return hash;
}
};
template <class T,class K,class HashFunc = __HashFunc<T> >
class HashTableSecond
{
public:
HashTableSecond(size_t capacity = 10)
:_tables(new HashTableNode<T,K>[capacity])
,_states(new State[capacity])
,_capacity(capacity)
,_size(0)
{
for(size_t i=0;i < _capacity;++i)
{
_states[i] = EMPTY;
}
}
~HashTableSecond()
{
delete[] _tables;
delete[] _states;
_tables = NULL;
_states = NULL;
}
public:
bool Insert(const T& key,const K& value) //插入
{
_CheckCapacity();
size_t start = __HashFunc(key);
size_t index = start;
size_t i = 1;
while(_states[index] == EXITS)
{
if(_tables[index].key == key)
{
return false;
}
index = start + i * i;
++i;
index %= _capacity;
}
_tables[index].key = key;
_tables[index].value = value;
_states[index] = EXITS;
++_size;
return true;
}
HashTableNode<T,K>* Find(const T& key) //查找
{
size_t start = __HashFunc(key);
size_t index = start;
size_t i = 1;
while(_states[index] == EXITS)
{
if(_tables[index].key == key)
{
return &(_tables[index]);
}
index = start + i * i;
++i;
index %= _capacity;
}
return NULL;
}
bool Remove(const T& key) //刪除
{
size_t start = __HashFunc(key);
size_t index = start;
size_t i = 1;
while(_states[index] == EXITS)
{
if(_tables[index].key == key)
{
_states[index] = DELETE;
return true;
}
index = start + i * i;
++i;
}
return false;
}
public:
size_t __HashFunc(const T& key) //哈希函數(shù)
{
HashFunc hfun;
return hfun(key)%_capacity;
}
void _CheckCapacity() //檢測容量
{
if(_size*10 % _capacity == 7)
{
HashTableSecond<T,K> tmp(2*_capacity);
for(size_t i=0;i<_capacity;++i)
{
if(_states[i] == EXITS)
{
tmp.Insert(_tables[i].key,_tables[i].value);
}
}
Swap(tmp);
}
}
void Swap(HashTableSecond<T,K>& ht)
{
swap(_tables,ht._tables);
swap(_states,ht._states);
swap(_size,ht._size);
swap(_capacity,ht._capacity);
}
void Print()
{
for(size_t i=0;i<_capacity;++i)
{
cout<<"["<<_tables[i].key<<","<<_tables[i].value<<"]"<<" ";
}
cout<<endl;
}
private:
HashTableNode<T,K>* _tables; //哈希表
State* _states; //狀態(tài)表
size_t _size; //數(shù)據(jù)的個數(shù)
size_t _capacity; //容量
};另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
網(wǎng)站題目：哈希表/散列表-創(chuàng)新互聯(lián)
標題鏈接：http://jinyejixie.com/article34/dpphpe.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、響應式網(wǎng)站、微信小程序、搜索引擎優(yōu)化、營銷型網(wǎng)站建設(shè)、移動網(wǎng)站建設(shè)
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
- 網(wǎng)站制作我的15年都在關(guān)注你，BBS你真的老了? 2022-08-13
- 企業(yè)網(wǎng)站制作中員工個人空間與公共空間的設(shè)計與管理 2021-07-19
- 網(wǎng)站制作用戶體驗度如何提高 2021-05-13
- 怎樣才能提高企業(yè)網(wǎng)站制作競爭能力呢 2021-10-27
- 福州網(wǎng)站建設(shè)_福州網(wǎng)站制作公司怎么挑選 2021-11-13
- 英文網(wǎng)站制作的相關(guān)注意事項有哪些? 2015-11-20
- 成都網(wǎng)站制作的核心原則有哪些？ 2022-07-16
- 成都網(wǎng)站制作什么樣的網(wǎng)頁設(shè)計才是最好的 2013-10-08
- 寵物用品公司網(wǎng)站制作怎樣做才能見到效果 2023-02-16
- 品牌網(wǎng)站制作常見的布局方式 2022-03-22
- 中小企業(yè)建站費用由哪些因素決定？ 2016-05-07
- 網(wǎng)站制作中如何讓網(wǎng)頁文本看上去更舒服 2023-02-25