散列表（Hash table，也叫哈希表），是根据关键字（Key value）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
在吉隆等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站设计制作、做网站 网站设计制作按需开发,公司网站建设,企业网站建设,高端网站设计,网络营销推广,成都外贸网站制作,吉隆网站建设费用合理。
应用：
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名
到首字母
的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则
，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
基本概念：
查找效率：
散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：
散列函数是否均匀；
处理冲突的方法；
散列表的载荷因子
载荷因子：
散列表的载荷因子定义为：
= 填入表中的元素个数 / 散列表的长度。
是散列表装满程度的标志因子。由于表长是定值，与“填入表中的元素个数”成正比，所以，越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子的函数，只是不同处理冲突的方法有不同的函数。
构造哈希表的几种方法：
直接定址法--取关键字的某个线性函数为散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B为常数。
除留余数法--取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。Hash（Key）= Key % P。
平方取中法
折叠法
随机数法
数学分析法
线性探测：
#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;
#include
#include
enum Statue //标记一个数的存在状态
{
EXIST,
DELETE,
EMPTY
};
template //定义类型
struct HashNode
{
K _key;
V _value;
Statue statue;
HashNode(const K& key, const V& value)
:_key(key),
_value(value),
statue(EXIST)
{}
HashNode()
:statue(EMPTY)
{}
};
template
struct _HashFuncDefault
{
size_t operator()(const K& key)
{
return key;
}
};
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);
}
template<>
struct _HashFuncDefault
{
size_t operator()(const string str)
{
return BKDRHash(str.c_str());
}
};
template>
class HashTable
{
typedef HashNode Node;
public:
HashTable()
:_size(0)
{
for (size_t i = 0; i < _table.size(); i++)
{
_table[i].statue = EMPTY;
}
}
bool Insert(const K& key, const V& value)
{
_CheckCapaciy();
size_t index = _HashFunc(key,_table.size());
size_t tmp = index;
if (_table[index]._key == key)//已经有这个数
{
return false;
}
if (_table[index].statue == EXIST)
{
++index;
while (index != tmp) //保证不走过一圈
{
if (index == _table.size()) //到最后一个就从第一个开始
{
index = 0;
}
if (_table[index].statue != EXIST)//找到可以插入的位置
{
break;
}
if (_table[index]._key == key)//已经有这个数
{
return false;
}
++index;
}
}
_table[index].statue = EXIST;
_table[index]._key = key;
_table[index]._value = value;
++_size;
return true;
}
void Remove(const K& key)
{
size_t index = _HashFunc(key, _table.size());
size_t tmp = index;
if (_table[index]._key != key)
{
++index;
while (index != tmp)
{
if (index == _table.size())
{
index = 0;
}
if (_table[index]._key == key)
{
break;
}
++index;
}
}
if (_table[index]._key == key)
{
_table[index].statue = DELETE;
--_size;
return;
}
return;
}
int Find(const K& key)
{
size_t index = _HashFunc(key, _table.size());
size_t tmp = index;
if (_table[index]._key == key && _table[index].statue == EXIST)
{
return index;
}
else
{
++index;
while (index != tmp)
{
if (index == _table.size())
{
index = 0;
}
if (_table[index]._key == key && _table[index].statue == EXIST)
{
break;
}
++index;
}
}
if (_table[index]._key == key && _table[index].statue == EXIST)
{
return index;
}
return -1;
}
void Print()
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i].statue == EXIST)
{
cout << "KEY:" << _table[i]._key << " " << "VALUE:" << _table[i]._value<< " " << "STATUE:" << _table[i].statue << endl;
}
}
}
protected:
size_t _HashFunc(const K& key, size_t capacity)
{
_HashFuncer hf;
return hf(key) % capacity;
}
void _CheckCapaciy()
{
if (_size * 10 >= _table.size())
{
const int _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
};
size_t newCapacity = 0;
for (size_t i = 0; i < _PrimeSize; i++)
{
if (_table.size() < _PrimeList[i])
{
newCapacity = _PrimeList[i];
break;
}
}
HashTable tmp;
tmp._table.resize(newCapacity);
for (size_t i = 0; i < _table.size(); i++)
{
tmp.Insert(_table[i]._key, _table[i]._value);
}
Swap(tmp);
}
}
void Swap(HashTable& tem)
{
swap(_table, tem._table);
tem._size = _size;
}
private:
vector _table;
size_t _size;
};
void test()
{
HashTable ht;
ht.Insert("hello", "你好");
ht.Insert("hello", "你好");
ht.Insert("change", "改变");
ht.Insert("world", "世界");
ht.Insert("change", "改变");
ht.Insert("xi'an", "西安");
ht.Remove("hello");
int ret = ht.Find("world");
ht.Print();
}
int main()
{
test();
system("pause");
return 0;
}
二次探测：
#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;
enum Status
{
EXIST,
DELETE,
EMPTY
};
template
struct KeyValue
{
K _key;
V _value;
KeyValue(const K& key = K(), const V& value = V())
:_key(key),
_value(value)
{}
};
template
class HashTable
{
typedef KeyValue type;
public:
HashTable()
:_table(NULL),
_size(0),
_capacity(0),
_status(EMPTY)
{}
HashTable(const size_t& size)
:_table(new type[size]),
_size(0),
_capacity(size),
_status(new Status[size])
{
for (size_t i = 0; i < size; i++)
{
_status[i] = EMPTY;
}
}
bool Insert(const K& key, const V& value);
void Print();
int Find(const K& key);
void Remove(const K& key);
~HashTable();
protected:
void _Swap(HashTable& tmp);
size_t _HashFunc(const K& key, size_t i);
private:
type* _table;
size_t _size;
size_t _capacity;
Status* _status;
};
template
bool HashTable::Insert(const K& key, const V& value)
{
if (_size * 10 >= _capacity * 8)//负载因子
{
size_t newcapacity = 2 * _capacity;
HashTable tmp(newcapacity);
for (size_t i = 0; i < _capacity; i++)
{
tmp.Insert(_table[i]._key, _table[i]._value);
}
this->_Swap(tmp);
}
size_t i = 0;//计数器
size_t index = _HashFunc(key, i);//计算下标
size_t begin = index;
do
{
if (_status[index] == EMPTY || _status[index] == DELETE)//是空或者已经删除
break;
if (_status[index] == EXIST && _table[index]._key == key)//已经有这个数
return true;
index = _HashFunc(key, ++i);
if (index == _capacity)
index = 0;
} while (begin != index);
if (_status[index] == EXIST)
return false;
_table[index]._key = key;
_table[index]._value = value;
_status[index] = EXIST;
++_size;
return true;
}
template
void HashTable::_Swap(HashTable& tmp)
{
swap(_table, tmp._table);
swap(_size, tmp._size);
swap(_capacity, tmp._capacity);
swap(_status, tmp._status);
}
template
size_t HashTable::_HashFunc(const K& key, size_t i)
{
size_t ret = (key + i*i) % _capacity;
return ret;
}
template
void HashTable::Print()
{
for (size_t i = 0; i < _capacity; i++)
{
printf("第%d个 key: %d value: %d status: %d \n", i, _table[i]._key, _table[i]._value, _status[i]);
}
}
template
int HashTable::Find(const K& key)
{
int i = 0;
size_t index = _HashFunc(key,i);
if (_table[index]._key == key && _status[index]==EXIST)
{
return index;
}
else
{
int begin = index;
++index;
while (index != begin)
{
if (_table[index]._key == key && _status[index] == EXIST)
{
return index;
}
index = _HashFunc(key, ++i);
}
}
return -1;
}
template
void HashTable::Remove(const K& key)
{
int i = 0;
size_t index = _HashFunc(key, i);
if (_table[index]._key == key && _status[index] == EXIST)
{
_status[index] = DELETE;
return;
}
else
{
int begin = index;
++index;
while (index != begin)
{
if (_table[index]._key == key && _status[index] == EXIST)
{
_status[index] = DELETE;
return;
}
index = _HashFunc(key, ++i);
}
}
}
template
void HashTable::~HashTable()
{
if (_table)
{
delete[] _table;
}
}
void test()
{
HashTableha(2);
ha.Insert(0, 1);
ha.Insert(1, 2);
ha.Insert(2, 5);
ha.Insert(3, 8);
ha.Insert(4, 9);
ha.Insert(6, 0);
ha.Print();
int ret=ha.Find(3);
ha.Remove(4);
ha.Print();
}
int main()
{
test();
system("pause");
return 0;
}
名称栏目：哈希表的实现
文章分享：
http://cdkjz.cn/article/jddeci.html
的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系
为散列函数，按这个思想建立的表为散列表。
，而
，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数