哈希表的實現

   散列表（Hash table，也叫哈希表），是根據關鍵字（Key value）而直接訪問在內存存儲位置的數據結構。也就是說，它通過計算一個關于鍵值的函數，將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散列表。

應用：

  一個通俗的例子是，為了查找電話簿中某人的號碼，可以創建一個按照人名首字母順序排列的表（即建立人名到首字母的一個函數關系），在首字母為W的表中查找“王”姓的電話號碼，顯然比直接查找就要快得多。這里使用人名作為關鍵字，“取首字母”是這個例子中散列函數的函數法則，存放首字母的表對應散列表。關鍵字和函數法則理論上可以任意確定。

基本概念：

• 若關鍵字為K，則其值存放在的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系為散列函數，按這個思想建立的表為散列表。

• 對不同的關鍵字可能得到同一散列地址，即，而，這種現象稱為沖突（英語：Collision）。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。綜上所述，根據散列函數和處理沖突的方法將一組關鍵字映射到一個有限的連續的地址集（區間）上，并以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。

• 若對于關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為均勻散列函數（Uniform Hash function），這就是使關鍵字經過散列函數得到一個“隨機的地址”，從而減少沖突。

查找效率： 

  散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到，另一些關鍵碼在散列函數得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突后的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。

查找過程中，關鍵碼的比較次數，取決于產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。影響產生沖突多少有以下三個因素：

1. 散列函數是否均勻；

2. 處理沖突的方法；

3. 散列表的載荷因子

載荷因子：

散列表的載荷因子定義為： = 填入表中的元素個數 / 散列表的長度。

  是散列表裝滿程度的標志因子。由于表長是定值，與“填入表中的元素個數”成正比，所以，越大，表明填入表中的元素越多，產生沖突的可能性就越大；反之，越小，標明填入表中的元素越少，產生沖突的可能性就越小。實際上，散列表的平均查找長度是載荷因子的函數，只是不同處理沖突的方法有不同的函數。

構造哈希表的幾種方法：

1. 直接定址法--取關鍵字的某個線性函數為散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B為常數。

2. 除留余數法--取關鍵值被某個不大于散列表長m的數p除后的所得的余數為散列地址。Hash（Key）= Key % P。

3. 平方取中法

4. 折疊法

5. 隨機數法

6. 數學分析法

線性探測：

#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<vector>
#include<string>

enum Statue  //標記一個數的存在狀態
{
EXIST,
DELETE,
EMPTY
};


template<class K, class V>    //定義類型
struct HashNode
{
K _key;
V _value;
Statue statue;

HashNode(const K& key, const V& value)
:_key(key),
_value(value),
statue(EXIST)
{}

HashNode()
:statue(EMPTY)
{}
};


template<class K>
struct _HashFuncDefault
{
size_t operator()(const K& key)
{
return key;
}
};


static size_t BKDRHash(const char * str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}


template<>
struct _HashFuncDefault<string>
{
size_t operator()(const string str)
{
return BKDRHash(str.c_str());
}
};


template<class K, class V, class _HashFuncer = _HashFuncDefault<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
:_size(0)
{
for (size_t i = 0; i < _table.size(); i++)
{
_table[i].statue = EMPTY;
}
}

bool Insert(const K& key, const V& value)
{
_CheckCapaciy();
size_t index = _HashFunc(key,_table.size());
size_t tmp = index;
if (_table[index]._key == key)//已經有這個數
{
return false;
}
if (_table[index].statue == EXIST)
{
++index;
while (index != tmp)  //保證不走過一圈
{
if (index == _table.size()) //到最后一個就從第一個開始
{
index = 0;
}
if (_table[index].statue != EXIST)//找到可以插入的位置
{
break;
}
if (_table[index]._key == key)//已經有這個數
{
return false;
}
++index;
}
}
_table[index].statue = EXIST;
_table[index]._key = key;
_table[index]._value = value;
++_size;
return true;
}

void Remove(const K& key)
{
size_t index = _HashFunc(key, _table.size());
size_t tmp = index;
if (_table[index]._key != key)
{
++index;
while (index != tmp)
{
if (index == _table.size())
{
index = 0;
}
if (_table[index]._key == key)
{
break;
}
++index;
}
}
if (_table[index]._key == key)
{
_table[index].statue = DELETE;
--_size;
return;
}
return;
}


int Find(const K& key)
{
size_t index = _HashFunc(key, _table.size());
size_t tmp = index;
if (_table[index]._key == key && _table[index].statue == EXIST)
{
return index;
}
else
{
++index;
while (index != tmp)
{
if (index == _table.size())
{
index = 0;
}
if (_table[index]._key == key && _table[index].statue == EXIST)
{
break;
}
++index;
}
}
if (_table[index]._key == key && _table[index].statue == EXIST)
{
return index;
}
return -1;
}
void Print()
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i].statue == EXIST)
{
cout << "KEY:" << _table[i]._key << "  " << "VALUE:" << _table[i]._value<< "  " << "STATUE:" << _table[i].statue << endl;
}
}
}

protected:
size_t _HashFunc(const K& key, size_t capacity)
{
_HashFuncer hf;
return hf(key) % capacity;
}

void _CheckCapaciy()
{
if (_size * 10 >= _table.size())
{
const int _PrimeSize = 28;
static const unsigned long _PrimeList[_PrimeSize] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t newCapacity = 0;
for (size_t i = 0; i < _PrimeSize; i++)
{
if (_table.size() < _PrimeList[i])
{
newCapacity = _PrimeList[i];
break;
}
}
HashTable<K,V> tmp;
tmp._table.resize(newCapacity);
for (size_t i = 0; i < _table.size(); i++)
{
tmp.Insert(_table[i]._key, _table[i]._value);
}
Swap(tmp);
}
}


void Swap(HashTable<K, V>& tem)
{
swap(_table, tem._table);
tem._size = _size;
}
private:
vector<Node> _table;
size_t _size;
};


void test()
{
HashTable<string, string> ht;
ht.Insert("hello", "你好");
ht.Insert("hello", "你好");
ht.Insert("change", "改變");
ht.Insert("world", "世界");
ht.Insert("change", "改變");
ht.Insert("xi'an", "西安");
ht.Remove("hello");
int ret = ht.Find("world");
ht.Print();
}


int main()
{
test();
system("pause");
return 0;
}

二次探測：

#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
enum Status
{
EXIST,
DELETE,
EMPTY
};
template<class K, class V>
struct KeyValue
{
K _key;
V _value;
KeyValue(const K& key = K(), const V& value = V())
:_key(key),
_value(value)
{}
};
template<class K, class V>
class HashTable
{
typedef KeyValue<K, V> type;
public:
HashTable()
:_table(NULL),
_size(0),
_capacity(0),
_status(EMPTY)
{}
HashTable(const size_t& size)
:_table(new type[size]),
_size(0),
_capacity(size),
_status(new Status[size])
{
for (size_t i = 0; i < size; i++)
{
_status[i] = EMPTY;
}
}
bool Insert(const K& key, const V& value);
void Print();
int Find(const K& key);
void Remove(const K& key);
~HashTable();
protected:
void _Swap(HashTable<K, V>& tmp);
size_t _HashFunc(const K& key, size_t i);
private:
type* _table;
size_t _size;
size_t _capacity;
Status* _status;
};
template<class K, class V>
bool HashTable<K, V>::Insert(const K& key, const V& value)
{
if (_size * 10 >= _capacity * 8)//負載因子
{
size_t newcapacity = 2 * _capacity;
HashTable<K, V> tmp(newcapacity);
for (size_t i = 0; i < _capacity; i++)
{
tmp.Insert(_table[i]._key, _table[i]._value);
}
this->_Swap(tmp);
}
size_t i = 0;//計數器
size_t index = _HashFunc(key, i);//計算下標
size_t begin = index;
do
{
if (_status[index] == EMPTY || _status[index] == DELETE)//是空或者已經刪除
break;
if (_status[index] == EXIST && _table[index]._key == key)//已經有這個數
return true;
index = _HashFunc(key, ++i);
if (index == _capacity)
index = 0;
} while (begin != index);
if (_status[index] == EXIST)
return false;
_table[index]._key = key;
_table[index]._value = value;
_status[index] = EXIST;
++_size;
return true;
}
template<class K, class V>
void HashTable<K, V>::_Swap(HashTable<K, V>& tmp)
{
swap(_table, tmp._table);
swap(_size, tmp._size);
swap(_capacity, tmp._capacity);
swap(_status, tmp._status);
}
template<class K, class V>
size_t HashTable<K, V>::_HashFunc(const K& key, size_t i)
{
size_t ret = (key + i*i) % _capacity;
return ret;
}
template<class K, class V>
void HashTable<K, V>::Print()
{
for (size_t i = 0; i < _capacity; i++)
{
printf("第%d個 key: %d  value: %d status: %d \n", i, _table[i]._key, _table[i]._value, _status[i]);
}
}
template<class K, class V>
int HashTable<K, V>::Find(const K& key)
{
int i = 0;
size_t index = _HashFunc(key,i);
if (_table[index]._key == key && _status[index]==EXIST)
{
return index;
}
else
{
int begin = index;
++index;
while (index != begin)
{
if (_table[index]._key == key && _status[index] == EXIST)
{
return index;
}
index = _HashFunc(key, ++i);
}
}
return -1;
}
template<class K, class V>
void HashTable<K, V>::Remove(const K& key)
{
int i = 0;
size_t index = _HashFunc(key, i);
if (_table[index]._key == key && _status[index] == EXIST)
{
_status[index] = DELETE;
return;
}
else
{
int begin = index;
++index;
while (index != begin)
{
if (_table[index]._key == key && _status[index] == EXIST)
{
_status[index] = DELETE;
return;
}
index = _HashFunc(key, ++i);
}
}
}
template<class K, class V>
void HashTable<K, V>::~HashTable()
{
if (_table)
{
delete[] _table;
}
}
void test()
{
HashTable<int, int>ha(2);
ha.Insert(0, 1);
ha.Insert(1, 2);
ha.Insert(2, 5);
ha.Insert(3, 8);
ha.Insert(4, 9);
ha.Insert(6, 0);
ha.Print();
int ret=ha.Find(3);
ha.Remove(4);
ha.Print();
}
int main()
{
test();
system("pause");
return 0;
}