#pragma once

創(chuàng)新互聯(lián)公司成立10年來(lái)，這條路我們正越走越好，積累了技術(shù)與客戶資源，形成了良好的口碑。為客戶提供網(wǎng)站設(shè)計(jì)制作、網(wǎng)站建設(shè)、網(wǎng)站策劃、網(wǎng)頁(yè)設(shè)計(jì)、主機(jī)域名、網(wǎng)絡(luò)營(yíng)銷、VI設(shè)計(jì)、網(wǎng)站改版、漏洞修補(bǔ)等服務(wù)。網(wǎng)站是否美觀、功能強(qiáng)大、用戶體驗(yàn)好、性價(jià)比高、打開快等等，這些對(duì)于網(wǎng)站建設(shè)都非常重要，創(chuàng)新互聯(lián)公司通過(guò)對(duì)建站技術(shù)性的掌握、對(duì)創(chuàng)意設(shè)計(jì)的研究為客戶提供一站式互聯(lián)網(wǎng)解決方案，攜手廣大客戶，共同發(fā)展進(jìn)步。

#include<string>

using namespace std;

enum Status//表示當(dāng)前位置的狀態(tài)

{

EXITS,

DELETE,

EMPTY,

};

template<class K,class V>

struct KeyValueNode//KV鍵值對(duì)

{

K _key;

V _value;

KeyValueNode(const K& key=K(), const V& value=V())

:_key(key)

, _value(value)

{}

};

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<class K>//仿函數(shù)

struct HashFuner

{

size_t operator() (const K& key)

{

return key;

}

};

template<>//特化

struct HashFuner<string>

{

size_t operator() (const string& key)

{

return BKDRHash(key.c_str());

}

};

template<class K,class V,class HashFun = HashFuner<K> >

class HashTable

{

typedef KeyValueNode<K, V> KVNode;

public:

HashTable()

: _tables(NULL)

, _capacity(0)

, _size(0)

, _status(0)

{}

HashTable(int capacity)

:_tables(new KVNode[capacity])

, _capacity(capacity)

, _size(0)

, _status(new Status[capacity])

{

for (int i = 0; i < capacity; ++i)

{

_status[i] = EMPTY;

}

}

HashTable(const HashTable<K, V>& ht)

:_tables(NULL)

, _status(NULL)

{

HashTable<K, V> newtable(ht._capacity);

for (int i = 0; i < _capacity; ++i)

{

_tables[i]._key = ht._tables[i]._key;

_tables[i]._value = ht._tables[i]._value;

_size = ht._size;

_status[i] = ht._status[i];

}

this->Swap(newtable);

}

HashTable<K, V>& operator=(HashTable<K, V> ht)

{

this->Swap(ht);

return *this;

}

~HashTable()

{

if (_tables)

{

delete[] _tables;

delete[] _status;

}

}

public:

bool Insert(const K& key, const V& value)

{

if (_capacity == _size)

{

HashTable<K,V> newtables(_capacity * 2 + 1);

for (size_t i = 0; i < _capacity; ++i)

{

if (_status[i] == EXITS)

{

size_t index = HashFunc0(_tables[i]._key);

while (newtables._status[i] == EXITS)

{

index = HashFunc2(index, i++);

}

newtables._tables[index] = KVNode(_tables[i]._key,_tables[i]._value);

newtables._status[index] = EXITS;

++_size;

}

}

this->Swap(newtables);

}

size_t index = HashFunc0(key);

int i = 1;

while (_status[index] == EXITS)

{

index = HashFunc2(index, i++);

}

_tables[index] = KVNode(key, value);

_status[index] = EXITS;

_size++;

return true;

}

bool Remove(const K& key)

{

size_t index = HashFunc0(key);

int i = 1;

while (_tables[index] != EMPTY)

{

if (_tables[index]._key == key)

{

if (_status[index] == EXITS)

{

--_size;

_status[index] = DELETE;

return true;

}

else

{

return false;

}

}

index = HashFunc2(index, i++);

}

return false;

}

KVNode* Find(const K& key)

{

size_t index = HashFunc0(key);

int i = 0;

while (_status[index] != EMPTY)

{

if (key == _tables[index]._key)

{

if (_status[index] == EXITS)

return &_tables[index];

else

return NULL;

}

index = HashFunc2(index, i++);

}

return NULL;

}

size_t HashFunc0(const K& key)

{

return HashFun()(key) % _capacity;

}

size_t HashFunc2(size_t prevValue, int i)

{

return (prevValue + 2 * i - 1) % _capacity;

}

void Swap(HashTable<K, V, HashFun>& ht)

{

swap(_tables, ht._tables);

swap(_status, ht._status);

swap(_size, ht._size);

swap(_capacity, ht._capacity);

}

protected:

KVNode* _tables;

int _capacity;

int _size;

Status* _status;

};

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

文章題目：數(shù)據(jù)結(jié)構(gòu)哈希表的閉散列基本實(shí)現(xiàn)-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)地址：http://jinyejixie.com/article22/dpdhjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、做網(wǎng)站、品牌網(wǎng)站制作、網(wǎng)站制作、建站公司、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)