溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
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.二次探測
以上就是本人在學習過程中的一些經驗總結。當然，本人能力有限，難免會有紕漏，希望大家可以指正。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
