溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
HashTable-散列表/哈希表，是根據關鍵字（key）而直接訪問在內存存儲位置的數據結構。它通過一個關鍵值的函數將所需的數據映射到表中的位置來訪問數據，這個映射函數叫做散列函數，存放記錄的數組叫做散列表。 構造哈希表的幾種方法 直接定址法--取關鍵字的某個線性函數為散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B為常數。 除留余數法--取關鍵值被某個不大于散列表長m的數p除后的所得的余數為散列地址。Hash（Key）= Key % P。 平方取中法 折疊法 隨機數法 數學分析法 哈希沖突/哈希碰撞 不同的Key值經過哈希函數Hash(Key)處理以后可能產生相同的值哈希地址，我們稱這種情況為哈希沖突。任意的散列函數都不能避免產生沖突。
處理哈希沖突的閉散列方法
線性探測
#pragma once
#include <string>
#include <iostream>
using namespace std;
namespace First
{
enum State
{
EMPTY,
DELETE,
EXIST,
};
template<class K>
struct __HashFunc // 產生鍵值(如把string的轉化成數字) 默認的返回哈希鍵值key的 仿函數
{
size_t operator()(const K& key)
{
return key;
}
};
template<class K>
class HashTable
{
// Key形式的線性探測
public:
HashTable(size_t capacity = 10)
:_tables(new K[capacity])
,_size(0)
,_capacity(capacity)
,_states(new State[capacity])
{
// memset 有問題 是以字節為單位初始化的 但第二個參數值為int
// 會出問題 本來初始化為0x00000001 結果初始化為0x01010101
//memset(_states, EMPTY, sizeof(State) * capacity);
for (size_t i = 0; i < capacity; i++)
{
_states[i] = EMPTY;
}
}
HashTable(const HashTable<K>& ht)
:_tables(new K[ht._capacity])
,_size(0)
,_capacity(ht._capacity)
,_states(new State[ht._capacity])
{
for (size_t i = 0; i < ht._capacity; i++)
{
if (EXIST == ht._states[i])
{
Insert(ht._tables[i]);
}
}
}
HashTable& operator=(const HashTable<K>& ht)
{
if (ht._tables != _tables && ht._states != _states)
{
HashTable<K> tmp(ht);
Swap(tmp);
}
return *this;
}
~HashTable()
{
if (NULL != _tables)
{
delete[] _tables;
}
if (NULL != _states)
{
delete[] _states;
}
}
bool Insert(const K& key)
{
// 靜態哈希表 不擴容的
/*if (_size == _capacity)
{
cout<<"HashTable is full"<<endl;
return false;
}*/
_CheckCapacity();
size_t index = _HashFunc(key);
while (EXIST == _states[index])
{
index++;
if (_capacity == index)
{
index=0;
}
}
_tables[index] = key;
_states[index] = EXIST;
_size++;
return true;
}
int Find(const K& key)
{
size_t index = _HashFunc(key);
size_t start = index;
// 存在 或者 被刪除 兩種狀態
while (EMPTY != _states[index])
{
if (_tables[index] == key)
{
if (_states[index] == EXIST)
{
return index;
}
else // 被刪除 DELETE
{
return -1;
}
}
index++;
if (index == _capacity)
{
index = 0;
}
// 找一圈 沒找到就停止 防止死循環
if (index == start)
{
return -1;
}
}
return -1;
}
bool Remove(const K& key)
{
int index = Find(key);
if (-1 != index)
{
_states[index] = DELETE;
--_size;
return true;
}
return false;
}
// 線性探測計算出存放位置（假設不哈希沖突）
size_t _HashFunc(const K& key)
{
__HashFunc<K> hf;
return hf(key) % _capacity; // 仿函數hf()
// 匿名對象
// return __HashFunc<K>()(key) % _capacity;
}
void Print()
{
for (size_t i = 0; i < _capacity; i++)
{
if (EXIST == _states[i])
{
cout<< i << "EXIST:" << _tables[i] << endl;
}
else if (DELETE == _states[i])
{
cout<< i << "DELETE:" << _tables[i] << endl;
}
else
{
cout << i << "EMPTY" << _tables[i] <<endl;
}
}
}
void Swap(HashTable<K>& ht)
{
swap(_size, ht._size);
swap(_states, ht._states);
swap(_tables, ht._tables);
swap(_capacity, ht._capacity);
}
protected:
void _CheckCapacity() // 擴容
{
// 動態的 可擴容的
// 高效哈希表的載荷因子大概在0.7-0.8較好
if (10 * _size / _capacity >= 7) // _size/_capacity為0 因為都是××× 所以乘10
// 保證載荷因子在0.7之內
{
HashTable<K> tmp(2 * _capacity);
for (size_t i = 0; i < _capacity; i++)
{
if (EXIST == _states[i])
{
tmp.Insert(_tables[i]);
}
}
Swap(tmp);
}
}
protected:
K* _tables; // 哈希表
State* _states; // 狀態表
size_t _size;
size_t _capacity;
};
}
void test_namespace_First()
{
using namespace First;
HashTable<int> ht;
ht.Insert(89);
ht.Insert(18);
ht.Insert(49);
ht.Insert(58);
ht.Insert(9);
ht.Print();
int ret = ht.Find(49);
cout<<ret<<endl;
ht.Remove(89);
ht.Print();
ht.Remove(18);
ht.Print();
cout<<"---------------------------"<<endl;
HashTable<int> ht2 = ht;
ht2.Print();
cout<<"---------------------------"<<endl;
ht = ht2;
ht.Print();
cout<<"---------------------------"<<endl;
}
//============================================================================2 二次探測
namespace Second
{
enum State
{
EMPTY,
DELETE,
EXIST,
};
// Key/Value
template<class K, class V>
struct HashTableNode
{
K _key;
V _value;
};
template<class K>
struct __HashFunc // 默認的返回哈希鍵值key的 仿函數
{
size_t operator()(const K& key)
{
return key;
}
};
// 特化string的__HashFunc 仿函數
template<>
struct __HashFunc<string>
{
//下面這種缺點 產生重復key 如“abcd” 與 “bcda”
size_t operator()(const string& str)
{
size_t key = 0;
for (size_t i = 0; i < str.size(); i++)
{
key += str[i];
}
return key;
}
};
// 實現哈希表的Key/Value形式的二次探測
template<class K, class V, class HashFunc = __HashFunc<K>>
class HashTable
{
typedef HashTableNode<K,V> Node;
public:
HashTable(size_t capacity = 10)
:_tables(new Node[capacity])
,_size(0)
,_capacity(capacity)
,_states(new State[capacity])
{
// memset 有問題 是以字節為單位初始化的 但第二個參數值為int
// 會出問題 本來初始化為0x00000001 結果初始化為0x01010101
//memset(_states, EMPTY, sizeof(State) * capacity);
for (size_t i = 0; i < capacity; i++)
{
_states[i] = EMPTY;
}
}
HashTable(const HashTable<K, V, HashFunc>& ht)
:_tables(new Node[ht._capacity])
,_size(0)
,_capacity(ht._capacity)
,_states(new State[ht._capacity])
{
for (size_t i = 0; i < ht._capacity; i++)
{
if (EXIST == ht._states[i])
{
Insert(ht._tables[i]._key, ht._tables[i]._value);
}
}
}
HashTable& operator=(const HashTable<K, V, HashFunc>& ht)
{
if (ht._tables != _tables && ht._states != _states)
{
HashTable<K, V, HashFunc> tmp(ht);
Swap(tmp);
}
return *this;
}
~HashTable()
{
if (NULL != _tables)
{
delete[] _tables;
}
if (NULL != _states)
{
delete[] _states;
}
}
bool Insert(const K& key, const V& value)
{
// 靜態哈希表 不擴容的
/*if (_size == _capacity)
{
cout<<"HashTable is full"<<endl;
return false;
}*/
_CheckCapacity();
//size_t hashKeyStart = _HashFunc(key);
//size_t add_more = 1;
//size_t index = hashKeyStart;
//// ****************************************
//// 二次探測 Hash(key) + 0 Hash(key) + 1^2 Hash(key) + 2^2
//while (EXIST == _states[index])
//{
// index = hashKeyStart + add_more * add_more;
// add_more++;
// if (index >= _capacity)
// {
// index = index % _capacity;
// }
//}
// ****************************************
// 改進 用GetNextIndex 解決哈希沖突
size_t index = _HashFunc(key);
// 二次探測
size_t i = 1;
while (EXIST == _states[index])
{
index = _GetNextIndex(index, i++);
if (index >= _capacity)
{
index = index % _capacity;
}
}
_tables[index]._key = key;
_tables[index]._value = value;
_states[index] = EXIST;
_size++;
return true;
}
int Find(const K& key)
{
size_t index = _HashFunc(key);
size_t start = index;
size_t i = 1;
// 存在 或者 被刪除 兩種狀態
while (EMPTY != _states[index])
{
if (_tables[index]._key == key)
{
if (_states[index] == EXIST)
{
return index;
}
else // 被刪除 DELETE
{
return -1;
}
}
index = _GetNextIndex(index, i++);
if (index >= _capacity)
{
index = index % _capacity;
}
// 因為有填充因子 不為100% 不會出現全滿且key！=_key 導致死循環的情況
}
return -1;
}
bool Remove(const K& key)
{
int index = Find(key);
if (-1 != index)
{
_states[index] = DELETE;
--_size;
return true;
}
return false;
}
// 二次探測計算出存放位置
size_t _HashFunc(const K& key)
{
// __HashFunc<K> hf;
HashFunc hf;
return hf(key) % _capacity; // 仿函數hf()
// 匿名對象
// return __HashFunc<K>()(key) % _capacity;
}
// 哈希沖突時 得到下一個index的可以利用上一個index的值 這樣能提高效率 比如 string的index計算就比較費時
size_t _GetNextIndex(size_t prev, size_t i)
{
//二次探測
// 公式推導 Hash(i) = Hash(0) + i^2
// Hash(i-1) = Hash(0) + (i -1)^2=Hash(0)+i^2-2i+1
// 上面兩式相減 得 Hash(i) = Hash(i-1) + +2*i - 1;
return prev + 2*i - 1;
}
void Print()
{
for (size_t i = 0; i < _capacity; i++)
{
if (EXIST == _states[i])
{
cout<< i << "EXIST:" <<_tables[i]._key << "-------" <<_tables[i]._value <<endl;
}
else if (DELETE == _states[i])
{
cout<< i << "DELETE:" << _tables[i]._key << "-------" << _tables[i]._value <<endl;
}
else
{
cout << i << "EMPTY:" << _tables[i]._key << "-------" << _tables[i]._value <<endl;
}
}
}
void Swap(HashTable<K, V, HashFunc>& ht)
{
swap(_size, ht._size);
swap(_states, ht._states);
swap(_tables, ht._tables);
swap(_capacity, ht._capacity);
}
protected:
void _CheckCapacity() // 擴容
{
// 動態的 可擴容的
// 高效哈希表的載荷因子大概在0.7-0.8較好
if (10 * _size / _capacity >= 7) // _size/_capacity為0 因為都是××× 所以乘10
// 保證載荷因子在0.7之內
{
HashTable<K, V, HashFunc> tmp(2 * _capacity);
for (size_t i = 0; i < _capacity; i++)
{
if (EXIST == _states[i])
{
tmp.Insert(_tables[i]._key, _tables[i]._value);
}
}
Swap(tmp);
}
}
protected:
Node* _tables; // 哈希表
State* _states; // 狀態表
size_t _size;
size_t _capacity;
};
}
void test_namespace_Second()
{
using namespace Second;
HashTable<string, string> ht;
ht.Insert("one","一");
ht.Insert("two","二");
ht.Insert("three","三");
ht.Insert("four","四");
ht.Insert("five","五");
ht.Print();
int ret = ht.Find("two");
cout<<ret<<endl;
ret = ht.Find("hfjks");
cout<<ret<<endl;
ht.Remove("one");
ht.Print();
ht.Remove("two");
ht.Print();
cout<<"---------------------------"<<endl;
HashTable<string, string> ht2 = ht;
ht2.Print();
cout<<"---------------------------"<<endl;
ht = ht2;
ht.Print();
cout<<"---------------------------"<<endl;
}3 處理哈希沖突的開鏈法(哈希桶)
#pragma once
#include<iostream>
#include<vector>
#include<string>
/*********
* 哈希桶 （處理哈希沖突的開鏈法）
*
****************/
template<class K, class V>
struct HashTableNode
{
K _key;
V _value;
HashTableNode* _next;
HashTableNode()
:_next(NULL)
{}
HashTableNode(const K& key, const V& value)
:_key(key)
,_value(value)
,_next(NULL)
{}
};
template<class K>
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return key ;
}
};
template<>
struct DefaultHashFunc<std::string>
{
size_t operator()(const std::string& str)
{
size_t key = 0;
for (size_t i = 0; i < str.size(); i++)
{
key += str[i];
}
return key;
}
};
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTableBucket
{
typedef HashTableNode<K, V> Node;
public:
HashTableBucket()
:_size(0)
{}
HashTableBucket(const HashTableBucket<K, V, HashFunc>& ht)
:_size(ht._size)
{
_tables.resize(ht._tables.size());
for (size_t i = 0; i < ht._tables.size(); i++)
{
Node* cur = ht._tables[i];
while (NULL != cur)
{
Node* newNode = new Node(cur->_key, cur->_value);
newNode->_next = _tables[i];
_tables[i] = newNode;
cur = cur->_next;
}
}
}
HashTableBucket& operator=(const HashTableBucket& ht)
{
if (this != &ht)
{
HashTableBucket tmp(ht);
_tables.swap(tmp._tables);
std::swap(_size, tmp._size);
}
return *this;
}
~HashTableBucket()
{
for (size_t index = 0 ; index < _tables.size(); index++)
{
Node* cur = _tables[index];
while (NULL != cur)
{
Node* del = cur;
cur = cur->_next;
delete del;
}
}
_size = 0;
}
bool Insert(const K& key, const V& value)
{
// 檢測容量
_CheckExpand();
size_t index = _HashFunc(key, _tables.size());
Node* cur = _tables[index];
// 防止冗余
while (NULL != cur)
{
// 鍵值重復
if (key == cur->_key)
{
return false;
}
cur = cur->_next;
}
// 頭插 (同一單鏈表上 順序無關)
Node* newNode = new Node(key, value);
newNode->_next = _tables[index];
_tables[index] = newNode;
++_size;
return true;
}
Node* Find(const K& key)
{
size_t index = _HashFunc(key, _tables.size());
Node* cur = _tables[index];
while (NULL != cur)
{
if (key == cur->_key)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
bool Remove(const K& key)
{
size_t index = _HashFunc(key, _tables.size());
Node* cur = _tables[index];
Node* prev = cur;
if (NULL == cur)
{
return false;
}
// 一個結點
if (NULL == cur->_next && cur->_key == key)
{
delete cur;
_tables[index] = NULL;
--_size;
return true;
}
cur = cur->_next;
while (NULL != cur)
{
if (key == cur->_key)
{
prev->_next = cur->_next;
delete cur;
--_size;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
void PrintTables()
{
for (size_t index = 0; index < _tables.size(); index++)
{
Node* cur = _tables[index];
while (NULL != cur)
{
std::cout<<index<<" {"<<cur->_key<<"---"<<cur->_value<<"} ";
cur = cur->_next;
if (NULL == cur)
{
std::cout<<std::endl;
}
}
}
}
protected:
size_t _HashFunc(const K& key, const size_t size)
{
// _table.size90 哈希桶空間大小 vector 數組大小（相當于哈希表的空間）
return HashFunc()(key) % size;
}
size_t _GetNextPrime() // 得到下一個擴容的素數
{
static const size_t _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
};
for (size_t i = 0; i < _PrimeSize; i++)
{
if (_PrimeList[i] > _size)
{
return _PrimeList[i];
}
}
return _PrimeList[_PrimeSize - 1];
}
void _CheckExpand() // 擴容(容量都是素數)
{
if (_size == _tables.size())
{
size_t newSize = _GetNextPrime();
std::vector<Node*> newTables;
newTables.resize(newSize);
// newTables.resize() 已經初始化成0x00000000
/*for (size_t i = 0; i < newSize; i++)
{
newTables[i] = NULL;
}*/
// 將每個單鏈表上的元素摘下來 掛到新表上
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (NULL != cur)
{
// 摘結點
Node* pTmp = cur;
cur = cur->_next;
// 掛結點
size_t index = _HashFunc(pTmp->_key, newSize);
pTmp->_next = newTables[index];
newTables[index] = pTmp;
}
_tables[i] = NULL;
}
_tables.swap(newTables);
}
}
protected:
std::vector<Node*> _tables; // 存放頭指針
size_t _size; // _tables中已有元素(頭指針)的個數
};================測試=====================================
#define _CRT_SECURE_NO_WARNINGS 1
//#include"HashTable.hpp
#include"HashTableBucket.hpp"
void test_HashTable()
{
// test_namespace_First();
// test_namespace_Second();
}
void test_HashTableBucket1()
{
HashTableBucket<int,int> ht;
ht.Insert(1,1);
ht.Insert(2,2);
ht.Insert(3,3);
ht.Insert(4,4);
ht.Insert(53 + 1,53);
ht.PrintTables();
HashTableBucket<int,int>ht2(ht);
ht2.PrintTables();
HashTableNode<int,int>* pht2 = ht2.Find(4);
bool brm = ht2.Remove(4);
pht2 = ht2.Find(4);
brm = ht2.Remove(5); // false
ht = ht2;
ht.PrintTables();
HashTableBucket<int,int> ht3;
//擴容測試 _CheckExpand() //
for (size_t i = 0; i < 53; i++)
{
ht3.Insert(i,1);
}
// 增容
ht3.Insert(53,4);
std::cout<<"-------------------"<<std::endl;
ht3.PrintTables();
}
void test_HashTableBucket2()
{
// 特殊類型測試
HashTableBucket<std::string,std::string> ht;
ht.Insert("one","一");
ht.Insert("two","二");
ht.Insert("three","三");
ht.Insert("four","四");
ht.PrintTables();
HashTableBucket<std::string,std::string>ht2(ht);
ht2.PrintTables();
HashTableNode<std::string,std::string>* pht2 = ht2.Find("two");
bool brm = ht2.Remove("two");
pht2 = ht2.Find("two");
brm = ht2.Remove("five"); // false
ht = ht2;
ht.PrintTables();
HashTableBucket<std::string,std::string> ht3;
//擴容測試 _CheckExpand() //
for (size_t i = 0; i < 53; i++)
{
ht3.Insert(std::string().append(i,'0'),"ooooo");
}
// 增容
ht3.Insert("53","4");
std::cout<<"-------------------"<<std::endl;
ht3.PrintTables();
}
int main()
{
test_HashTableBucket2();
return 0;
}
字符串哈希算法
http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
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);
}
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
