云端浮梦

large picture of the cover

Hash（C++）

Hash

哈希方法： 通过哈希函数

  • 直接定制法：映射只跟关键字直接或者间接相关（数据分布均匀）

  • 除留余数法 ：在限定的大小空间中将我们的值映射出去，不同的值会映射到相同的位置，会导致哈希冲突，哈希冲突整体上效率越低（数据分布不均匀）

如何解决哈希冲突？

开放寻址法：（冲突了，按规则给你找个位置）

  • 线性探测法 （one by one）

  • 二次探测 （按照i^2,跳跃往后找 知道null）

开散列表--拉链法（哈希桶）

闭散列哈希表不能满了再增大空间，如果哈希表满了的时候再插入数据冲突的概率很大，效率很低。

解决方法： 使用控制负载因子的方法（空间换时间）

负载因子 = 表中数据个数/表的大小， 一般闭散列哈希表负载因子到达0.7就可以开始增容。

一般情况下，负载因子越小，冲突越低 效率越高。

负载因子是一种用空间换时间的思路

每次增容的时候使用的时间损耗都很大，很容易出现哈希冲突，效率极低

所以闭散列开放定址法并不是一个好方法。

可以使用拉链法来更好的解决问题

线性探测 开放寻址

HashTable.h

#pragma once
#include <vector>
using namespace std;
​
namespace chen{
​
​
    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 HashTable
    {
    private:
        vector<HashData<K,V>> _tables;
        size_t _n = 0;
    public:
        HashData<K,V> * Find(const K& key)
        {
            if(_tables.size() == 0){
                return nullptr;
            }
            size_t hash = key % _tables.size();
​
            size_t i  = 1;
            size_t index = hash;
​
​
            // 线性探测 一个一个找
            while(_tables[index]._state != EMPTY){
                if(_tables[index]._state == EXIST && \
                    _tables[index]._kv.first  == key 
                ){
                    return &_tables[index];
                }
​
                index = hash + i;
                index %= _tables.size();
                ++i;
                if(index == hash) // 如果找了一圈
                {
                    break;
                }
            }
​
            return nullptr;
​
        }
​
        bool Insert(const pair<K,V> & KV){
            if(Find(KV.first)){
                return false;
            }
            if(_tables.size() == 0 || _n*10 / _tables.size() >= 7){
                // 遍历旧表 
                // 重新计算旧表在新表中的位置
                size_t newSize = _tables.size() == 0?10 : _tables.size() * 2;
                HashTable<K,V> newtable;
                newtable._tables.resize(newSize);
​
                //重新映射
                for(auto &data :_tables){
                    if(data._state == EXIST){
                        newtable.Insert(data._kv);
                    }
                }
                _tables.swap(newtable._tables);
            }
            // Insert  线性探测
            size_t hash = KV.first % _tables.size();
​
            size_t i = 1;
            size_t index = hash;
            while(_tables[index]._state == EXIST)
            {
                index = hash + i;
                index %= _tables.size();
                i ++;
            }
            _tables[index]._kv = KV;
            _tables[index]._state = EXIST;
            _n ++;        
            return true;
        }
​
        bool Erase(const K & key)
        {
            HashData<K,V> * ret = Find(key);
​
            if(ret){
                ret->_state = DELETE;
                -- _n;
                return true;
            }
            return false;
        }
    };
        void TestHashTable1()
    {
        int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
        HashTable<int, int> ht;
        for (auto e : a)
        {
            ht.Insert(make_pair(e, e));
        }
        ht.Insert(make_pair(15, 15));
        if (ht.Find(13))
        {
            cout << "13在" << endl;
        }
        else
        {
            cout << "13不在" << endl;
        }
        ht.Erase(13);
        if (ht.Find(13))
        {
            cout << "13在" << endl;
        }
        else
        {
            cout << "13不在" << endl;
        }
    }
}

完整的hashtable

#pragma once
​
​
#include <vector>
#include <iostream>
​
using namespace std;
​
namespace chen
{
​
​
    // 哈希表结构体
    template<class T>
    struct HashNode
    {
        HashNode<T>* _next;  // 指向下一个
        T _data;
        HashNode(const T& data)
            :_next(nullptr)
            ,_data(data)
        {}
    };
    template<class K,class T,class KeyOfT,class Hash>
    class HashTable;
​
​
    // hash 迭代器
    template<class K,class T , class Ref,class Ptr,class KeyOfT,class Hash>
    struct __HashIterator
    {
        typedef HashNode<T> Node;
        typedef HashTable<K,T,KeyOfT,Hash> HT;
        typedef __HashIterator<K,T,Ref,Ptr,KeyOfT,Hash> Self;
        typedef __HashIterator <K,T,T&,T*,KeyOfT,Hash>  Iterator;
​
        Node * _node;
        const HT* _ht;
​
        __HashIterator(Node * node,const HT* ht)
            :_node(node)
            ,_ht(ht)
        {}
        __HashIterator(const Iterator & it)
            :_node(it._node)
            ,_ht(it._ht)
        {}
​
        Ref operator*()
        {
            return _node->_data;
        }
​
        Ptr operator->()
        {
            return &_node->_data;
        }
        bool operator!=(const Self & s)
        {
            return _node != s._node;
        }
​
        Self& operator++()
        {
            if(_node->_next != nullptr) // 找到下一个节点
            {
                _node = _node->_next;
            }else{                     // 找到下一个桶的位置
                KeyOfT kot;
                Hash hash;
​
                // 算出当前桶的位置
                size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
                ++hashi;
                while(hashi < _ht->_tables.size())
                {
                    if(_ht->_tables[hashi]){
                        _node = _ht->_tables[hashi];
                        break;
                    }
                    else{
                        ++hashi;
                    }
                }
​
                if(hashi == _ht->_tables.size())
                {
                    _node = nullptr;
                }
            }
​
            return *this; ///  _node
        }
​
    };
    
​
​
    template<class K,class T ,class KeyOfT,class Hash>
    class HashTable
    {
​
        template<class Ki,class Ti , class Ref,class Ptr,class KeyOfTi,class Hash1>
        // template<K,T, T&,T*,KeyOfT,Hash>
        friend struct __HashIterator;
          // __HashIterator友元类
        typedef HashNode<T> Node;
    private:
        vector<Node*> _tables;
        size_t _n = 0;
    public:
​
        typedef __HashIterator<K,T,T&,T*,KeyOfT,Hash> iterator;
        typedef __HashIterator<K,T,const T&,const T*,KeyOfT,Hash> const_iterator;
        
        iterator begin()
        {
            Node * cur = nullptr;
            for(size_t i = 0;i < _tables.size();i ++)
            {
                cur = _tables[i];
                if(cur)break;
            }
​
            return iterator(cur,this);
        }
​
        iterator end()
        {
            return iterator(nullptr,this);
        }
​
        const_iterator begin() const
        {
            Node* cur  = nullptr;
            for(size_t i;i < _tables.size();i ++)
            {
                cur = _tables[i];
                if(cur)break;
            }
            return const_iterator(cur,this);
        }
​
        const_iterator end() const
        {
            return const_iterator(nullptr,this);
        }
​
        ~HashTable()
        {
            clear();
        }
​
        void clear()
        {
            for(auto & cur : _tables)
            {
                while(cur)
                {
                    Node * next = cur->_next;
                    delete cur;
                    cur = next;
                }
                cur = nullptr;
            }
        }
​
        iterator Find(const K& key)
        {
            if(_tables.size() == 0)
                return end();
            KeyOfT kot;
​
            Hash hash;
​
            size_t hashi = hash(key)% _tables.size();
            Node * cur = _tables[hashi];
​
            while(cur)
            {
                if(kot(cur->_data) == key)
                {
                    return iterator(cur,this);
                }
                cur = cur->_next;
            }
            return end();
        }
​
        bool Erase(const K& key)
        {
            Hash hash;
            KeyOfT kot;
            size_t hashi = hash(key) % _tables.size();
            Node * prev = nullptr;
            Node * cur = _tables[hashi];
            while(cur)
            {
                if(kot(cur->_data) == key)
                {
                    if(prev == nullptr)
                    {
                        _tables[hashi] = cur->_next;
                        delete cur;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                        delete cur;
                    }
                    return true;
                }else{
                    prev = cur;
                    cur = cur->_next;
                }
            }
​
​
            return false;
​
        }
​
        pair<iterator,bool> Insert(const T& data)
        {
            KeyOfT kot;
            iterator it = Find(kot(data));
            if(it != end())
            {
                return make_pair(it,false);
            }
            Hash hash;
​
            if(_n == _tables.size()) // 负载因子为1 的时候进行扩容
            {
                // 可以使用之前的方法进行扩容
                /// C++ 底层是使用一个素数表进行扩容数据
                // 因为一个数去mod一个素数来进行哈希产生的冲突是很少的
​
​
                size_t newSize = GetNextPrime(_tables.size());
                vector<Node*> newTables(newSize,nullptr);
​
                for(auto &cur : _tables)
                {
                    while(cur)
                    {
                        Node * next = cur->_next;
                        size_t hashi = hash(kot(cur->_data)) % newTables.size();
                        cur->_next = newTables[hashi];
                        newTables[hashi] = cur;
                        cur = next;
                    }
                }
                _tables.swap(newTables);
            }
​
             // 头插
             size_t hashi = hash(kot(data)) % _tables.size();
​
             Node *newNode = new Node(data);
​
             newNode->_next = _tables[hashi];
             ++_n;
             _tables[hashi] = newNode;
             return make_pair(iterator(newNode,this),false);
        }
​
        size_t GetNextPrime(size_t prime)
        {
            // SGI
            static const int __stl_num_primes = 28;
            static const unsigned long __stl_prime_list[__stl_num_primes] =
            {
                53, 97, 193, 389, 769,
                1543, 3079, 6151, 12289, 24593,
                49157, 98317, 196613, 393241, 786433,
                1572869, 3145739, 6291469, 12582917, 25165843,
                50331653, 100663319, 201326611, 402653189, 805306457,
                1610612741, 3221225473, 4294967291
            };
​
            size_t i = 0;
            for (; i < __stl_num_primes; ++i)
            {
                if (__stl_prime_list[i] > prime)
                    return __stl_prime_list[i];
            }
​
            return __stl_prime_list[i];
        }
​
    };
​
    template <class K>
    struct HashFunc
    {
        size_t operator()(const K& key)
        {
            return key;
        }
    };
​
​
    template<>
    struct HashFunc<string>
    {
        size_t operator()(const string& s)
        {
            size_t hash = 0;
            for(auto ch:s)
            {
                hash += ch;
                hash *= 31;
            }
            return hash;
        }
    };
}

unordered_map

#pragma once
#include "HashTable.h"
#include <iostream>
​
​
using namespace std;
namespace chen
{
    using namespace std;
    template<class K,class V,class Hash = HashFunc<K>>
    class unordered_map
    {
        public:
            struct MapKeyOfT
            {
                const K& operator()(const pair<K,V>& kv)
                {
                    return kv.first;
                }
            };
        public:
​
            typedef typename chen::HashTable<K,pair<const K,V>,MapKeyOfT,Hash>::iterator iterator;
            typedef typename chen::HashTable<K,pair<const K,V>,MapKeyOfT,Hash>::const_iterator const_iterator;
​
            iterator begin()
            {
                return _ht.begin();
            }
​
            iterator end()
            {
                return _ht.end();
            }
            const_iterator begin() const 
            {
                return _ht.begin();
            }
​
            const_iterator end()  const 
            {
                return _ht.end();
            }
​
            pair<iterator,bool> insert(const pair<K,V>& kv)
            {
                return _ht.Insert(kv);
            }
​
            V& operator[](const K& key)
            {
                pair<iterator,bool> ret = insert(make_pair(key,V()));
                return ret.first->second;
            }
​
            iterator find(const K& key)
            {
                return _ht.Find(key);
            }
​
            iterator erase(const K& key)
            {
                return _ht.Erase(key);
            }
​
            private:
                chen::HashTable<K,pair<const K,V>,MapKeyOfT,Hash> _ht;
​
​
    };
​
​
​
    void test_unordered_map1()
    {
        unordered_map<int, string> m;
        m.insert(make_pair(1, "11"));
        m.insert(make_pair(3, "333"));
        m.insert(make_pair(2, "222"));
​
        unordered_map<int, string>::iterator it = m.begin();
        while (it != m.end())
        {
            cout << it->first << ":" << it->second << endl;
            ++it;
        }
    }
​
}

unordered_map 和 unordered_set 大体上相同 一个是K 一个是KV 通过仿函数进行实现一个哈希表两个使用方法

哈希是映射方式

哈希表是使用哈希存储的数据库结构

位图

是哈希的一种的方式

优点 节省空间 效率高 但是是能处理整形

在stl中是<btiset>

代码实现

#pragma once
​
#include <vector>
#include <iostream>
​
using namespace  std;
namespace chen
{
​
    class bitset
    {
    private:
        vector<int> _bit;
        size_t _bitCount;
    public:
        bitset(size_t bitCount) //// (bitCount>>5) 表示bitCount右移动五位相当于/32 +1确保足够空间存储
            :_bit((bitCount>>5)+1),_bitCount(bitCount)
            {}
        void set(size_t whish)
        {
            if(whish > _bitCount)
            {
                return ;
            }
​
            size_t index = whish >> 5;
            size_t pos = whish%32;
​
            _bit[index] |= (1<<pos);
        }
        void reset(size_t whish)
        {
            if(whish > _bitCount)
            {
                return ;
            }
​
            size_t index = whish >> 5;
            size_t pos = whish%32;
​
            _bit[index] &= ~(1<<pos);
        }
​
​
        bool cleck(size_t which)
        {
            if(which > _bitCount)return  false;
            size_t index = which >> 5;
            size_t pos = which%32;
            return _bit[index] & (1<<pos);
        }
​
        size_t size() const
        {
            return _bitCount;
        }
        // 使用“位计数表“ 来 确认个数
        size_t Count()const
        {
            int bitCnttable[256] = {
                    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
                    3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
                    3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
                    4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
                    3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
                    6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
                    4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
                    6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
                    3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
                    4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
                    6, 7, 6, 7, 7, 8};
            size_t size = _bit.size();
            size_t count = 0;
            for(size_t i = 0; i < size; ++i)
            {
                int value = _bit[i];
                int j = 0;
                while(j < sizeof(_bit[0]))
                {
                    unsigned char c = value;
                    count += bitCnttable[c];
                    ++j;
                    value >>= 8;
                }
            }
            return count;
        }
    };
    void  test_Bitset()
    {
        bitset con(10);
        con.set(8);
        cout << con.cleck(8) << endl;
        con.reset(8);
        cout << con.cleck(8) << endl;
        con.set(9);
        cout << con.Count() <<" " <<con.size() << endl;
    }
}

布隆过滤器

也是一种位图，解决位图bitset只能处理整形的缺点

优点：

  • 节省空间，高效 ，可以标记类型

  • 存在误判，不支持删除

哈希相关面试题

问题：给一个超过100G大小的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址？

解决方法：分治法 + hash

  1. 切分文件： 将超过100G的文件切分成多份。例如，将文件切分为100份，每份1G。可以通过IP地址的hash值进行分类，将相同IP映射到同一个文件中。

  2. 将IP地址转换为整型： 使用字符串hash算法，将IP地址转换为整型来进行计算和处理。

  3. 统计次数： 对每个小文件中的IP地址使用hash表进行统计，每个IP的出现次数记录在hash表中。

  4. 合并统计结果： 将所有小文件中的hash表合并，追踪IP地址出现的次数，最终找出出现次数最多的IP。

与上题条件相同，如何找到Top K的IP？Linux命令如何实现？

解决方法：

与前述方案类似，在合并阶段，可以通过一个大小为K的大根堆来存储Top K的IP。每次合并过程中，维护堆的大小，保持Top K的IP在堆中。

Linux命令：

awk '{print $1}' large_log.txt | sort | uniq -c | sort -nr | head -n 10

  1. awk '{print $1}'：提取文件中的IP地址。

  2. sort：对IP地址排序。

  3. uniq -c：统计每个IP地址出现的次数。

  4. sort -nr：按次数从高到低排序。

  5. head -n 10：输出出现次数最多的前10个IP。

问题：给定100亿个整数，设计算法找到只出现一次的整数？

解决方法：位图法

  • 使用两个位图：

    1. 第一个位图bitmap_once[]记录每个整数是否出现过。

    2. 第二个位图bitmap_multiple[]记录每个整数是否出现过多次。

  • 步骤：

    1. 遍历所有整数：

      • 如果bitmap_once[x]未被设置，则设置为1。

      • 如果bitmap_once[x]已设置，则将bitmap_multiple[x]设置为1。

    2. 遍历位图，找出在bitmap_once中设置为1且bitmap_multiple中未设置为1的整数。

问题：给两个文件，分别有100亿个整数，如何在1G内存下找到交集？

精确算法：

  1. 哈希切分： 将两个文件通过hash函数切分成若干小文件。假设切分成1000份，每份大约400MB（40亿整数/1000 = 400万整数）。

  2. 求交集： 对每个小文件分别加载到内存中，使用hash表对每个文件的整数进行存储和查找，依次找出交集。

近似算法：

  1. 布隆过滤器：

    • 构建布隆过滤器，将第一个文件中的整数加入过滤器中。

    • 遍历第二个文件，检查每个整数是否在过滤器中，虽然布隆过滤器有一定的误判率，但可以较快找到交集。

问题：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数？

解决方法：位图法的变形

使用两个比特位来记录整数的状态：

  • 第一个比特记录整数是否出现过一次。

  • 第二个比特记录整数是否出现过多次。

每个整数需要两个比特位表示，总共需要大约2.5GB的位图空间（假设整数范围较大，40亿个整数需要大约2*40亿位 ≈ 10亿字节）。通过对文件的多次扫描，可以统计出出现次数不超过2次的整数。

问题：给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件的交集？

精确算法：

  1. 哈希切分： 与前述方案相同，将两个文件通过hash切分成若干份。

  2. 求交集： 通过哈希切分后，在每一对小文件中找出交集。

近似算法：

  1. 布隆过滤器： 构建布隆过滤器，将第一个文件中的query加入过滤器。然后遍历第二个文件，查找query是否存在于过滤器中，快速得到近似交集。

如何扩展BloomFilter使得它支持删除元素的操作

计数型布隆过滤器（Counting Bloom Filter, CBF）

基本原理：

在标准的布隆过滤器中，使用的是一个位数组，位只能是 0 或 1。而在计数型布隆过滤器中，位数组被替换为计数数组，即每个位置存储的不是 0 或 1，而是一个计数值。这样我们可以在插入元素时将相应位置的计数值加 1，在删除元素时将计数值减 1。

插入元素 x：通过哈希函数计算 h1(x) = 1, h2(x) = 3, h3(x) = 5，因此 C[1]++, C[3]++, C[5]++。结果数组为 [0, 1, 0, 1, 0, 1]。

插入元素 y：假设 h1(y) = 1, h2(y) = 2, h3(y) = 3，因此 C[1]++, C[2]++, C[3]++。结果数组为 [0, 2, 1, 2, 0, 1]。

删除元素 x：使用同样的哈希函数，找到 h1(x) = 1, h2(x) = 3, h3(x) = 5，然后将相应位置的计数值减 1，即 C[1]--, C[3]--, C[5]--。结果数组为 [0, 1, 1, 1, 0, 0]。

site logo

Welcome to my blog.

© 2025 云端浮梦