1 基本知识
Hash Table-散列表/哈希表，是根据关键字（key）而直接访问在内存存储位置的数据结构。它通过一个关键值的函数将所需的数据映射到表中的位置来访问数据，这个映射函数叫做散列函数，存放记录的数组叫做散列表。
1.1 构造哈希表的方法
1）直接定址法–取关键字的某个线性函数为散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B为常数。
2）除留余数法–取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。Hash（Key）= Key % P。
3）平方取中法
4）折叠法
5）随机数法
6）数学分析法
1.2 哈希表优缺点
优点：速度快（插入和查找）
缺点：基于数组，不能有序的遍历
键值对存储方式，通过键来访问值
hashMap.put( key , value );
1.3 哈希冲突和解决方法
哈希冲突：不同的Key值经过哈希函数Hash(Key)处理以后可能产生相同的值哈希地址，我们称这种情况为哈希冲突。任意的散列函数都不能避免产生冲突。例如：如果碰到两个不同的关键字key1≠key2，但却有相同的f(key1)=f(key2)，这种现象称为冲突，并把key1和key2称为这个散列函数的同义词。
散链表的载荷因子
散链表的载荷因子定义为：a=填入表的元素个数/散列表的长度
a是散列表装满程度的标志因子，由于表长是定值，a与填入表中的元素个数成正比，a越大，表示填入表中的元素越多，产生冲突的可能性越大；a越小，填入表中的元素越少，产生冲突的可能性越小；散列表的平均查找长度是载荷因子a的函数，只是不同处理冲突的方法有不同的函数。
对于开放定址法，载荷因子是特别重要的因素，一般限制在0.7-0.8以下。超过时应resize散列表。
解决方法
解决哈希冲突有两种方法：
1)开放地址法：1>线性探测2>二次探测
2)链地址法
1.4 算法时间复杂度分析
采用哈希表作为数据结构的存储系统中，根据关键字的值可快速定位到相应的地址上，在采用开放定址法时仅需O(1)复杂度就可找到，在采用链地址法时，需要O(N)复杂度，主要在链表中搜索，相对于搜索树的O(lg(N))的复杂度，开放定址法显然来得快，但是哈希表的长度会变得非常长，采用链地址法时快速定位到相应的头结点中，只需在链表中循环遍历即可，编程难度比树降低了不少，还可以将链地址法中哈希表数组中的指针指向一个树，这样在搜索时，快速定位到搜索树的根节点，根据树的对数搜索复杂度，更可快速的找到元素,比如说，红黑树，B树..
2 代码实现
//HashTable.h
#pragma once
#include<vector>
#include<utility>
#include<string>
namespace OPEN
{
enum State
{
EMPTY = 1,
EXITS = 2,
DELETE = 3,
};
template<class K, class V>
struct HashNode
{
K _key;
V _value;
State _state;
HashNode(const K& key = K(), const V& value = V())
:_key(key)
, _value(value)
, _state(EMPTY)
{}
};
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct Hash<string>//特化，使得缺省时，若调string,则调用此函数
{
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);
}
size_t operator()(const string& key)
{
return BKDRHash(key.c_str());
}
};
template<class K, class V, class _HashFunc = Hash<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
:_size(0)
{}
size_t HashFunc(const K&key)//取模
{
_HashFunc hf;
return hf(key) % _tables.size();
}
void CheckCapacity()
{
if (_tables.size() == 0 || _size * 10 / _tables.size() >= 7)//当大于载荷因子，扩容后要重新映射
{
size_t newsize = _tables.size() * 2;
if (newsize == 0)
{
newsize = 10;
}
HashTable<K, V, _HashFunc> newht;
newht._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._state == EXITS)
{
newht.Insert(_tables[i]._key, _tables[i]._value);
}
}
_tables.swap(newht._tables);
}
}
bool Insert(const K& key, const V& value)
{
CheckCapacity();
if (Find(key))
{
return false;
}
size_t i = 1;
size_t index = HashFunc(key);
size_t start = index;
while (_tables[index]._state == EXITS)
{
index = start + i*i;
index = index%_tables.size();
++i;
//++index;//线性探测
if (index == _tables.size())
{
index = 0;
}
}
_tables[index]._key = key;
_tables[index]._value = value;
_tables[index]._state = EXITS;
_size++;
return true;
}
Node* Find(const K& key)
{
size_t index = HashFunc(key);
size_t start = index;
int i = 1;
while (_tables[index]._state != EMPTY)
{
if (_tables[index]._key == key)
{
if (_tables[index]._state == EXITS)
{
return &_tables[index];
}
else
{
return NULL;
}
}
//++index;
index = start + i*i;
index = index%_tables.size();
++i;
if (index == _tables.size())
{
index = 0;
}
}
return NULL;
}
bool Remove(const K& key)
{
Node* node = Find(key);
if (node)
{
node->_state = DELETE;
--_size;
return true;
}
else
{
return false;
}
}
private:
std::vector<Node> _tables;
size_t _size;
};
}测试代码：
//Test.cpp
#include<iostream>
#include<utility>
#include"HashTable.h"
using namespace std;
void TestHashTable()
{
int a[] = { 89, 18, 49, 58, 9};
HashTable<int, int> ht;
for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
ht.Insert(a[i],i);
}
HashTable<string, string> dict;
dict.Insert("sort", "排序");
dict.Insert("left", "剩余");
}
int main()
{
TestHashTable();
system("pause");
return 0;
}