成都创新互联主要从事网站建设、成都网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务察布查尔锡伯,10余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220
HashTable-散列表/哈希表，是根据关键字（key）而直接访问在内存存储位置的数据结构。
它通过一个关键值的函数将所需的数据映射到表中的位置来访问数据，这个映射函数叫做散列函数，存放记录的数组叫做散列表。
构造哈希表的方法：
1.直接定址法--取关键字的某个线性函数为散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B为常数。
2.除留余数法--取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。Hash（Key）= Key % P。
3.平方取中法
4.折叠法
5.随机数法
6.数学分析法
常用方法为直接定址法，除留余数法。
K类型代码：
#pragma once
#include
enum Status
{
EXIST,
DELETE,
EMPTY,
};
// 仿函数
template
struct DefaultHashFuncer
{
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 + (unsigned char)(*str++);
}
return (hash & 0x7FFFFFFF);
}
template<>
struct DefaultHashFuncer
{
size_t operator()(const string& str)
{
//size_t value = 0;
//for (size_t i = 0; i < str.size(); ++i)
//{
// value += str[i];
//}
//return value;
return BKDRHash(str.c_str());
}
};
template >
class HashTable
{
public:
HashTable()
:_tables(NULL)
,_status(NULL)
,_size(0)
,_capacity(0)
{}
HashTable(size_t size)
:_tables(new K[size])
,_status(new Status[size])
,_size(0)
,_capacity(size)
{
//memset(_status, 0, sizeof(Status)*_size);
for (size_t i = 0; i < _capacity; ++i)
{
_status[i] = EMPTY;
}
}
HashTable(const HashTable& ht)
{
HashTable tmp(ht._capacity);
for (size_t )
{}
}
HashTable& operator=(HashTable ht);
~HashTable()
{
if (_tables)
{
delete[] _tables;
delete[] _status;
}
_size = 0;
_capacity = 0;
}
bool Insert(const K& key)
{
/*if (_size == _capacity)
{
cout<<"Full"<& ht)
{
swap(_tables, ht._tables);
swap(_size, ht._size);
swap(_status, ht._status);
swap(_capacity, ht._capacity);
}
size_t _HashFunc(const K& key)
{
//
//return key%_capacity;
HashFuncer hf;
return hf(key)%_capacity;
}
void PrintTables()
{
for (size_t i = 0 ; i < _capacity; ++i)
{
if (_status[i] == EXIST)
{
printf("[%d]:E->", i);
cout<<_tables[i];
}
else if (_status[i] == DELETE)
{
printf("[%d]:D->", i);
cout<<_tables[i];
}
else
{
printf("[%d]:N", i);
}
cout<= _capacity*7)
{
/*K* tmpTables = new K[2*_capacity];
K* tmpStatus = new Status[2*_capacity];
for(size_t i = 0; i < _capacity; ++i)
{
if ()
{
}
}*/
HashTable tmp(2*_capacity);
for (size_t i = 0; i < _capacity; ++i)
{
if (_status[i] == EXIST)
{
tmp.Insert(_tables[i]);
}
}
this->Swap(tmp);
}
}
protected:
K* _tables;
Status* _status;
size_t _size;
size_t _capacity;
};
a:变量分析：
1.K类型的数组，用来存储key。
2.Status类型的数组，用来标志每一个位置状态。
3._size,用于表示有效数据个数。
4._capacity，容量
b:难点分析
1.使用仿函数计算不同类型数据的Key。
2.处理哈希冲突以及载荷因子。
KV类型的代码
#pragma once
#include
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
struct DefaultHashFuncer
{
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 + (unsigned char)(*str++);
}
return (hash & 0x7FFFFFFF);
}
template<>
struct DefaultHashFuncer
{
size_t operator()(const string& str)
{
//size_t value = 0;
//for (size_t i = 0; i < str.size(); ++i)
//{
// value += str[i];
//}
//return value;
return BKDRHash(str.c_str());
}
};
template >
class HashTable
{
typedef KeyValue KV;
public:
HashTable(size_t size)
:_tables(new KV[size])
,_status(new Status[size])
,_size(0)
,_capacity(size)
{
//memset(_status, 0, sizeof(Status)*_size);
for (size_t i = 0; i < _capacity; ++i)
{
_status[i] = EMPTY;
}
}
~HashTable()
{
if (_tables)
{
delete[] _tables;
delete[] _status;
}
_size = 0;
_capacity = 0;
}
bool Insert(const K& key, const V& value)
{
if (_size == _capacity)
{
cout<<"Full"<同理上面K类型，不同的是_tables的每一个元素是一个KeyValue类型的结构体。
处理哈希冲突的闭散列方法
1.线性探测
2.二次探测
以上就是本人在学习过程中的一些经验总结。当然，本人能力有限，难免会有纰漏，希望大家可以指正。
分享文章：HashTable
分享网址：http://njwzjz.com/article/giheod.html
