柚子快報激活碼778899分享：【C++】哈希

http://yzkb.51969.com/

1. unordered系列關(guān)聯(lián)式容器

STL提供了底層為紅黑樹結(jié)構(gòu)的一系列關(guān)聯(lián)式容

這里介紹 unordered_set 和 unordered_map

a. unordered_map

unordered_map 是存儲鍵值對的關(guān)聯(lián)式容器，其允許通過 key 快速的索引到與

其對應的 value

unordered_map 容器通過 key 訪問單個元素要比 map 快，但它通常在遍歷元素子集的范圍迭

代方面效率較低

unordered_map 實現(xiàn)了直接訪問操作符(operator[])，它允許使用key作為參數(shù)直接訪問value它的迭代器至少是前向迭代器重復數(shù)據(jù)可以去重

b. unordered_set

unordered_set 允許通過 key 快速的索引是否存在重復數(shù)據(jù)可以去重刪除，查找，插入，效率都很快

2. unordered_map 的接口說明

a. unordered_map 的容量

函數(shù)聲明

1. bool empty() const

2. size_t size() const

功能介紹

1. 檢測unordered_map是否為空

2. 獲取unordered_map的有效元素個數(shù)

b. unordered_map 的迭代器

函數(shù)聲明

1. iterator begin()

2. iterator end()

3. iterator cbegin() const

4. iterator cend() const

功能介紹

1. 返回 unordered_map 第一個元素的迭代器

2. 返回 unordered_map 最后一個元素下一個位置的迭代器

3. 返回 unordered_map 第一個元素的const迭代器

4. 返回 unordered_map 最后一個元素下一個位置的const迭代器

c. unordered_map 的元素訪問

函數(shù)聲明

1. K& operator[]

功能介紹

1. 返回與 key 對應的 value ，允許被修改

d. unordered_map 的查詢

函數(shù)聲明

1. iterator find(const K& key)

2. size_t count(const K& key)

功能介紹

1. 返回key在哈希桶中的位置

2. 返回哈希桶中關(guān)鍵碼為key的鍵值對的個數(shù)

注意：

unordered_map 中 key 是不能重復的，因此 count函數(shù)的返回值最大為 1

e. unordered_map 的桶操作

函數(shù)聲明

1. size_t bucket_count() const

2. size_t bucket_size(size_t n) const

3. size_t bucket(const K& key)

功能介紹

1. 返回哈希桶中桶的總個數(shù)

2. 返回n號桶中有效元素的總個數(shù)

3. 返回元素key所在的桶號

注意：

unordered_set 用法差不多，就不介紹了

3. 哈希概念

通過位置關(guān)系找到對應的 key

a. 哈希沖突解決

先說上述問題的解決：

設插入的值為 key，n 為數(shù)組的大小

hashi (數(shù)組下標) = key % n (若 key 不為整數(shù)， 另做處理)

但是在插入的過程中，我們?nèi)菀子龅揭韵聠栴}：

hashi 已經(jīng)有數(shù)值存入 （這種問題又叫 哈希沖突 ）

第一種方法：（閉散列）

如果是這種情況，直接往后找，直到遇到空位置 （數(shù)組里面存入什么值都很難表示這個位置的狀態(tài)，所以我們自己可以加入）

? ? ?2. 所有的位置都有沒有位置了

這種問題一定要涉及到空間的開辟 （但是這里我們需要談論的是什么時候擴空間比較好）

注意：

這種分情況，后面實現(xiàn)再講

另外一種方法解決（開散列）：

開散列法又叫鏈地址法(開鏈法)，首先對關(guān)鍵碼集合用散列函數(shù)計算散列地址，具有相同地

址的關(guān)鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈

接起來，各鏈表的頭結(jié)點存儲在哈希表中

4. 閉散列實現(xiàn)

代碼

?

enum State

{

Empty,

Exist,

Delete

};

template

struct HashTable

{

pair _table;

State _state = Empty;

};

template

class Hsah

{

public:

bool insert(const pair& kv)

{

if (_t.size() == 0 || n * 10 / _t.size() >= 7)

{

Hsah x;

size_t size = _t.size() == 0 ? 10 : _t.size() * 2;

x._t.resize(size);

for (auto i : _t)

{

if (i._state == Exist)

{

x.insert(i._table);

}

}

_t.swap(x._t);

}

size_t hashi = kv.first % _t.size();

int index = hashi;

size_t i = 1;

while (_t[index]._state != Empty)

{

index = hashi + i;

index %= _t.size();

i++;

}

_t[index]._table = kv;

_t[index]._state = Exist;

n++;

return true;

}

HashTable* find(const K& key)

{

if (_t.size() == 0)

{

return nullptr;

}

size_t hashi = key % _t.size();

int index = hashi;

size_t i = 1;

while (_t[index]._state != Empty)

{

if (_t[index]._table.first == key)

{

if (_t[index]._state == Delete)

{

return nullptr;

}

return &_t[index];

}

index = hashi + i;

index %= _t.size();

i++;

if (index == hashi)

{

break;

}

}

return nullptr;

}

bool Erase(const K& key)

{

HashTable* t = find(key);

if (t == nullptr || t->_state == Delete)

{

return false;

}

t->_state = Delete;

}

private:

size_t n = 0;

vector> _t;

};

5. 開散列實現(xiàn)

代碼

template

struct HashNode

{

HashNode(const pair& kv)

:_kv(kv)

,next(nullptr)

{}

HashNode* next;

pair _kv;

};

template

class HashBucket

{

public:

typedef HashNode Node;

void insert(const pair& kv)

{

if (n == _hash.size())

{

size_t newsize = _hash.size() == 0 ? 10 : _hash.size() * 2;

vector newnode(newsize, nullptr);

for (auto cur : _hash)

{

while (cur)

{

int hashi = cur->_kv.first % newsize;

Node* prev = newnode[hashi];

newnode[hashi] = cur;

cur->next = prev;

cur = cur->next;

}

}

_hash.swap(newnode);

}

int hashi = kv.first % _hash.size();

Node* cur = new Node(kv);

Node* _next = _hash[hashi];

_hash[hashi] = cur;

cur->next = _next;

n++;

}

bool find(const K& key)

{

if (_hash.size() == 0)

{

return false;

}

int hashi = key % _hash.size();

Node* cur = _hash[hashi];

while (cur)

{

if (cur->_kv.first = key)

{

return true;

}

cur = cur->next;

}

return false;

}

Node* erase(const K& key)

{

int hashi = key % _hash.size();

Node* prev = nullptr;

Node* cur = _hash[hashi];

while (cur)

{

if (cur->_kv.first = key)

{

if (prev == nullptr)

{

_hash[hashi] = cur->next;

}

else

{

prev->next = cur->next;

}

delete cur;

break;

}

prev = cur;

cur = cur->next;

}

return nullptr;

}

private:

size_t n = 0;

vector _hash;

};

//這里插入選擇了頭插

6. unordered_map , unordered_set 底層實現(xiàn)

代碼

“test.h” :

#pragma once

template

struct Compare

{

size_t operator()(const K& key)

{

return key;

}

};

template<>

struct Compare

{

size_t operator()(const string& k)

{

size_t x = 0;

for (auto i : k)

{

x += i;

x *= 31;

}

return x;

}

};

namespace unordered

{

template

struct HashNode

{

HashNode(const T& data)

:_data(data)

, next(nullptr)

{}

HashNode* next;

T _data;

};

template

class HashBucket;

template

struct HashIterator

{

typedef typename HashIterator Self;

typedef HashNode Node;

HashIterator(Node* hash,const HashBucket* x)

:_node(hash)

,p(x)

{}

Self& operator++()

{

if (_node->next)

{

_node = _node->next;

}

else

{

Key0f kf;

int hashi = compare()(kf(_node->_data)) % (p->_hash.size());

++hashi;

while (hashi < p->_hash.size())

{

if (p->_hash[hashi])

{

_node = p->_hash[hashi];

break;

}

else

{

++hashi;

}

}

if (hashi == p->_hash.size())

{

_node = nullptr;

}

}

return *this;

}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const Self& ptr)

{

return _node != ptr._node;

}

const HashBucket* p;

Node* _node;

};

template

class HashBucket

{

template

friend class HashIterator;

public:

typedef HashNode Node;

typedef typename HashBucket Self;

typedef typename HashIterator Iterator;

typedef typename HashIterator const_Iterator;

Iterator begin()

{

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

{

if (_hash[i])

{

return Iterator(_hash[i], this);

}

}

return end();

}

const_Iterator begin() const

{

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

{

if (_hash[i])

{

return const_Iterator(_hash[i], this);

}

}

return end();

}

Iterator end()

{

return Iterator(nullptr, this);

}

const_Iterator end() const

{

return const_Iterator(nullptr, this);

}

pair insert(const T& data)

{

Key0f kf;

Iterator it = find(kf(data));

if (it != Iterator(nullptr,this))

{

return make_pair(it, false);

}

if (n == _hash.size())

{

size_t newsize = _hash.size() == 0 ? 10 : _hash.size() * 2;

vector newnode(newsize, nullptr);

for (auto cur : _hash)

{

while (cur)

{

int hashi = compare()(kf(cur->_data)) % newsize;

Node* prev = newnode[hashi];

newnode[hashi] = cur;

cur->next = prev;

cur = cur->next;

}

}

_hash.swap(newnode);

}

int hashi = compare()(kf(data)) % _hash.size();

Node* cur = new Node(data);

Node* _next = _hash[hashi];

_hash[hashi] = cur;

cur->next = _next;

n++;

return make_pair(Iterator(cur,this), true);

}

Iterator find(const K& key)

{

Key0f kf;

if (_hash.size() == 0)

{

return Iterator(nullptr,this);

}

int hashi = compare()(key) % _hash.size();

Node* cur = _hash[hashi];

while (cur)

{

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

{

return Iterator(cur, this);

}

cur = cur->next;

}

return Iterator(nullptr, this);

}

T* erase(const K& key)

{

Key0f kf;

int hashi = compare()(key) % _hash.size();

Node* prev = nullptr;

Node* cur = _hash[hashi];

while (cur)

{

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

{

if (prev == nullptr)

{

_hash[hashi] = cur->next;

}

else

{

prev->next = cur->next;

}

delete cur;

break;

}

prev = cur;

cur = cur->next;

}

return nullptr;

}

private:

size_t n = 0;

vector _hash;

};

}

?

?"my_map.h" :

#pragma once

#include "test.h"

template>

class map

{

struct MapOf

{

const K& operator()(const pair& _key)

{

return _key.first;

}

};

public:

typedef typename unordered::HashBucket, MapOf, Hash>::const_Iterator Iterator;

typedef typename unordered::HashBucket, MapOf, Hash>::const_Iterator const_Iterator;

pair insert(const pair& data)

{

return pair(const_Iterator(key.insert(data).first._node,&key), key.insert(data).second);

}

Iterator find(const K& data)

{

return key.find(data);

}

pair* erase(const K& data)

{

return key.erase(data);

}

const_Iterator begin() const

{

return key.begin();

}

const_Iterator end() const

{

return key.end();

}

V& operator[](const K& k)

{

pair ret = key.insert(make_pair(k,V()));

return ret.first->second;

}

private:

unordered::HashBucket, MapOf,Hash> key;

};

?

?"my_set.h" :

#pragma once

#include "test.h"

template>

class set

{

struct SetOf

{

const K& operator()(const K& _key)

{

return _key;

}

};

public:

typedef typename unordered::HashBucket::const_Iterator Iterator;

typedef typename unordered::HashBucket::const_Iterator const_Iterator;

pair insert(const K& data)

{

return pair(const_Iterator(key.insert(data).first._node,&key), key.insert(data).second);

}

Iterator find(const K& data)

{

return key.find(data);

}

const K* erase(const K& data)

{

return key.erase(data);

}

const_Iterator begin() const

{

return key.begin();

}

const_Iterator end() const

{

return key.end();

}

private:

unordered::HashBucket key;

};

?

?

仿函數(shù)實現(xiàn)分析

”test.h“ 中：

其中：

這個完成了偏特化，將 string 可以變成 整型數(shù)，方便計算下標 hashi

細節(jié)注意

”my_map.h“ 中 ：

”my_set.h“ 中 ：

確保 map 和 set 都可以使用，

如果類型是 map ，得到的就是 pair里面的 K 類型

如果類型是 set ，得到的就是 K 類型

迭代器問題分析

由于在operator++過程中，需要訪問HashBucket的成員變量，所以需要友元

且在構(gòu)造時需要HashBucket類，則需要前置聲明

（前置聲明）

迭代器注意：

pair insert(const pair& data)

{

return pair(const_Iterator(key.insert(data).first._node,&key), key.insert(data).second);

}

// return pair(key.insert(data)) 是錯誤的

key.insert(data)是 pair 類型，普通迭代器不能轉(zhuǎn)換成 const迭代器

柚子快報激活碼778899分享：【C++】哈希

http://yzkb.51969.com/

精彩文章