哈希表 | 悬笔一绝 那岸边浪千叠
Cobb 596 1

线性探测法


#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <list>
#include <string>
using namespace std;

enum State
{
    STATE_IDLE,   // 空闲的
    STATE_NORMAL, // 正常有数据
    STATE_DEL     // 元素被删掉了
};

const int PRIME_SIZE = 6;
int Primes[PRIME_SIZE] = { 7, 23, 59, 127, 337, 871 };

// 线性探测哈希表
class HashTable
{
public:
    HashTable(double loadFactor = 0.75)
        : loadFactor_(loadFactor)
        , useBuckets_(0)
        , primeIdx(0)
    {
        buckets_.resize(Primes[primeIdx]);
    }
public:
    void emplace(int key)
    {
        // 先判断加载因子
        double load = useBuckets_*1.0 / buckets_.size();
        if (load >= loadFactor_)
        {
            expand();
        }

        // 先计算元素放置的桶
        int idx = key % buckets_.size();

        // 找合适的位置 O(n)
        while (buckets_[idx].state_ == STATE_NORMAL)
        {
            int next = (idx + 1) % buckets_.size();
            if (next == idx)
                return;
            idx = next;
        }

        // 存储元素 O(1)
        buckets_[idx].val_ = key;
        buckets_[idx].state_ = STATE_NORMAL;
        this->useBuckets_++;
    }
    void erase(int key)
    {
        // 先计算元素放置的桶
        int idx = key % buckets_.size();

        // 找合适的位置 O(n)
        while ((buckets_[idx].state_ == STATE_NORMAL
                && buckets_[idx].val_ != key)
                || buckets_[idx].state_ == STATE_DEL)
        {
            int next = (idx + 1) % buckets_.size();
            if (next == idx || buckets_[next].state_ == STATE_IDLE)
                return;
            idx = next;
        }

        // 元素找到了
        buckets_[idx].val_ = -1;
        buckets_[idx].state_ = STATE_DEL;
        this->useBuckets_--;
    }
    bool find(int key)
    {
        // 先计算元素放置的桶
        int idx = key % buckets_.size();

        // 找合适的位置 O(n)
        while ((buckets_[idx].state_ == STATE_NORMAL
            && buckets_[idx].val_ != key)
            || buckets_[idx].state_ == STATE_DEL)
        {
            int next = (idx + 1) % buckets_.size();
            if (next == idx || buckets_[next].state_ == STATE_IDLE)
                return false;
            idx = next;
        }

        return true;
    }

private:
    void expand() // 哈希表扩容函数
    {
        vector<Node> tmpv; // DEL
        tmpv.swap(buckets_);

        ++primeIdx;
        buckets_.resize(Primes[primeIdx]);  // IDEL

        for (int i = 0; i < tmpv.size(); i++)
        {
            if (tmpv[i].state_ == STATE_NORMAL)
            {
                // 先计算元素放置的桶
                int idx = tmpv[i].val_ % buckets_.size();

                // 找合适的位置 O(n)
                while (buckets_[idx].state_ == STATE_NORMAL)
                {
                    int next = (idx + 1) % buckets_.size();
                    if (next == idx)
                        return;
                    idx = next;
                }

                // 存储元素 O(1)
                buckets_[idx].val_ = tmpv[i].val_;
                buckets_[idx].state_ = STATE_NORMAL;
            }
        }
    }

private:
    struct Node
    {
        int val_{ -1 };
        State state_{ STATE_IDLE }; // 枚举状态
    };

    vector<Node> buckets_; // 哈希桶
    const double loadFactor_; // 加载因子
    int useBuckets_; // 已经使用的桶的个数
    int primeIdx;  // 当前素数的位置
};


int main()
{
    HashTable ht;
    ht.emplace(97);
    ht.emplace(8);
    ht.emplace(87);
    ht.emplace(33);
    ht.emplace(61);
    ht.emplace(57);

    ht.emplace(7);

    //ht.erase(87);
    //ht.erase(61);

    cout << endl;
}

链地址法(无序关联容器)


#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <list>
#include <string>
using namespace std;

enum State
{
    STATE_IDLE,   // 空闲的
    STATE_NORMAL, // 正常有数据
    STATE_DEL     // 元素被删掉了
};

const int PRIME_SIZE = 6;
int Primes[PRIME_SIZE] = { 7, 23, 59, 127, 337, 871 };

// 链地址法哈希表
class HashMap
{
public:
    HashMap(double loadFactor = 0.75)
        : loadFactor_(loadFactor)
        , useBuckets_(0)
        , primeIdx(0)
    {
        buckets_.resize(Primes[primeIdx]);
    }
public:
    void emplace(int key)
    {
        // 先判断加载因子
        double load = useBuckets_ * 1.0 / buckets_.size();
        if (load >= loadFactor_)
        {
            expand();
        }

        int idx = key % buckets_.size();
        if (buckets_[idx].empty())
        {
            this->useBuckets_++;
        }

        buckets_[idx].push_front(key);
    }
    void erase(int key)
    {
        int idx = key % buckets_.size();
        for (auto it = buckets_[idx].begin();
            it != buckets_[idx].end();
            ++it)
        {
            if (*it == key)
            {
                buckets_[idx].erase(it);
                if (buckets_[idx].empty())
                {
                    this->useBuckets_--;
                }
                return;
            }
        }
    }
    bool find(int key)
    {
        int idx = key % buckets_.size();
        auto it = find(buckets_[idx].begin(), buckets_[idx].end(), key);
        return it != buckets_[idx].end();
        /*for (auto it = buckets_[idx].begin();
            it != buckets_[idx].end();
            ++it)
        {
            if (*it == key)
            {
                return true;
            }
        }
        return false;*/
    }

private:
    void expand() // 哈希表扩容函数
    {
        vector<list<int>> tmp;
        tmp.swap(buckets_);

        useBuckets_ = 0;
        primeIdx++;
        buckets_.resize(Primes[primeIdx]);

        // 取出来 key 值, 重新放到数组种
        for (auto& lis : tmp)
        {
            for (auto key : lis)
            {
                int idx = key % buckets_.size();
                if (buckets_[idx].empty())
                {
                    this->useBuckets_++;
                }
                buckets_[idx].push_front(key);
            }
        }
    }

private:
    vector<list<int>> buckets_; // 哈希桶
    const double loadFactor_; // 加载因子
    int useBuckets_; // 已经使用的桶的个数
    int primeIdx;  // 当前素数的位置
};

/*
哈希表
*/
#if 0
int main()
{
    vector<int> v;
    srand(time(0));
    for (int i = 0; i < 10; i++)
    {
        v.push_back(rand() % 100);
    }

    // operator[]   iterator   iterator foreach版
    for (auto val : v)
    {
        cout << val << " ";
    }
    cout << endl;
}
#endif

评论区

索引目录