C++數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)（目錄）

1 什么是HashMap？

我們這里要實(shí)現(xiàn)的HashMap接口不會(huì)超過(guò)標(biāo)準(zhǔn)庫(kù)的版本（是一個(gè)子集）。

HashMap是一種鍵值對(duì)容器（關(guān)聯(lián)容器），又叫字典。

和其他容易一樣，它可以對(duì)存儲(chǔ)的元素進(jìn)行增刪改查操作。

它之所以叫關(guān)聯(lián)容器，是因?yàn)樗拿總€(gè)元素都是一對(duì)（鍵 key 和值 value）。

比如：

HashMap h;
h[123] = string("張三");//每個(gè)元素包括一個(gè)鍵（123）和值（"張三"）

這種容器可以快速的訪(fǎng)問(wèn)容器中的任何一個(gè)元素。

2 為何可以快速訪(fǎng)問(wèn)元素？桶

它之所以能快速的做到這一點(diǎn)，是因?yàn)榭梢钥焖俚闹肋@個(gè)容器里有沒(méi)有這個(gè)元素。

而快速知道容器里有沒(méi)有這個(gè)元素的關(guān)鍵就在于拿到一個(gè)key，就知道這個(gè)元素會(huì)在哪個(gè)桶里面。

這里使用一個(gè)函數(shù)，也叫hash函數(shù)，計(jì)算key對(duì)應(yīng)的桶：

auto index = hashFunction(key);

HashMap的結(jié)構(gòu)如下圖所示：

槽桶是一個(gè)vector數(shù)組，每個(gè)數(shù)組里是一個(gè)list鏈表。

3 沖突與解決

不同的 key 如果都映射到同一個(gè)index怎么讓同一個(gè)桶存兩個(gè)value呢？

hashFun(key1) == hashFun(key2)

可以使用一個(gè)單鏈表，將相同 hash 值的 key 放到同一個(gè)桶里。

4 元素的均勻分布

怎么樣設(shè)計(jì)hashFun使得元素會(huì)均勻的落到每個(gè)鏈表里？

使得每個(gè)鏈表里都有大概n/N個(gè)元素。其中，n是元素總數(shù)，N是槽的個(gè)數(shù)。是我們需要重點(diǎn)考慮的。

為了解決這個(gè)問(wèn)題，我們要求hashFunction 對(duì)每一個(gè)key，都能均勻的分散到各個(gè)桶里，最簡(jiǎn)單有效的辦法就是將key看成（轉(zhuǎn)換成）整數(shù)，對(duì)vector 桶的數(shù)量求余數(shù)，余數(shù)作為桶的索引（本文我們就使用這種方法）。

5 再哈希 rehash

如果隨著元素?cái)?shù)量越來(lái)越多，元素都堆積在某一個(gè)或幾個(gè)鏈表里，其他鏈表都空著。這樣HashMap又退化成鏈表了：

解決了元素的均勻分布之后，我們還會(huì)遇到下一個(gè)問(wèn)題。

元素越來(lái)越多以后，桶bucket的數(shù)量應(yīng)該要增加，不然每個(gè)鏈表都很長(zhǎng)，效率還是會(huì)降低。

這時(shí)候就要再hash。

判斷什么時(shí)候應(yīng)該rehash的機(jī)制就是看裝載因子load_factor 的大小。

load_factor 來(lái)表示現(xiàn)在是不是元素?cái)?shù)量已經(jīng)很多了，如果這個(gè)值 大于0.8，就表示每個(gè)桶里堆積的元素都比較多了。就要使用更多的桶來(lái)存放元素了。

裝載因子的計(jì)算方法，有個(gè)很簡(jiǎn)單的辦法，就是讓每個(gè)vector里的鏈表盡量的短。那就是容器元素接近vector元素的數(shù)量：

load_factor = n/N

其中，n 是元素總數(shù)，N是槽的個(gè)數(shù)。

比如， n/N > 0.8 ，我們就再 hash 一次。

6 成員函數(shù)設(shè)計(jì)要點(diǎn)

我們將使用vector 和 list 來(lái)實(shí)現(xiàn)這個(gè)容器，讓大家感受一下用輪子造輪子到底有多爽。

感受軟件復(fù)用的力量。

感受抽象的力量。

1） clear

這個(gè)函數(shù)負(fù)責(zé)清空元素，回到初始狀態(tài)，也就是對(duì)象被構(gòu)造出來(lái)的狀態(tài)。

但是，由于我們的HashMap 在初始狀態(tài)就開(kāi)辟了8個(gè)空間為未來(lái)存放元素使用，所以clear會(huì)涉及到調(diào)用reset。

而 reset需要記得初始化一切數(shù)據(jù)，包括將容量設(shè)置為8.

2） reset

reset是給默認(rèn)構(gòu)造函數(shù)調(diào)用的，其具體行為參考 clear部分的介紹。

同時(shí)，reset也會(huì)被clear調(diào)用。那直接用clear一個(gè)函數(shù)不就好了嗎?實(shí)際上是為了代碼更容易閱讀理解。

reset為了初始化， clear是用戶(hù)調(diào)用的，用戶(hù)只知道清空容器，并不關(guān)心reset。

3） copy

copy函數(shù)負(fù)責(zé)拷貝另一個(gè)對(duì)象的數(shù)據(jù)給當(dāng)前對(duì)象。

主要是拷貝構(gòu)造函數(shù)和賦值操作符會(huì)調(diào)用。

首先，需要先清空當(dāng)前對(duì)象的數(shù)據(jù)。然后再做深拷貝即可。

4） rehash 再哈希

這個(gè)函數(shù)是最復(fù)雜的，它主要分為如下幾個(gè)部分：

（1）創(chuàng)建一個(gè)新的HashMap對(duì)象

（2）新對(duì)象的桶數(shù)量要翻倍（rehash的主要作用就是橫向擴(kuò)展，讓每個(gè)list變短）

（3）把原來(lái)的元素裝到新的HashMap對(duì)象里

（4）交換新舊對(duì)象的資源實(shí)現(xiàn)接管新場(chǎng)所，釋放舊空間的目的

5） operator[]

這個(gè)函數(shù)會(huì)添加元素（如果元素不存在的話(huà)），而如果此時(shí)容器已經(jīng)比較擁擠了，就是擴(kuò)容的時(shí)機(jī)。

6） 其他函數(shù)

更多函數(shù)設(shè)計(jì)的實(shí)現(xiàn)細(xì)節(jié)思路，參考下面代碼中的注釋部分。

C++實(shí)現(xiàn)

下面我們將實(shí)現(xiàn)一個(gè) key 類(lèi)型為 int，value 類(lèi)型為 std::string 的HashMap。

HashMap.h 頭文件

#pragma once
#include<string>
#include<list>
#include<memory>
#include<vector>
#include<utility>
using namespace std;
class HashMap
{
public:
    HashMap(void);
    ~HashMap(void);
    HashMap(const HashMap& from);
    HashMap& operator=(const HashMap& from);
public:
    bool empty(void) const { return m_size == 0; }
    size_t size(void) const;
    bool contains(const int& key) const;
    std::string& operator[](const int& key);
    void erase(const int& key);
public:
    using value_type = std::pair<int, std::string>;
public:
    class iterator
    {
        friend class HashMap;
    public:
        iterator& operator++(void);//++itr
        bool operator==(const iterator& itr);
        bool operator!=(const iterator& itr);
        value_type& operator*(void);
    private:
        iterator(HashMap* hashmap, size_t bucket_index, std::list<value_type>::iterator itr);
    private:
        std::list<value_type>::iterator m_itr;
        size_t m_bucket_index;//-1 for end()
        HashMap* m_hashmap;
    };
    iterator begin(void);
    iterator end(void);
    void clear(void);
private:
    size_t hash(const int& key) const;
    void copy(const HashMap& from);
    //裝載因子
    double load_factor(void) const { return (double)m_size / m_bucket_array_length; };
    void re_hash(void);//擴(kuò)大容量
    void reset(void);
private:
    std::vector<std::list<value_type>> m_bucket_array;
    size_t m_size = 0;
    size_t m_bucket_array_length = 8;
};

實(shí)現(xiàn)特點(diǎn)：增刪改查、迭代器、再哈希、復(fù)制控制、基于std::vector、std::list (復(fù)用、模塊化)

HashMap.cpp 源文件

#include "HashMap.h"
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;

HashMap::HashMap(void)
{
    //(1) your code 直接調(diào)用reset完成默認(rèn)開(kāi)辟8個(gè)元素空間

    cout << "HashMap()" << endl;
}

HashMap::~HashMap(void)
{
    // 析構(gòu)函數(shù)什么也不用做，因?yàn)榇娣艛?shù)據(jù)的容器 vector list 會(huì)自動(dòng)釋放其擁有的元素
    cout << "~HashMap()" << endl;
}

HashMap::HashMap(const HashMap& from)
{
    //(2) your code 直接調(diào)用 copy 即可完成拷貝

    cout << "HashMap(const HashMap &)" << endl;
}

HashMap& HashMap::operator=(const HashMap& from)
{
    //(2) your code 直接調(diào)用 copy 即可完成拷貝

    cout << "HashMap::operator=(const HashMap & from)" << endl;
    return *this;
}

size_t HashMap::size(void) const
{
    return m_size;
}

bool HashMap::contains(const int& key) const
{
    //(3) your code 通過(guò)hash(key) 得到數(shù)據(jù)如果存在應(yīng)該在哪個(gè)桶里


    //(4) your code 再到桶里 list 查找有沒(méi)有這個(gè)元素 ，在鏈表中 線(xiàn)性查找





    return false;//這里需要改成真正的查找結(jié)果
}

std::string& HashMap::operator[](const int& key)
{
    //(5) your code 如果裝載因子 大于了 0.8 就 re_hash 擴(kuò)大容量



    //通過(guò)hash(key) 得到數(shù)據(jù)如果存在應(yīng)該在哪個(gè)桶里
    auto index = hash(key);
    assert(m_bucket_array.size() > index);
    auto& bucket = m_bucket_array[index];
    //再到桶里 list 查找有沒(méi)有這個(gè)元素 ，在鏈表中 線(xiàn)性查找。返回 list<T>::iterator
    auto itr = std::find_if(bucket.begin(), bucket.end(), [key](const value_type& value) {
        return value.first == key;
        });

    if (itr == bucket.end())
    {
        //(6) your code. key not exist, insert empty std::string as default value

        //(7) your code. increase the size of current hash map.

        //(8) your code. return element

        static string s_bad;//請(qǐng)刪除
        return s_bad;//請(qǐng)重寫(xiě)
    }
    else
    {
        //(9) your code. return element

        static string s_bad;//請(qǐng)刪除
        return s_bad;//請(qǐng)重寫(xiě)
    }
}

void HashMap::erase(const int& key)
{
    auto index = hash(key);
    auto& bucket = m_bucket_array[index];

    auto itr = std::find_if(bucket.begin(), bucket.end(), [key](const value_type& value) {
        return value.first == key;
        });

    if (itr == bucket.end())
    {
        throw std::runtime_error("erasing not exist key!");
    }
    else
    {
        --m_size;
        bucket.erase(itr);
    }
}

HashMap::iterator HashMap::begin(void)
{
    for (size_t i = 0; i < m_bucket_array_length; i++)
    {
        if (!m_bucket_array[i].empty())
        {
            return HashMap::iterator(this, i, m_bucket_array[i].begin());
        }
    }
    return end();
}

HashMap::iterator HashMap::end(void)
{
    return HashMap::iterator(this, -1, std::list<value_type>::iterator());
}

size_t HashMap::hash(const int& key) const
{
    // 使用key 得到元素在哪個(gè)桶里。使用求余數(shù)來(lái)得到。
    // 這種算法可以認(rèn)為是足夠簡(jiǎn)單而且元素會(huì)均勻分布在各個(gè)桶里的
    int index = key % m_bucket_array_length;
    return index;
}

void HashMap::clear(void)
{
    reset();
}

void HashMap::copy(const HashMap& from)
{
    clear();
    m_bucket_array.resize(from.m_bucket_array_length);
    for (size_t i = 0; i < m_bucket_array_length; i++)
    {
        //10 your code. 使用鏈表的賦值操作符直接拷貝鏈表

    }
    m_size = from.m_size;
}

void HashMap::re_hash(void)
{
    //另起爐灶，新創(chuàng)建一個(gè)HashMap
    HashMap re_hashmap;
    //將新的爐灶擴(kuò)大容量
    re_hashmap.m_bucket_array_length = this->m_bucket_array_length * 2 + 1;
    //11 your code. 將新的爐灶實(shí)際的桶開(kāi)辟出來(lái)

    //使用迭代器，遍歷原來(lái)的（this）所有元素，將所有元素拷貝到新的爐灶里
    for (auto itr = begin(); itr != end(); ++itr)
    {
        //12 your code. 先根據(jù)key獲得桶，再把value追加到桶里list的末尾

    }
    //交換新舊兩個(gè)容器的內(nèi)容，接管新?tīng)t灶
    std::swap(re_hashmap.m_bucket_array, m_bucket_array);
    //其他成員變量更新
    this->m_bucket_array_length = re_hashmap.m_bucket_array_length;
    re_hashmap.m_size = this->m_size;
}

void HashMap::reset(void)
{
    m_size = 0;
    m_bucket_array.clear();
    m_bucket_array_length = 8;
    m_bucket_array.resize(m_bucket_array_length);
}

HashMap::iterator& HashMap::iterator::operator++(void)
{
    //valid itr can always do ++itr
    auto index = m_hashmap->hash(m_itr->first);
    auto& bucket = m_hashmap->m_bucket_array[index];

    ++m_itr;

    //find next list or the end() occor
    if (m_itr == bucket.end())
    {
        for (size_t i = m_bucket_index + 1; i < m_hashmap->m_bucket_array_length; i++)
        {
            if (!m_hashmap->m_bucket_array[i].empty())
            {
                m_bucket_index = i;
                m_itr = m_hashmap->m_bucket_array[i].begin();
                return *this;
            }
        }
        m_bucket_index = -1;//end()
    }

    return *this;
}

bool HashMap::iterator::operator==(const iterator& itr)
{
    if (itr.m_bucket_index != this->m_bucket_index)
    {
        return false;
    }
    if (itr.m_bucket_index == -1 && this->m_bucket_index == -1)
    {
        return true;//both end()
    }
    else
    {
        bool equal = &*(m_itr) == &*(itr.m_itr);
        return equal;//pointed to the same value address
    }
}

bool HashMap::iterator::operator!=(const iterator& itr)
{
    bool equal = (*this == itr);
    return  !equal;
}

HashMap::value_type& HashMap::iterator::operator*(void)
{
    return *m_itr;
}

HashMap::iterator::iterator(HashMap* hashmap, size_t bucket_index, std::list<value_type>::iterator itr)
{
    m_hashmap = hashmap;
    m_itr = itr;
    m_bucket_index = bucket_index;
}

main.cpp

#include <iostream>
#include "HashMap.h"
#include <cassert>
#include <unordered_map>
#include <set>
using namespace std;

//------下面的代碼是用來(lái)測(cè)試你的代碼有沒(méi)有問(wèn)題的輔助代碼，你無(wú)需關(guān)注------
#include <algorithm>
#include <cstdlib>
#include <iostream> 
#include <vector>
#include <utility>
using namespace std;
struct Record { Record(void* ptr1, size_t count1, const char* location1, int line1, bool is) :ptr(ptr1), count(count1), line(line1), is_array(is) { int i = 0; while ((location[i] = location1[i]) && i < 100) { ++i; } }void* ptr; size_t count; char location[100] = { 0 }; int line; bool is_array = false; bool not_use_right_delete = false; }; bool operator==(const Record& lhs, const Record& rhs) { return lhs.ptr == rhs.ptr; }std::vector<Record> myAllocStatistic; void* newFunctionImpl(std::size_t sz, char const* file, int line, bool is) { void* ptr = std::malloc(sz); myAllocStatistic.push_back({ ptr,sz, file, line , is }); return ptr; }void* operator new(std::size_t sz, char const* file, int line) { return newFunctionImpl(sz, file, line, false); }void* operator new [](std::size_t sz, char const* file, int line)
{
    return newFunctionImpl(sz, file, line, true);
}void operator delete(void* ptr) noexcept { Record item{ ptr, 0, "", 0, false }; auto itr = std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr != myAllocStatistic.end()) { auto ind = std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr = nullptr; if (itr->is_array) { myAllocStatistic[ind].not_use_right_delete = true; } else { myAllocStatistic[ind].count = 0; }std::free(ptr); } }void operator delete[](void* ptr) noexcept { Record item{ ptr, 0, "", 0, true }; auto itr = std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr != myAllocStatistic.end()) { auto ind = std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr = nullptr; if (!itr->is_array) { myAllocStatistic[ind].not_use_right_delete = true; } else { myAllocStatistic[ind].count = 0; }std::free(ptr); } }
#define new new(__FILE__, __LINE__)
struct MyStruct { void ReportMemoryLeak() { std::cout << "Memory leak report: " << std::endl; bool leak = false; for (auto& i : myAllocStatistic) { if (i.count != 0) { leak = true; std::cout << "leak count " << i.count << " Byte" << ", file " << i.location << ", line " << i.line; if (i.not_use_right_delete) { cout << ", not use right delete. "; }	cout << std::endl; } }if (!leak) { cout << "No memory leak." << endl; } }~MyStruct() { ReportMemoryLeak(); } }; static MyStruct my; void check_do(bool b, int line = __LINE__) { if (b) { cout << "line:" << line << " Pass" << endl; } else { cout << "line:" << line << " Ohh! not passed!!!!!!!!!!!!!!!!!!!!!!!!!!!" << " " << endl; exit(0); } }
#define check(msg)  check_do(msg, __LINE__);
//------上面的代碼是用來(lái)測(cè)試你的代碼有沒(méi)有問(wèn)題的輔助代碼，你無(wú)需關(guān)注------


int main()
{
    //create insert find
    {
        HashMap students;
        check(students.empty());
        check(students.size() == 0);
        int id = 123;
        check(students.contains(id) == false);
        std::string name("zhangsan");
        students[id] = name;
        check(!students.empty());
        check(students.size() == 1);
        check(students.contains(id));
        check(students[id] == name);
    }
    //modify value
    {
        HashMap students;
        int id = 123;
        std::string name("zhangsan");
        students[id] = name;
        std::string name2("lisi");
        students[id] = name2;
        check(students[id] == name2);
        check(students.size() == 1);
    }
    //erase
    {
        HashMap students;
        int id = 123;
        std::string name("zhangsan");
        students[id] = name;
        students.erase(id);
        check(!students.contains(id));
        check(students.size() == 0);
    }
    //clear value
    {
        HashMap students;
        int id = 123;
        std::string name("zhangsan");
        students[id] = name;
        std::string name2("lisi");
        students[id] = name2;
        check(students[id] == name2);
        check(students.size() == 1);
        students.clear();
        check(students.size() == 0);
        students.clear();
    }
    //copy
    {
        HashMap students;
        int id = 123;
        std::string name("zhangsan");
        students[id] = name;
        HashMap students2(students);//copy constructor
        check(students.contains(id));
        check(students.size() == 1);
        students[456] = "lisi";
        check(students.contains(456));
        check(!students2.contains(456));
        students2[789] = "wanger";
        check(!students.contains(789));
        check(students2.contains(789));
        check(students.size() == 2);
        check(students2.size() == 2);
    }
    //assignment
    {
        HashMap students;
        int id = 123;
        std::string name("zhangsan");
        students[id] = name;
        students[456] = "lisi";
        HashMap students2;
        students2 = students;
        check(students2.contains(id));
        check(students2.contains(456));
        check(students.size() == 2);
    }
    //iterator
    const int total = 50;
    {
        int id_creator = 1;
        HashMap students;
        std::string name("zhangsan");
        for (int i = 1; i <= total; ++i)
        {
            students[id_creator++] = name + std::to_string(i);
        }
        check(students.size() == total);
        std::multiset<int> all_keys;
        for (auto& item : students)
        {
            all_keys.insert(item.first);
            cout << item.first << " " << item.second << endl;
        }
        int i = 1;
        for (auto item : all_keys)
        {
            assert(item == i++);
        }
        check(i == total + 1);
        students.clear();
        for (int i = 1; i <= total; ++i)
        {
            students[i] = std::to_string(i);
        }
        check(students.contains(1));
        check(students.contains(total));
        check(students[1] == "1");
        check(students[total] == to_string(total));
        check(students.size() == total);
    }
}

輸出如下：

HashMap()
line:30 Pass
line:31 Pass
line:33 Pass
line:36 Pass
line:37 Pass
line:38 Pass
line:39 Pass
~HashMap()
HashMap()
line:49 Pass
line:50 Pass
~HashMap()
HashMap()
line:59 Pass
line:60 Pass
~HashMap()
HashMap()
line:70 Pass
line:71 Pass
line:73 Pass
~HashMap()
HashMap()
HashMap(const HashMap &)
line:83 Pass
line:84 Pass
line:86 Pass
line:87 Pass
line:89 Pass
line:90 Pass
line:91 Pass
line:92 Pass
~HashMap()
~HashMap()
HashMap()
HashMap()
HashMap::operator=(const HashMap & from)
line:103 Pass
line:104 Pass
line:105 Pass
~HashMap()
~HashMap()
HashMap()
HashMap()
~HashMap()
HashMap()
~HashMap()
HashMap()
~HashMap()
line:117 Pass
1 zhangsan1
2 zhangsan2
3 zhangsan3
4 zhangsan4
5 zhangsan5
6 zhangsan6
7 zhangsan7
8 zhangsan8
9 zhangsan9
10 zhangsan10
11 zhangsan11
12 zhangsan12
13 zhangsan13
14 zhangsan14
15 zhangsan15
16 zhangsan16
17 zhangsan17
18 zhangsan18
19 zhangsan19
20 zhangsan20
21 zhangsan21
22 zhangsan22
23 zhangsan23
24 zhangsan24
25 zhangsan25
26 zhangsan26
27 zhangsan27
28 zhangsan28
29 zhangsan29
30 zhangsan30
31 zhangsan31
32 zhangsan32
33 zhangsan33
34 zhangsan34
35 zhangsan35
36 zhangsan36
37 zhangsan37
38 zhangsan38
39 zhangsan39
40 zhangsan40
41 zhangsan41
42 zhangsan42
43 zhangsan43
44 zhangsan44
45 zhangsan45
46 zhangsan46
47 zhangsan47
48 zhangsan48
49 zhangsan49
50 zhangsan50
line:129 Pass
HashMap()
~HashMap()
HashMap()
~HashMap()
HashMap()
~HashMap()
line:135 Pass
line:136 Pass
line:137 Pass
line:138 Pass
line:139 Pass
~HashMap()
Memory leak report:
No memory leak.

項(xiàng)目下載：start file

鏈接：百度網(wǎng)盤(pán) 請(qǐng)輸入提取碼

提取碼：1234

加油吧！

期待你的pass

答案在此

哈希表HashMap（基于vector和list）（答案）_C++開(kāi)發(fā)者的博客-CSDN博客文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-687119.html

到了這里，關(guān)于哈希表HashMap（基于vector和list）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！