哈希表的靜態(tài)，動(dòng)態(tài)，以及key/value形式

   哈希是一種算法，將指定的數(shù)據(jù)按一定規(guī)律映射到一段空間內(nèi)，又可以按照這種規(guī)律對(duì)它的值進(jìn)行相應(yīng)的操作，這一段空間可以稱作哈希表，它的的查找速度要快于線性的數(shù)據(jù)結(jié)構(gòu)，同時(shí)也快于表格隊(duì)列等，所以它具有獨(dú)特的優(yōu)勢，一般將哈希算法用于快速查找和加密算法。

   對(duì)于最簡單的哈希表，里面設(shè)置一個(gè)key，它決定將這個(gè)值存于哈希表的什么位置，同時(shí)把每個(gè)設(shè)置一個(gè)狀態(tài)，如果有插入數(shù)據(jù)就將其設(shè)置為EXITS，其他操作同理，現(xiàn)在可以實(shí)現(xiàn)最簡單的哈希表。

namespace First

{

enum State

{

EMPTY,

DELETE,

EXITS

};

template <typename T>

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<T>& h)//拷貝構(gòu)造

:_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<T> h)//賦值運(yùn)算符重載

{

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)//往后線形探測

{

if (_tables[index] == key)//有相等的

{

return false;

}

index++;

if (index == _capacity)//最后一個(gè)

{

index = 0;

}

if (index == start)//找了一圈沒找到

{

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值過多就會(huì)造成越界訪問，同時(shí)用的是線性探測方法，這樣降低了cpu的訪問命中率，現(xiàn)在可以實(shí)現(xiàn)一種動(dòng)態(tài)的而且隨意設(shè)置負(fù)載因子的功能。

namespace Second//因?yàn)橛胸?fù)載因子的限制，可以提高cpu訪問命中率

{

enum State

{

EMPTY,

DELETE,

EXITS

};

template <typename T>

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<T>& h)//拷貝構(gòu)造

:_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<T> h)//賦值運(yùn)算符重載

{

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)//插入（線性探測）

//{

//_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)//插入（二次探測,即某個(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<T> tmp(2 * _capacity);

for (int i = 0; i < _capacity; i++)

{

if (_states[i]==EXITS)

{

tmp.Insert(_tables[i]);

}

}

_swap(tmp);

}

}

void _swap(HashTable<T> h)

{

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)比較健全了?，F(xiàn)在可以利用哈希算法可以實(shí)現(xiàn)一種key/value形式的功能，可以支持字典功能，key是一個(gè)信息，同時(shí)value是key的一個(gè)附帶信息，比如說key為學(xué)號(hào)，那么班級(jí)就是附帶的信息value，例如還有簡單的英漢字典形式，現(xiàn)進(jìn)行簡單的實(shí)現(xiàn)。

namespace Third//支持字典形式的

{

enum State

{

EMPTY,

DELETE,

EXITS

};

template<class T,class V>

struct HashTableNode

{

HashTableNode()

{}

HashTableNode(const T& key, const V& value)

:_key(key)

, _value(value)

{}

T _key;

V _value;

};

template <class T>

struct __HashFunc

{

size_t operator()(const T& key)

{

return key;

}

};

//實(shí)現(xiàn)key，value形式，并且是二次探測的

template <class T ,class V,class HashFunc=__HashFunc<T>>

class Dictionary

{

public:

Dictionary(size_t capacity=10)

:_capacity(capacity)

, _tables(new HashTableNode<T,V> [_capacity])

, _states(new State[_capacity])

,_size(0)

{

for (int i = 0; i < _capacity; i++)

{

_states[i] = EMPTY;//將最開始的狀態(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<T, V>(key, value);

_states[index] = EXITS;

_size++;

return true;

}

HashTableNode<T,V>* Find(const T& key)

{

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<T, V, HashFunc> tmp(2 * _capacity);

for (int i = 0; i < _capacity; i++)

{

if (_states[i] == EXITS)

{

tmp.Insert(_tables[i]._key,_tables[i]._value);

}

}

_Swap(tmp);

}

}

void _Swap(Dictionary<T, V, HashFunc> tmp)

{

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)//獲取二次探測的下標(biāo)

{

return (index + i*i) % _capacity;

}

private:

size_t _capacity;

HashTableNode<T,V>* _tables;

State* _states;

size_t _size;

};

}

void test3()//二次探測，負(fù)載因子，實(shí)現(xiàn)字典的功能

{

/*Third::Dictionary<int, string> h2;

h2.Insert(10, "c語言基礎(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<int,int>h2;

h2.Insert(10, 1);

h2.Insert(59, 2);

h2.Insert(9, 3);

h2.Insert(19,4);

h2.Insert(18, 5);

//h2.Print();

cout<<h2.Find(9)->_value<<endl;

//h2.Remove(9);

//h2.Remove(19);

//h2.Remove(10);

//h2.Print();

}

上述就是對(duì)哈希算法的簡單應(yīng)用。