哈希是一種算法，將指定的數(shù)據(jù)按一定規(guī)律映射到一段空間內(nèi)，又可以按照這種規(guī)律對(duì)它的值進(jìn)行相應(yīng)的操作，這一段空間可以稱(chēng)作哈希表，它的的查找速度要快于線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)，同時(shí)也快于表格隊(duì)列等，所以它具有獨(dú)特的優(yōu)勢(shì)，一般將哈希算法用于快速查找和加密算法。
創(chuàng)新互聯(lián)建站專(zhuān)注于禹城企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站建設(shè),商城網(wǎng)站制作。禹城網(wǎng)站建設(shè)公司,為禹城等地區(qū)提供建站服務(wù)。全流程按需策劃，專(zhuān)業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)建站專(zhuān)業(yè)和態(tài)度為您提供的服務(wù)
對(duì)于最簡(jiǎn)單的哈希表，里面設(shè)置一個(gè)key，它決定將這個(gè)值存于哈希表的什么位置，同時(shí)把每個(gè)設(shè)置一個(gè)狀態(tài)，如果有插入數(shù)據(jù)就將其設(shè)置為EXITS，其他操作同理，現(xiàn)在可以實(shí)現(xiàn)最簡(jiǎn)單的哈希表。
namespace First
{
enum State
{
EMPTY,
DELETE,
EXITS
};
template
class HashTable
{
public:
HashTable(size_t capacity = 10)//構(gòu)造
:_capacity(capacity)
, _tables(new T[_capacity])
, _states(new State[_capacity])
, _size(0)
{
for (int i = 0; i < _capacity; i++)//最初始得狀態(tài)置成空的
{
_states[i] = EMPTY;
}
}
~HashTable()//析構(gòu)
{
delete[] _tables;
delete[] _states;
}
HashTable(const HashTable
:_capacity(h._capacity)
, _tables(new T[h._capacity])
, _states(new State[h._capacity])
, _size(h._size)
{
for (int i = 0; i < h._capacity; i++)
{
_tables[i] = h._tables[i];
_states[i] = h._states[i];
}
}
HashTable& operator=(HashTable
{
if (this != &h)
{
swap(_tables, h._tables);
swap(_states, h._states);
swap(_capacity, h._capacity);
swap(_size, h._size);
}
return *this;
}
bool Insert(const T& key)//插入
{
if (_size == _capacity)
{
cout << "HashTable full" << endl;
return false;
}
int index = HashFunc(key);
int start = index;
while (_states[index] == EXITS)//往后線(xiàn)形探測(cè)
{
if (_tables[index] == key)//有相等的
{
return false;
}
index++;
if (index == _capacity)//最后一個(gè)
{
index = 0;
}
if (index == start)//找了一圈沒(méi)找到
{
return false;
}
}
_tables[index] = key;
_states[index] = EXITS;
_size++;
}
bool Find(const T& key)//查找
{
int index = HashFunc(key);
int start = index;
while (_states[index] != EMPTY)
{
if (_tables[index] == key)
{
if (_states[index] != DELETE)
{
cout << "find succees" << endl;
return true;
}
else
{
cout << "find fail" << endl;
return false;
}
}
index++;
if (index == _capacity)
{
index = 0;
}
if (start == index)
{
cout << "find fail" << endl;
return false;
}
}
cout << "find fail" << endl;
return false;
}
bool Remove(const T& key)///刪除
{
int index = HashFunc(key);
int start = index;
while (_states[index] != EMPTY)
{
if (_tables[index] == key)
{
if (_states[index] != DELETE)
{
cout << "delete key" << endl;
_states[index] = DELETE;
return true;
}
else
{
cout << "delete fail" << endl;
return false;
}
}
index++;
if (index == _capacity)
{
index = 0;
}
if (start == index)
{
return false;
}
}
cout << "delete fail" << endl;
return true;
}
void Print()//打印哈希表
{
for (int i = 0; i < _capacity; i++)
{
cout << '[' << _tables[i] << ',' << _states[i] << ']' << ' ';
}
cout << endl;
}
protected:
int HashFunc(const T& key)
{
return key%_capacity;
}
private:
size_t _capacity;
T* _tables;
State* _states;
size_t _size;
};
}
/**************************************/
從上面的代碼可以看出，這個(gè)哈希表并不適用于實(shí)際，因?yàn)槭紫人且粋€(gè)靜態(tài)的，如果存入的key值過(guò)多就會(huì)造成越界訪(fǎng)問(wèn)，同時(shí)用的是線(xiàn)性探測(cè)方法，這樣降低了cpu的訪(fǎng)問(wèn)命中率，現(xiàn)在可以實(shí)現(xiàn)一種動(dòng)態(tài)的而且隨意設(shè)置負(fù)載因子的功能。
namespace Second//因?yàn)橛胸?fù)載因子的限制，可以提高cpu訪(fǎng)問(wèn)命中率
{
enum State
{
EMPTY,
DELETE,
EXITS
};
template
class HashTable
{
public:
HashTable(size_t capacity = 30)//構(gòu)造
:_capacity(capacity)
, _tables(new T[_capacity])
, _states(new State[_capacity])
, _size(0)
{
for (int i = 0; i < _capacity; i++)//最初始得狀態(tài)置成空的
{
_states[i] = EMPTY;
}
}
~HashTable()//析構(gòu)
{
delete[] _tables;
delete[] _states;
}
HashTable(const HashTable
:_capacity(h._capacity)
, _tables(new T[h._capacity])
, _states(new State[h._capacity])
, _size(h._size)
{
for (int i = 0; i { _tables[i] = h._tables[i]; _states[i] = h._states[i]; } } HashTable& operator=(HashTable { if (this != &h) { swap(_tables, h._tables); swap(_states, h._states); swap(_capacity, h._capacity); swap(_size, h._size); } return *this; } //bool Insert(const T& key)//插入（線(xiàn)性探測(cè)） //{ //_CheckCapacity(); //int index = _HashFunc(key); //int start = index; //while (_states[index]==EXITS) //{ //if (_tables[index] == key) //{ //return false; //} //index++; //if (index == _capacity) //{ //index = 0; //} //if (index == start) //{ //return false; //} // //} //_tables[index] = key; //_states[index] = EXITS; //_size++; //} bool Insert(const T& key)//插入（二次探測(cè),即某個(gè)數(shù)的二次方,這樣數(shù)據(jù)存著更稀疏） { _CheckCapacity(); int index = _HashFunc(key); int start = index; int i = 0; while (_states[index]==EXITS) { if (_tables[index] == key) { return false; } index = _HashFuncT(index, ++i); if (start = index) { return false; } if (index == _capacity) { index = 0; } } _tables[index] = key; _states[index] = EXITS; _size++; } bool Find(const T& key)//查找 { int index = _HashFunc(key); int start = index; int i = 0; while (_states[index]!=EMPTY) { if (_tables[index] == key) { if (_states[index] != DELETE) { cout << "find success" << endl; return true; } else { cout << "find fail" << endl; return false; } } index = _HashFuncT(index, ++i); if (start = index) { cout << "find fail" << endl; return false; } if (index == _capacity) { index = 0; } } cout << "find fail" << endl; return false; } bool Remove(const T& key)///刪除 { int index = _HashFunc(key); int start = index; int i = 0; while (_states[index] == EXITS) { if (_tables[index] == key) { _states[index] = DELETE; _size--; return true; } index = _HashFuncT(index, ++i); if (start == index) { return false; } if (index == _capacity) { index = 0; } } return false; } void Print()//打印哈希表 { for (int i = 0; i < _capacity; i++) { cout << '[' << _tables[i] << ',' << _states[i] << ']' << ' '; } cout << endl; } protected: int _HashFuncT(int index,int i) { return (index + i*i) % _capacity; } int _HashFunc(const T& key) { return key%_capacity; } void _CheckCapacity()//檢查容量 { if ((10 * _size)/ _capacity == 6)//負(fù)載因子設(shè)為0.6 { HashTable for (int i = 0; i < _capacity; i++) { if (_states[i]==EXITS) { tmp.Insert(_tables[i]); } } _swap(tmp); } } void _swap(HashTable { swap(_tables, h._tables); swap(_states, h._states); swap(_capacity, h._capacity); swap(_size, h._size); } private: size_t _capacity; T* _tables; State* _states; size_t _size; }; } /****************************************/ 上面的代碼對(duì)于key形式的相對(duì)第一種已經(jīng)比較健全了。現(xiàn)在可以利用哈希算法可以實(shí)現(xiàn)一種key/value形式的功能，可以支持字典功能，key是一個(gè)信息，同時(shí)value是key的一個(gè)附帶信息，比如說(shuō)key為學(xué)號(hào)，那么班級(jí)就是附帶的信息value，例如還有簡(jiǎn)單的英漢字典形式，現(xiàn)進(jìn)行簡(jiǎn)單的實(shí)現(xiàn)。 namespace Third//支持字典形式的 { enum State { EMPTY, DELETE, EXITS }; template struct HashTableNode { HashTableNode() {} HashTableNode(const T& key, const V& value) :_key(key) , _value(value) {} T _key; V _value; }; template struct __HashFunc { size_t operator()(const T& key) { return key; } }; //實(shí)現(xiàn)key，value形式，并且是二次探測(cè)的 template class Dictionary { public: Dictionary(size_t capacity=10) :_capacity(capacity) , _tables(new HashTableNode , _states(new State[_capacity]) ,_size(0) { for (int i = 0; i < _capacity; i++) { _states[i] = EMPTY;//將最開(kāi)始的狀態(tài)置為空 } } ~Dictionary() { delete[] _tables; delete[] _states; } bool Insert(const T& key,const V& value) { _CheckCapacity(); int index = _HashFunonce(key); int start = index; int i = 0; while (_states[index] == EXITS) { if (_tables[index]._key == key) { return false; } index = _HashFuntwice(index, ++i); if (index == _capacity) { index = 0; } if (index == start) { return false; } } _tables[index] = HashTableNode _states[index] = EXITS; _size++; return true; } HashTableNode { int index = _HashFunonce(key); int start = index; int i = 0; while (_states[index]==EXITS) { if (_tables[index]._key == key) { cout << "find success" << endl; return _tables+index; } index = _HashFuntwice(index, ++i); if (start == index) { cout << "find fail" << endl; return NULL; } } cout << "find fail" << endl; return NULL; } bool Remove(const T& key) { int index = _HashFunonce(key); int start = index; int i = 0; while (_states[index]!=EMPTY) { if (_tables[index]._key == key) { if (_states[index]!=DELETE) { _states[index] = DELETE; _size--; return true; } else { return false; } } index = _HashFuntwice(index, ++i); if (index == start) { return false; } } return false; } void Print() { for (int i = 0; i < _capacity; i++) { cout << "[" << _tables[i]._key << "," << _tables[i]._value <<","<< _states[i]<<"]" << " "; } cout << endl; } protected: void _CheckCapacity()//將負(fù)載因子設(shè)為0.6 { if (_size * 10 / _capacity == 6) { Dictionary for (int i = 0; i < _capacity; i++) { if (_states[i] == EXITS) { tmp.Insert(_tables[i]._key,_tables[i]._value); } } _Swap(tmp); } } void _Swap(Dictionary { swap(_tables, tmp._tables); swap(_states, tmp._states); swap(_capacity, tmp._capacity); swap(_size, tmp._size); } size_t _HashFunonce(const T& key) { return key %_capacity; } size_t _HashFuntwice(int index,int i)//獲取二次探測(cè)的下標(biāo) { return (index + i*i) % _capacity; } private: size_t _capacity; HashTableNode State* _states; size_t _size; }; } void test3()//二次探測(cè)，負(fù)載因子，實(shí)現(xiàn)字典的功能 { /*Third::Dictionary h2.Insert(10, "c語(yǔ)言基礎(chǔ)"); h2.Insert(59, "c++基礎(chǔ)"); h2.Insert(9, "數(shù)據(jù)結(jié)構(gòu)"); h2.Insert(19, "Linux"); h2.Insert(18, "網(wǎng)絡(luò)編程");*/ Third::Dictionary h2.Insert(10, 1); h2.Insert(59, 2); h2.Insert(9, 3); h2.Insert(19,4); h2.Insert(18, 5); //h2.Print(); cout< //h2.Remove(9); //h2.Remove(19); //h2.Remove(10); //h2.Print(); } 上述就是對(duì)哈希算法的簡(jiǎn)單應(yīng)用。
網(wǎng)頁(yè)標(biāo)題：哈希表的靜態(tài)，動(dòng)態(tài)，以及key/value形式
URL鏈接：http://weahome.cn/article/jepjsg.html
重慶分公司
重慶分公司
