#pragma once
#include<iostream>
#include<string>
using namespace std;
enum State
{
EMPTY,
DELETE,
EXIST,
};
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>
{
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)
, _states(new State[capacity])
, _capacity(capacity)
{
// memset 有問題 是以字節(jié)為單位初始化的 但第二個參數值為int
//memset(_states, EMPTY, sizeof(State) * capacity);
for (size_t i = 0; i < capacity; i++)
{
_states[i] = EMPTY;
}
}
~HashTable()
{
if (NULL != _tables)
{
delete[] _tables;
_tables = NULL;
}
if (NULL != _states)
{
delete[] _states;
_states = NULL;
}
}
bool Insert(const K& key, const V& value)
{
_CheckCapacity();
//用GetNextIndex 解決哈希沖突
size_t index = _HashFunc(key);
// 二次探測   
size_t i = 1;
while (_states[index] == EXIST)
{
index = _GetNextIndex(index, i++);
if (index >= _capacity)
{
index = index % _capacity;
}
}
_tables[index]._key = key;
_tables[index]._value = value;
_states[index] = EXIST;
_size++;
return true;
}
Node* Find(const K& key)
{
size_t index = _HashFunc(key);
size_t start = index;
size_t i = 1;
// 存在 或者 被刪除 兩種狀態(tài)
while (_states[index] != EMPTY)
{
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 導致死循環(huán)的情況
}
return -1;
}
bool Remove(const K& key)
{
int index = Find(key);
if (index != -1)
{
_states[index] = DELETE;
--_size;
return true;
}
return false;
}
// 二次探測計算出存放位置
size_t _HashFunc(const K& key)
{
HashFunc hf;
return hf(key) % _capacity; //  仿函數hf() 
}
//   哈希沖突時 得到下一個index的可以利用上一個index的值 這樣能提高效率 比如 string的index計算就比較費時
size_t _GetNextIndex(size_t prev, size_t i)
{
return prev + 2 * i - 1;
}
void Print()
{
for (size_t i = 0; i < _capacity; i++)
{
if (_states[i] == EXIST)
{
cout << i << "EXIST:" << _tables[i]._key << "-------" << _tables[i]._value << endl;
}
else if (_states[i] == DELETE)
{
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之內
{
HashTable<K, V, HashFunc> tmp(2 * _capacity);
for (size_t i = 0; i < _capacity; i++)
{
if (_states[i] == EXIST)
{
tmp.Insert(_tables[i]._key, _tables[i]._value);
}
}
Swap(tmp);
}
}
protected:
Node* _tables;
State* _states;//狀態(tài)表
size_t _size;
size_t _capacity;
};

創(chuàng)新互聯www.cdcxhl.cn，專業(yè)提供香港、美國云服務器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調度，確保服務器高可用性。佳節(jié)活動現已開啟，新人活動云服務器買多久送多久。

成都創(chuàng)新互聯公司主打移動網站、做網站、成都網站設計、網站改版、網絡推廣、網站維護、域名申請、等互聯網信息服務，為各行業(yè)提供服務。在技術實力的保障下，我們?yōu)榭蛻舫兄Z穩(wěn)定，放心的服務，根據網站的內容與功能再決定采用什么樣的設計。最后，要實現符合網站需求的內容、功能與設計，我們還會規(guī)劃穩(wěn)定安全的技術方案做保障。

當前名稱：哈希表（散列表）二次探測-創(chuàng)新互聯
分享URL：http://m.rwnh.cn/article18/djiodp.html

成都網站建設公司_創(chuàng)新互聯，為您提供服務器托管、網站導航、ChatGPT、手機網站建設、電子商務、網站營銷

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯