哈希表/散列表，是根据关键字（key）直接访问在内存存储位置的数据结构。
创新互联公司是一家专业提供松北企业网站建设,专注与网站设计制作、网站设计、H5响应式网站、小程序制作等业务。10年已为松北众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。
构造哈希表的常用方法：
直接地址法---取关键字的某个线性函数为散列地址，Hash(Key) = Key或Hash(key) = A*Key + B,
A,B为常数。
除留余数法---取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。
Hash(key) = key % p。
若采用直接地址法（Hash(Key) = Key）存在一定的缺陷。
当Key值特别大时，而Key之前的数很少，就会造成空间浪费。大多时候采取除留余数法。
哈希冲突/哈希碰撞
不同的Key值经过哈希函数Hash(Key)处理以后可能产生相同的哈希地址，我们称这种情况为哈希冲突。任何的散列函数都不能避免产生冲突。
散列表的载荷因子定义为a = 填入表中元素的个数/散列表的长度
载荷因子越大，冲突的可能性就越大。
解决冲突的办法：
（1）线性探测
（2）二次探测
#pragma once
#include
#include
using namespace std;
enum State
{
EMPTY,
DELETE,
EXITS,
};
//以key形式实现线性探测
template
class HashTable
{
public:
HashTable(T capacity = 10)
:_tables(new T[capacity])
,_states(new State[capacity])
,_capacity(capacity)
,_size(0)
{
for(size_t i=0;i < _capacity;++i)
{
_states[i] = EMPTY;
}
}
~HashTable()
{
delete[] _tables;
delete[] _states;
_tables = NULL;
_states = NULL;
}
HashTable(const HashTable& ht) //拷贝构造
{
_tables = new T[ht._capacity];
_states = new State[ht._capacity];
for(size_t i=0;i& operator=(const HashTable& ht) //赋值操作符重载
//{
// if(this != &ht)
// {
// delete[] _tables;
// delete[] _states;
// _tables = new T[ht._capacity];
// _states = new State[ht._capacity];
// for(size_t i=0;i& operator=(HashTable ht) //赋值操作符重载
{
this->Swap(ht);
return *this;
}
public:
bool Insert(const T& key) //插入
{
_CheckCapacity();
size_t index = HashFunc(key);
while(_states[index] == EXITS)
{
if(_tables[index] == key) //冗余
{
return false;
}
++index;
if(index == _capacity) //到达哈希表尾部
{
index = 0;
}
}
_tables[index] = key;
_states[index] = EXITS;
++_size;
return true;
}
bool Find(const T& key) //查找
{
size_t index = HashFunc(key);
size_t start = index;
while(_states[index] == EXITS)
{
if(_tables[index] == key)
{
return true;
}
++index;
if(index == _capacity)
{
index = 0;
}
if(start == index) //哈希表查完
{
return false;
}
}
return false;
}
bool Remove(const T& key) //删除
{
size_t index = HashFunc(key);
size_t start = index;
while(_states[index] == EXITS)
{
if(_tables[index] == key)
{
_states[index] = DELETE;
return true;
}
++index;
if(index == _capacity) //到达哈希表的尾部
{
index = 0;
}
if(start == index) //哈希表查完
{
return false;
}
}
return false;
}
public:
size_t HashFunc(const T& key) //哈希函数
{
return key%10;
}
void _CheckCapacity() //检查容量
{
if(_size*10 % _capacity == 7) //载荷因子
{
HashTable tmp(2*_capacity);
for(size_t i=0;i<_capacity;++i)
{
if(_states[i] == EXITS)
{
tmp.Insert(_tables[i]);
}
}
Swap(tmp);
}
}
void Swap(HashTable& ht)
{
swap(_tables,ht._tables);
swap(_states,ht._states);
swap(_size,ht._size);
swap(_capacity,ht._capacity);
}
void Print()
{
for(size_t i=0;i<_capacity;++i)
{
cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<" ";
}
cout<
//class HashTableSecond
//{
//public:
// HashTableSecond(T capacity = 10)
// :_tables(new T[capacity])
// ,_states(new State[capacity])
// ,_capacity(capacity)
// ,_size(0)
// {
// for(size_t i=0;i < _capacity;++i)
// {
// _states[i] = EMPTY;
// }
// }
//
// ~HashTableSecond()
// {
// delete[] _tables;
// delete[] _states;
// _tables = NULL;
// _states = NULL;
// }
//
// HashTableSecond(const HashTableSecond& ht) //拷贝构造
// {
// _tables = new T[ht._capacity];
// _states = new State[ht._capacity];
// for(size_t i=0;i tmp(2*_capacity);
// for(size_t i=0;i<_capacity;++i)
// {
// if(_states[i] == EXITS)
// {
// tmp.Insert(_tables[i]);
// }
// }
// Swap(tmp);
// }
// }
//
// void Swap(HashTableSecond& ht)
// {
// swap(_tables,ht._tables);
// swap(_states,ht._states);
// swap(_size,ht._size);
// swap(_capacity,ht._capacity);
// }
//
// void Print()
// {
// for(size_t i=0;i<_capacity;++i)
// {
// cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<" ";
// }
// cout<
struct HashTableNode //节点
{
T key;
K value;
};
template
struct __HashFunc //重载()
{
size_t operator()(const T& key)
{
return key;
}
};
template<>
struct __HashFunc //特化
{
size_t operator()(const string& key)
{
size_t hash = 0;
for(size_t i=0;i >
class HashTableSecond
{
public:
HashTableSecond(size_t capacity = 10)
:_tables(new HashTableNode[capacity])
,_states(new State[capacity])
,_capacity(capacity)
,_size(0)
{
for(size_t i=0;i < _capacity;++i)
{
_states[i] = EMPTY;
}
}
~HashTableSecond()
{
delete[] _tables;
delete[] _states;
_tables = NULL;
_states = NULL;
}
public:
bool Insert(const T& key,const K& value) //插入
{
_CheckCapacity();
size_t start = __HashFunc(key);
size_t index = start;
size_t i = 1;
while(_states[index] == EXITS)
{
if(_tables[index].key == key)
{
return false;
}
index = start + i * i;
++i;
index %= _capacity;
}
_tables[index].key = key;
_tables[index].value = value;
_states[index] = EXITS;
++_size;
return true;
}
HashTableNode* Find(const T& key) //查找
{
size_t start = __HashFunc(key);
size_t index = start;
size_t i = 1;
while(_states[index] == EXITS)
{
if(_tables[index].key == key)
{
return &(_tables[index]);
}
index = start + i * i;
++i;
index %= _capacity;
}
return NULL;
}
bool Remove(const T& key) //删除
{
size_t start = __HashFunc(key);
size_t index = start;
size_t i = 1;
while(_states[index] == EXITS)
{
if(_tables[index].key == key)
{
_states[index] = DELETE;
return true;
}
index = start + i * i;
++i;
}
return false;
}
public:
size_t __HashFunc(const T& key) //哈希函数
{
HashFunc hfun;
return hfun(key)%_capacity;
}
void _CheckCapacity() //检测容量
{
if(_size*10 % _capacity == 7)
{
HashTableSecond tmp(2*_capacity);
for(size_t i=0;i<_capacity;++i)
{
if(_states[i] == EXITS)
{
tmp.Insert(_tables[i].key,_tables[i].value);
}
}
Swap(tmp);
}
}
void Swap(HashTableSecond& ht)
{
swap(_tables,ht._tables);
swap(_states,ht._states);
swap(_size,ht._size);
swap(_capacity,ht._capacity);
}
void Print()
{
for(size_t i=0;i<_capacity;++i)
{
cout<<"["<<_tables[i].key<<","<<_tables[i].value<<"]"<<" ";
}
cout<* _tables; //哈希表
State* _states; //状态表
size_t _size; //数据的个数
size_t _capacity; //容量
};
网站栏目：哈希表/散列表
网页链接：
http://cdxtjz.cn/article/jgdgjg.html
