柚子快報(bào)邀請(qǐng)碼778899分享：【C++】哈希桶

http://yzkb.51969.com/

前言

哈希桶是哈希表中用于存儲(chǔ)數(shù)據(jù)的基本單元，也稱為哈希槽或存儲(chǔ)桶。

哈希桶（Hash Bucket）** 是哈希表數(shù)據(jù)結(jié)構(gòu)中的一個(gè)概念。、哈希表通過(guò)哈希函數(shù)將輸入數(shù)據(jù)映射到一個(gè)存儲(chǔ)位置，而哈希桶就是這些存儲(chǔ)位置中的一個(gè)單元。哈希桶用于存放哈希表中的元素，當(dāng)不同的元素經(jīng)過(guò)哈希函數(shù)映射到同一個(gè)桶時(shí)，通常通過(guò)鏈表或其他結(jié)構(gòu)來(lái)存儲(chǔ)這些元素。這種情況稱為 哈希沖突。

哈希桶的工作機(jī)制

哈希函數(shù)的作用：哈希函數(shù)根據(jù)輸入元素計(jì)算出一個(gè)整數(shù)值，稱為哈希值，然后根據(jù)哈希值來(lái)決定元素存儲(chǔ)在哪個(gè)桶中。 假設(shè)哈希表的桶數(shù)為 num_buckets，元素 key 的哈希值為 hash(key)，則該元素將被存儲(chǔ)在 hash(key) % num_buckets 這個(gè)桶中。 哈希沖突：由于哈希表的容量有限，而插入的元素可能很多，因此會(huì)有多個(gè)元素映射到同一個(gè)桶。這就是哈希沖突。 沖突解決方式：當(dāng)發(fā)生哈希沖突時(shí)，哈希桶中的元素通常會(huì)存儲(chǔ)在某種結(jié)構(gòu)中。常見(jiàn)的沖突解決方式包括：

拉鏈法：在每個(gè)哈希桶中維護(hù)一個(gè)鏈表，當(dāng)多個(gè)元素映射到同一個(gè)桶時(shí)，這些元素會(huì)依次插入鏈表中。開(kāi)放尋址法：當(dāng)某個(gè)桶已經(jīng)有元素時(shí)，尋找下一個(gè)空的桶來(lái)存儲(chǔ)沖突的元素。參考

哈希桶示例

例如，一個(gè)哈希表有 5 個(gè)桶（編號(hào)為 0-4），通過(guò)簡(jiǎn)單的哈希函數(shù) hash(key) = key % 5 來(lái)決定桶的位置。

//假設(shè)插入的元素為：12, 7, 5, 10, 15, 9

hash(12) = 12 % 5 = 2

hash(7) = 7 % 5 = 2

hash(5) = 5 % 5 = 0

hash(10) = 10 % 5 = 0

hash(15) = 15 % 5 = 0

hash(9) = 9 % 5 = 4

最終得到的哈希桶分布如下：

桶 0：5 -> 10 -> 15桶 1：（空）桶 2：12 -> 7桶 3：（空）桶 4：9

其中：

桶 0 通過(guò)拉鏈法存儲(chǔ)了 5、10 和 15，使用鏈表處理沖突。桶 2 同樣存儲(chǔ)了 12 和 7。

哈希桶的實(shí)現(xiàn)

存儲(chǔ)結(jié)構(gòu)

類(lèi)似于鏈表，在順序表中存儲(chǔ)一個(gè)一個(gè)節(jié)點(diǎn)?！?/p>

template

struct defaultHashfunc

{

size_t operator()(const T& data)

{

return (size_t)data;

}

};

table：使用 std::vector 存儲(chǔ)多個(gè)鏈表，每個(gè)鏈表代表一個(gè)桶，鏈表中的元素是映射到這個(gè)桶的所有元素。記錄_n進(jìn)行負(fù)載因子的儲(chǔ)存

template>

class HashTable

{

public:

...

private:

vector _table;

size_t _n = 0;

};

哈希函數(shù)

在函數(shù)的內(nèi)容的不確定的時(shí)候進(jìn)行返回。針對(duì)string字符串的直接進(jìn)行特模板化。針對(duì)26字母有不同的組合，要進(jìn)行字符串的哈?；幚恚康氖轻槍?duì)哈希沖突 （本次采用 BKDR算法）參考：字符串哈希算法

template

struct defaultHashfunc

{

size_t operator()(const T& data)

{

return (size_t)data;

}

};

//string特化

template<>

struct defaultHashfunc

{

size_t operator()(const string& str)

{

size_t hash = 0;

for (auto& ch : str)

{

hash *= 131;

hash += ch;

}

return hash;

}

};

插入操作

哈希桶插入步驟：

計(jì)算哈希值： 使用哈希函數(shù) hash(key) 將鍵值（key）映射為一個(gè)整數(shù)，稱為 哈希值。這個(gè)哈希值決定了 key 應(yīng)該被存儲(chǔ)在哪個(gè)桶中。 定位桶：根據(jù)哈希值和哈希表的大?。ㄍ暗臄?shù)量），確定目標(biāo)桶的位置。常用的方式是：bucket = hash(key) % num_buckets，其中 num_buckets 是哈希表的桶數(shù)量。 檢查沖突：定位到目標(biāo)桶后，檢查桶中是否已經(jīng)存在與 key 相同的元素。如果已經(jīng)存在，則插入操作可以直接結(jié)束（因?yàn)榧喜辉试S重復(fù)元素），否則繼續(xù)進(jìn)行。 插入元素： 如果目標(biāo)桶中不存在相同的元素，直接將元素插入到該桶中。對(duì)于拉鏈法，目標(biāo)桶通常使用鏈表（或類(lèi)似結(jié)構(gòu)）存儲(chǔ)多個(gè)元素，因此新元素會(huì)被插入到鏈表末尾。 哈希桶的擴(kuò)容： 如果大小不夠，一個(gè)桶的元素過(guò)于多，就需要進(jìn)行擴(kuò)容，創(chuàng)建一個(gè)新表進(jìn)行插入操作。

bool insert(const T& data)

{

HashFunc hf;

bool it = Find(kot(data));

if (it)

{

return false;

}

if (_n == _table.size())

{

size_t newsize = _table.size() * 2;

vector newtable;

newtable.resize(newsize,nullptr);

for (int i = 0; i < _table.size() ;i++)

{

HashFunc hf;

size_t hashi = 0;

Node* cur = _table[i];

while (cur)

{

Node* next = cur->_next;

hashi = hf(cur->_data) % newtable.size();

cur->_next = newtable[hashi];

newtable[hashi] = cur;

cur = next;

}

_table[i] = nullptr;

}

_table.swap(newtable);

}

size_t hashi = hf(data) % _table.size();

Node* newnode = new Node(data);

newnode->_next = _table[hashi];

_table[hashi] = newnode;

++_n;

return true;

}

插入效率：

時(shí)間復(fù)雜度：哈希桶的插入操作通常情況下的時(shí)間復(fù)雜度為 O(1)，因?yàn)楣：瘮?shù)能夠在常數(shù)時(shí)間內(nèi)定位到桶的位置。然而，最壞情況下（所有元素都被映射到同一個(gè)桶中），時(shí)間復(fù)雜度退化為 O(n)，其中 n 是桶中元素的數(shù)量。空間復(fù)雜度：哈希表的空間復(fù)雜度與桶的數(shù)量和元素?cái)?shù)量成正比，通常為 O(n)。

刪除操作

哈希桶刪除步驟：

計(jì)算哈希值： 使用哈希函數(shù) hash(key) 計(jì)算出元素的哈希值，找到元素應(yīng)該所在的桶。 定位桶： 根據(jù)哈希值和哈希表的桶數(shù)量，確定目標(biāo)桶的位置，通常通過(guò)：bucket = hash(key) % num_buckets 來(lái)找到對(duì)應(yīng)的桶。 遍歷桶中的元素： 在找到的桶中，遍歷桶中存儲(chǔ)的所有元素（通常是通過(guò)鏈表存儲(chǔ)），尋找需要?jiǎng)h除的元素。 刪除元素： 一旦找到目標(biāo)元素，將其從桶中刪除（對(duì)于拉鏈法，通常是從鏈表中刪除元素）。如果該元素不存在，則無(wú)需做任何操作。

bool Erase(const K& key)

{

HashFunc hf;

size_t hashi = hf(key) % _table.szie();

Node* cur = _table[hashi];

Node* prev = nullptr;

while (cur)

{

if (cur->_data == key)

{

if (prev == nullptr)

{

_table[hashi] = cur->_next;

}

else

{

prev->_next = cur->_next;

}

delete cur;

--_n;

return true;

}

prev = cur;

cur = cur->_next;

}

return false;

}

時(shí)間復(fù)雜度分析：

最佳情況：每個(gè)桶中只有一個(gè)元素或哈希函數(shù)將元素均勻分布到桶中，刪除操作的時(shí)間復(fù)雜度為 O(1)，因?yàn)橹恍枵业酵昂笾苯觿h除即可。 最壞情況：所有元素都被映射到同一個(gè)桶中，導(dǎo)致鏈表長(zhǎng)度等于元素?cái)?shù)量。在這種情況下，刪除操作的時(shí)間復(fù)雜度為 O(n)，其中 n 是鏈表中的元素?cái)?shù)量。 平均情況：如果哈希函數(shù)分布較好，鏈表的長(zhǎng)度較短，刪除操作的平均時(shí)間復(fù)雜度為 O(1)

查找操作

哈希桶查找步驟：

計(jì)算哈希值：使用哈希函數(shù) hash(key) 計(jì)算出需要查找的元素的哈希值，找到元素應(yīng)該存儲(chǔ)的桶。定位桶：根據(jù)哈希值，計(jì)算出目標(biāo)桶的索引。常用的方式是：bucket = hash(key) % num_buckets，其中 num_buckets 是哈希表的桶數(shù)量。在桶內(nèi)查找： 如果該桶為空，直接返回元素不存在。如果桶內(nèi)有元素，遍歷桶中的鏈表或數(shù)組，逐個(gè)檢查每個(gè)元素是否與要查找的鍵值相等。返回結(jié)果：

如果找到與目標(biāo)鍵相等的元素，則返回成功查找的結(jié)果。如果遍歷完整個(gè)桶（鏈表或數(shù)組）后，未找到目標(biāo)元素，則返回查找失敗。

bool Find(const K& key)

{

HashFunc hf;

size_t hashi = hf(key) % _table.size();

Node* cur = _table[hashi];

while (cur)

{

if (kot(cur->_data) == key)

{

return true;

}

cur = cur->_next;

}

return false;

}

柚子快報(bào)邀請(qǐng)碼778899分享：【C++】哈希桶

http://yzkb.51969.com/

文章來(lái)源