數據結構哈希表的閉散列基本實現(xiàn)-創(chuàng)新互聯(lián)

#pragma once

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

#include<string>

using namespace std;

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

{

EXITS,

DELETE,

EMPTY,

};

template<class K,class V>

struct KeyValueNode//KV鍵值對

{

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>//仿函數

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;

};

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

文章題目：數據結構哈希表的閉散列基本實現(xiàn)-創(chuàng)新互聯(lián)
網頁地址：http://muchs.cn/article22/dpdhjc.html

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

廣告

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

網站建設網站維護公司