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 <string>
enum Status
{
EXIST,
DELETE,
EMPTY,
};
// 仿函數
template<class K>
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<string>
{
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 K, class HashFuncer = DefaultHashFuncer<K> >
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<K, HashFuncer>& ht)
{
HashTable<K, HashFuncer> tmp(ht._capacity);
for (size_t )
{}
}
HashTable<K, HashFuncer>& operator=(HashTable<K, HashFuncer> ht);
~HashTable()
{
if (_tables)
{
delete[] _tables;
delete[] _status;
}
_size = 0;
_capacity = 0;
}
bool Insert(const K& key)
{
/*if (_size == _capacity)
{
cout<<"Full"<<endl;
return false;
}*/
_CheckCapacity();
size_t index = _HashFunc(key);
// 線性探測
while(_status[index] == EXIST)
{
if (_tables[index] == key)
{
return false;
}
++index;
if (index == _capacity)
index = 0;
}
_status[index] = EXIST;
_tables[index] = key;
++_size;
return true;
}
int Find(const K& key)
{
int i = 0;
size_t index = _HashFunc(key);
while (_status[index] != EMPTY)
{
if (_tables[index] == key
&& _status[index] != DELETE)
{
return index;
}
++i;
index = _HashFunc(key)+i*i;
++index;
if (index == _capacity)
{
index = 0;
}
}
return -1;
}
bool Remove(const K& key)
{
int index = Find(key);
if (index != -1)
{
_status[index] = DELETE;
return true;
}
return false;
}
void Swap(HashTable<K, HashFuncer>& 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<<endl;
}
}
void _CheckCapacity()
{
if (_size*10 >= _capacity*7)
{
/*K* tmpTables = new K[2*_capacity];
K* tmpStatus = new Status[2*_capacity];
for(size_t i = 0; i < _capacity; ++i)
{
if ()
{
}
}*/
HashTable<K, HashFuncer> 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 <string>
enum Status
{
EXIST,
DELETE,
EMPTY,
};
template<class K, class V>
struct KeyValue
{
K _key;
V _value;
KeyValue(const K& key = K(), const V& value = V())
:_key(key)
,_value(value)
{}
};
template<class K>
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<string>
{
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 K, class V,
class HashFuncer = DefaultHashFuncer<K> >
class HashTable
{
typedef KeyValue<K, V> 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"<<endl;
return false;
}
//_CheckCapacity();
// 二次方探測
int i = 1;
size_t index = _HashFunc0(key);
while(_status[index] == EXIST)
{
if (_tables[index]._key == key)
{
return false;
}
index = _HashFunci(index, i++);
}
_status[index] = EXIST;
_tables[index] = KV(key, value);
++_size;
return true;
}
KV* Find(const K& key);
size_t _HashFunc0(const K& key)
{
HashFuncer hf;
return hf(key)%_capacity;
}
size_t _HashFunci(size_t prevHash, int i)
{
return (prevHash + 2*i - 1)%_capacity;
}
protected:
KV* _tables;
Status* _status;
size_t _size;
size_t _capacity;
}; 同理上面K類型，不同的是_tables的每一個元素是一個KeyValue<K,V>類型的結構體。
處理哈希沖突的閉散列方法
1.線性探測
2.二次探測
![DataTable..::.ToString 方法[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)