溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
HashTable-散列表/哈希表，是根據(jù)關(guān)鍵字（key）而直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。
它通過一個(gè)關(guān)鍵值的函數(shù)將所需的數(shù)據(jù)映射到表中的位置來訪問數(shù)據(jù)，這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
構(gòu)造哈希表的方法：
1.直接定址法--取關(guān)鍵字的某個(gè)線性函數(shù)為散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B為常數(shù)。
2.除留余數(shù)法--取關(guān)鍵值被某個(gè)不大于散列表長m的數(shù)p除后的所得的余數(shù)為散列地址。Hash（Key）= Key % P。
3.平方取中法
4.折疊法
5.隨機(jī)數(shù)法
6.數(shù)學(xué)分析法
常用方法為直接定址法，除留余數(shù)法。
K類型代碼：
#pragma once
#include <string>
enum Status
{
EXIST,
DELETE,
EMPTY,
};
// 仿函數(shù)
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類型的數(shù)組，用來存儲(chǔ)key。
2.Status類型的數(shù)組，用來標(biāo)志每一個(gè)位置狀態(tài)。
3._size,用于表示有效數(shù)據(jù)個(gè)數(shù)。
4._capacity，容量
b:難點(diǎn)分析
1.使用仿函數(shù)計(jì)算不同類型數(shù)據(jù)的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的每一個(gè)元素是一個(gè)KeyValue<K,V>類型的結(jié)構(gòu)體。
處理哈希沖突的閉散列方法
1.線性探測
2.二次探測
以上就是本人在學(xué)習(xí)過程中的一些經(jīng)驗(yàn)總結(jié)。當(dāng)然，本人能力有限，難免會(huì)有紕漏，希望大家可以指正。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼