哈希 4个月前

编程语言
199
哈希

一、哈希的基本介绍

性能上

查找数据，哈希时间复杂度为O(1) 大量随机数据插入，map和set性能快 大量随机数据删除，map和set性能快

哈希映射方法

1.直接定址法:每个值都有自己唯一的位置 优点:无哈希冲突,简单且均匀 缺点:如果空间分散会有很大的空间浪费 适应于范围小且连续的情况

2,除留余数法 优点:空间合适且不浪费过多的空间 缺点:可能存在有相同的映射地址(哈希冲突)

哈希大部分都围绕着解决哈希冲突

1.闭散列:冲突后占用下一个空位置 缺点：查找效率变低，互相冲突导致插入逻辑复杂 线性探测:线性找下一个空位置,++ 二次探测:平方步调找下一个位置,^2

2.开散列(哈希桶)(拉链法):冲突的位置下加上链表(哈希桶),由此STL中并没有双向迭代器 缺点:链表太长有效率问题 优点:冲突不会相互影响

二、闭散列的哈希表实现

实际中开散列应用情况优于闭散列,点一下



#include<iostream>
#include<vector>
using namespace std;

template<class K>
struct KeyToCmp //得到可以进行比较的数据
{
    size_t operator()(const K& k)
    {
        return (size_t)k;
    }
};

template<>
struct KeyToCmp<string> //特化一个string的仿函数,使得字符也能有其映射的地址
{
    size_t operator()(const string& k)
    {
        size_t hash = 0;
        for (auto& e : k)
        {
            hash += e;
        }
        return hash;
    }
};


enum State
{
    EMPTY,
    EXIST,
    DELETE
};
    
template<class K,class V>
struct HashData
{
    pair<K,V> _kv;
    State _state = EMPTY; //通过加入状态成员来方便进行增删查改
};
    
template<class K,class V,class Hash = KeyToCmp<int>>
class HashTable
{
public:
    typedef HashData<K,V> Data;

    HashTable() //构造
    {
        _tables.resize(10);
    }


    //负载因子 = 表中数据/表的大小  衡量哈希表满的程度
    //负载因子越大,插入数据越容易发生哈希冲突,冲突越多,效率越低
    //所以哈希表并不是满了才增容,一般负载因子在0.7左右就开始增容
    //控制的太小,会使得空间浪费
    bool Insert(const pair<K,V>& kv)
    {
        if (Find(kv.first) != nullptr) //已经有了
            return false;
        
        if (_num * 10 / _tables.size() >= 7) //负载因子大了,开始增容
        {
            HashTable<K, V, Hash> tmp;
            tmp._tables.resize(2 * _tables.size()); //新创建一个哈希表,将其数组空间扩大至旧哈希表的两倍
            
            for (auto& e : _tables)
            {
                if (e._state == EXIST) //如果有数据
                    tmp.Insert(e._kv); //插入,扩容已经在上面完成了,递归时判断增容条件进不去,不会造成死循环
            }
            _tables.swap(tmp._tables);
        }

        Hash get;
        size_t index = get(kv.first) % _tables.size();

        while (_tables[index]._state == EXIST)
        {
            index++;
            index %= _tables.size();
        }

        _tables[index]._kv = kv;
        _tables[index]._state = EXIST;
        _num++;
        
        return true;
    }


    Data* Find(const K& k)
    {
        
        Hash get;
        size_t index = get(k) % _tables.size();

        while (_tables[index]._state != EMPTY)
        {
            if (_tables[index]._state == EXIST && _tables[index]._kv.first == k)
                return &_tables[index];
            index++;
            index %= _tables.size();
        }
        return nullptr; //哈希冲突是连续的,如果第一个后面为空,说明后面也没有冲突的情况,直接返回
    }


    bool Erase(const pair<K, V>& kv)
    {
        Data* ret = Find(kv.first);
        if (ret)
        {
            ret->_state = DELETE;
            --_num;
            return true;
        }
        else
        {
            return false;
        }
    }
    
private:
    vector<Data> _tables;
    size_t _num = 0; //存储当前存储有效数据的个数
};

三、开散列模拟实现unordered_xxx

unordered_xxx底层都是由开散列实现的



#pragma once
#include<iostream>
#include<vector>
using namespace std;

namespace BsyOpen
{
    template<class K>
    struct GetWay
    {
        const K& operator()(const K& k)
        {
            return k;
        }
    };

    template<> //特化处理字符串,使得其返回值能够被模
    struct GetWay<string>
    {
        size_t operator()(const string& k)
        {
            size_t way = 0;
            for (size_t i = 0; i < k.size(); ++i)
            {
                way *= 131; //BKDR Hash,使得哈希冲突降低
                way += k[i];
            }
            return way;
        }
    };


    template<class T> //一个哈希表节点
    struct HashNode 
    {
        T _data;
        HashNode<T>* _next;
        //我们自己实现的哈希输出,并非输入的顺序,如果要实现按输入顺序输出就要多指针
        //HashNode<T>* _linknext; //以按顺序输出
        //HashNode<T>* _linkprev; //以删除

        HashNode(const T& data)
            :_data(data)
            ,_next(nullptr)
        {}
    };


    // 前置声明一下, 否则在迭代器类中, 无法识别出HashTable是什么
    template<class K, class T, class TheKey, class GetWayy> //哈希表
    class HashTable; 

    template<class K,class T,class TheKey,class GetWayy> //哈希表迭代器
    struct __HashIterator
    {
        typedef __HashIterator< K, T, TheKey, GetWayy> Self;
        typedef HashTable<K, T, TheKey, GetWayy> HT;
        typedef HashNode<T> Node;
        Node* _node;
        HT* _pht; //以便在后续operator++中起到作用

        __HashIterator(Node* node,HT* pht)
            :_node(node)
            ,_pht(pht)
        {}

        T& operator*()
        {
            return _node->_data;
        }

        T* operator->()
        {
            return &_node->_data;
        }

        Self operator++()
        {
            if (_node->_next)
            {
                _node = _node->_next; //如果桶没走完接着往下走
            }
            else
            {
                TheKey thekey;
                GetWayy getway;
                //计算数值应该位于哪个头节点
                size_t i = getway(thekey(_node->_data)) % _pht->_tables.size();
              //size_t i = GetWayy()(TheKey()(_node->_data)) % _pht->_tables.size();
                i++; //现在i就是下一个需要验证是否为空的数组下标
                for (; i < _pht->_tables.size(); ++i)
                {
                    Node* cur = _pht->_tables[i];
                    if (cur)
                    {
                        _node = cur;
                        return *this;
                    }
                }
                //此时说明没有下一个节点了
                _node = nullptr;
            }
            return *this;
        }

        bool operator!=(const Self& s)
        {
            return _node != s._node;
        }
    };


    template<class K,class T,class TheKey,class GetWayy> //哈希表
    class HashTable
    {
    public:
        friend struct __HashIterator< K, T, TheKey, GetWayy>;
        typedef HashNode<T> Node;
        typedef __HashIterator< K, T, TheKey,GetWayy> iterator;

        iterator begin()
        {
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                if (_tables[i])
                {
                    return iterator(_tables[i],this);
                }
            }
            return end();
        }

        iterator end()
        {
            return iterator(nullptr,this);
        }

        ~HashTable() //销毁完桶之后,,析构自动销毁this,即vector会随着析构函数销毁
        {
            Clear();
        }

        void Clear()
        {
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                Node* cur = _tables[i];
                while (cur)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr; //使得无法访问每个头节点
            }
        }

        size_t GetNextPrime(size_t num) //这是一种算法,使得可以减小哈希冲突
        {
            const int primecount = 28;
            const size_t primelist[primecount] = //二倍关系质数表
            {
                53,97,193,389,769,
                1543,3079,6151,12289,24593,
                49157,98317,1996613,393241,786433,
                1572869,3145739,6291469,12582917,25165843,
                50331653,100663319,201326611,402653189,805306457,
                1610612741,3221225473,4294967291
            };

            for (size_t i = 0; i < primecount; ++i)
            {
                if (primelist[i] > num)
                {
                    return primelist[i];
                }
            }
            return primelist[primecount - 1]; //如果还大,就一直返回最后一个
        }

        pair<iterator,bool> Insert(const T& data)
        {
            TheKey thekey;
            GetWayy getway;

            if (_num == _tables.size()) //此时负载因子为1,避免以后造成大量冲突,增容
            {
                vector<Node*> newtable;
                size_t newsize = GetNextPrime(_num);
                newtable.resize(newsize);
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    Node* cur = _tables[i]; //取每个头
                    while (cur)
                    {
                        //旧表取下重新计算新表中的位置
                        Node* next = cur->_next;
                        size_t index = getway(thekey(cur->_data)) % newtable.size(); //新表中的位置
                        cur->_next = newtable[index]; //头插进去
                        newtable[index] = cur;
                        cur = next;
                    }
                    _tables[i] = nullptr; 
                }
                _tables.swap(newtable);
            }


            size_t index = getway(thekey(data)) % _tables.size();

            Node* cur = _tables[index];
            while (cur)
            {
                if (thekey(cur->_data) == thekey(data)) //重复了,不插入,结束
                    return make_pair(iterator(cur,this),false);
                else
                    cur = cur->_next;
            }

            //检验完后走到这里说明可以插入了
            //选择头插,因为有头节点的位置,不用找尾
            Node* newnode = new Node(data);
            newnode->_next = _tables[index];
            _tables[index] = newnode;

            ++_num;
            return make_pair(iterator(newnode, this), true);
        }

        Node* Find(const K& k)
        {
            TheKey thekey;
            GetWayy getway;
            size_t index = getway(k) % _tables.size();
            Node* cur = _tables[index];
            while (cur)
            {
                if (thekey(cur->_data) == k)
                    return cur;
                else
                    cur = cur->_next;
            }
            return nullptr;
        }


        bool Erase(const K& k)
        {
            TheKey thekey;
            GetWayy getway;
            size_t index = getway(k) % _tables.size();
            Node* prev = nullptr;
            Node* cur = _tables[index]; //找到需要找到数据的头
            while (cur)
            {
                if (thekey(cur->_data) == k)//找到了
                {

                    if (prev == nullptr) //说明要删除的对象就是第一个节点
                        _tables[index] = cur->_next;
                    else
                        prev->_next = cur->_next;
                    
                    delete cur;
                    return true;
                }
                else
                {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }

    private:
        vector<Node*> _tables;
        size_t _num = 0;
    };
}

1.unordered_set



#pragma once
#include"Open_Hash.hpp"

namespace Bsy
{
    template<class K, class GetWayy = BsyOpen::GetWay<K>>
    class unordered_set
    {
        struct TheKeyOfSet
        {
            const K& operator()(const K& k)
            {
                return k;
            }
        };


    public:
        typedef typename BsyOpen::HashTable<K, K, TheKeyOfSet, GetWayy>::iterator iterator;

        iterator begin()
        {
            return _ht.begin();
        }

        iterator end()
        {
            return _ht.end();
        }

        pair<iterator,bool> insert(const K& k)
        {
            return _ht.Insert(k);
        }

    private:
        BsyOpen::HashTable<K, K, TheKeyOfSet,GetWayy> _ht;
    };

    void test_unordered_set1()
    {
        unordered_set<int> s;
        s.insert(1);
        s.insert(5);
        s.insert(6);
        s.insert(2);

        unordered_set<int>::iterator it = s.begin();
        while (it != s.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }

}

2.unordered_map



#pragma once
#include"Open_Hash.hpp"

namespace Bsy
{
    template<class K,class V, class GetWayy = BsyOpen::GetWay<K>>
    class unordered_map
    {
        struct TheKeyOfMap
        {
            const K& operator()(const pair<K, V>& kv)
            {
                return kv.first;
            }
        };

    public:
        typedef typename BsyOpen::HashTable<K, pair<K,V>, TheKeyOfMap, GetWayy>::iterator iterator;

        iterator begin()
        {
            return _ht.begin();
        }

        iterator end()
        {
            return _ht.end();
        }

        pair<iterator,bool> insert(const pair<K, V>& kv)
        {
            return _ht.Insert(kv);
        }

        V& operator[](const K& k)
        {
            //pair<iterator, bool> ret = _ht.Insert(make_pair(k, V()));
            //return ret.first->second;
            return _ht.Insert(make_pair(k, V())).first->second;
        }

    private:
        BsyOpen::HashTable<K, pair<K, V>, TheKeyOfMap,GetWayy> _ht;
    };


    void test_unordered_map1()
    {
        unordered_map<string, string> dict;
        dict.insert(make_pair("sort", "paixu"));
        dict.insert(make_pair("left", "zuo"));
        dict.insert(make_pair("long", "chang"));
        dict["left"] = "you";
        dict["hash"] = "haxi";

        unordered_map<string, string>::iterator it = dict.begin();
        while (it != dict.end())
        {
            cout << it->first <<":"<<it->second<< endl;
            ++it;
        }
        cout << endl;
    }
}
image
EchoEcho官方
无论前方如何，请不要后悔与我相遇。
1377
发布数
439
关注者
2222669
累计阅读

热门教程文档

C++
73小节
MySQL
34小节
C#
57小节
HTML
32小节
Next
43小节
0 0