溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
HashTable-散列表/哈希表，是根據(jù)關(guān)鍵字（key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。它通過一個關(guān)鍵值的函數(shù)將所需的數(shù)據(jù)映射到表中的位置來訪問數(shù)據(jù)，這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。 構(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。 平方取中法 折疊法 隨機數(shù)法 數(shù)學(xué)分析法 哈希沖突/哈希碰撞 不同的Key值經(jīng)過哈希函數(shù)Hash(Key)處理以后可能產(chǎn)生相同的值哈希地址，我們稱這種情況為哈希沖突。任意的散列函數(shù)都不能避免產(chǎn)生沖突。
處理哈希沖突的閉散列方法
線性探測
#pragma once
#include <string>
#include <iostream>
using namespace std;
namespace First
{
enum State
{
EMPTY,
DELETE,
EXIST,
};
template<class K>
struct __HashFunc // 產(chǎn)生鍵值(如把string的轉(zhuǎn)化成數(shù)字) 默認的返回哈希鍵值key的 仿函數(shù)
{
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 有問題 是以字節(jié)為單位初始化的 但第二個參數(shù)值為int
// 會出問題 本來初始化為0x00000001 結(jié)果初始化為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)
{
// 靜態(tài)哈希表 不擴容的
/*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;
// 存在 或者 被刪除 兩種狀態(tài)
while (EMPTY != _states[index])
{
if (_tables[index] == key)
{
if (_states[index] == EXIST)
{
return index;
}
else // 被刪除 DELETE
{
return -1;
}
}
index++;
if (index == _capacity)
{
index = 0;
}
// 找一圈 沒找到就停止 防止死循環(huán)
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;
}
// 線性探測計算出存放位置（假設(shè)不哈希沖突）
size_t _HashFunc(const K& key)
{
__HashFunc<K> hf;
return hf(key) % _capacity; // 仿函數(shù)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() // 擴容
{
// 動態(tài)的 可擴容的
// 高效哈希表的載荷因子大概在0.7-0.8較好
if (10 * _size / _capacity >= 7) // _size/_capacity為0 因為都是××× 所以乘10
// 保證載荷因子在0.7之內(nèi)
{
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; // 狀態(tài)表
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的 仿函數(shù)
{
size_t operator()(const K& key)
{
return key;
}
};
// 特化string的__HashFunc 仿函數(shù)
template<>
struct __HashFunc<string>
{
//下面這種缺點 產(chǎn)生重復(fù)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;
}
};
// 實現(xiàn)哈希表的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 有問題 是以字節(jié)為單位初始化的 但第二個參數(shù)值為int
// 會出問題 本來初始化為0x00000001 結(jié)果初始化為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)
{
// 靜態(tài)哈希表 不擴容的
/*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;
// 存在 或者 被刪除 兩種狀態(tài)
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% 不會出現(xiàn)全滿且key！=_key 導(dǎo)致死循環(huán)的情況
}
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; // 仿函數(shù)hf()
// 匿名對象
// return __HashFunc<K>()(key) % _capacity;
}
// 哈希沖突時 得到下一個index的可以利用上一個index的值 這樣能提高效率 比如 string的index計算就比較費時
size_t _GetNextIndex(size_t prev, size_t i)
{
//二次探測
// 公式推導(dǎo) 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() // 擴容
{
// 動態(tài)的 可擴容的
// 高效哈希表的載荷因子大概在0.7-0.8較好
if (10 * _size / _capacity >= 7) // _size/_capacity為0 因為都是××× 所以乘10
// 保證載荷因子在0.7之內(nèi)
{
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; // 狀態(tài)表
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)
{
// 鍵值重復(fù)
if (key == cur->_key)
{
return false;
}
cur = cur->_next;
}
// 頭插 (同一單鏈表上 順序無關(guān))
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;
}
// 一個結(jié)點
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 數(shù)組大?。ㄏ喈?dāng)于哈希表的空間）
return HashFunc()(key) % size;
}
size_t _GetNextPrime() // 得到下一個擴容的素數(shù)
{
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() // 擴容(容量都是素數(shù))
{
if (_size == _tables.size())
{
size_t newSize = _GetNextPrime();
std::vector<Node*> newTables;
newTables.resize(newSize);
// newTables.resize() 已經(jīng)初始化成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)
{
// 摘結(jié)點
Node* pTmp = cur;
cur = cur->_next;
// 掛結(jié)點
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中已有元素(頭指針)的個數(shù)
};================測試=====================================
#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);
}
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼