哈希

文章目录

• unordered_map与unordered_set
• 哈希
• • 哈希本质
  • 哈希函数
  • 哈希冲突：
• 哈希函数
• 闭散列
• 散列表（哈希桶）

unordered_map与unordered_set

功能：

功能基本一样

1. unorder_xxx遍历不按照key进行排序 ,命名体现了
2. unorder_xxx只有单向迭代器，没有提供反向迭代器
3. unorder_xxx综合效率略胜map和set

unordered对于无序的数据效率很高
set底层使用对于顺序插入的数据效率就会很高

demo.cc

void test_set()
{

//set是排序+去重
//unordered_set：只能实现去重,没有实现排序


    unordered_set<int> us;
    us.insert(1);
    us.insert(3);
    us.insert(4);
    us.insert(1);
    us.insert(7);
    us.insert(6);
    us.insert(2);
    auto it=us.begin();
    while(it!=us.end())
    {
        cout<<*it<<" ";
        it++;
    }
    cout<<endl;
    //这个就不用去重,

    unordered_multiset<int> s;
    s.insert(12);
    s.insert(12);
    s.insert(12);
    auto dt=us.begin();

     while(dt!=s.end())
    {
        cout<<*dt<<" ";
        dt++;
    }

}

哈希

哈希本质

哈希/散列
本质上就是映射，找到一个值进行映射，把数据映射到对应的地方

使用示例
计数排序：
1.统计每个数字出现次数，范围很集中，可以使用，但是对于随机的一堆整数，就按照范围来开空间，很分散，最好不要这样，

哈希函数

除留余数法
10 122 31 400
%10把对应的数放到它余数对应的位置

开10个空间，分配到不同的地方

哈希冲突：

不同的数用哈希放到了同一个地方,不能保证每个值都开辟一个空间
但是我想要映射到一个相对固定的地方去
我们最常用的方法就是将

如何解决哈希冲突

1. 闭散列

闭散列：开放定址法，当发生hash冲突的时候，如果哈希表未被装满，说明在哈希表中必然还有空的位置，那么就把key存放到下一个“空位置”中去
* 线性探测
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

* 二次探测
>我们下一次探测到其平方的位置上，这样就不会让数据太集中

2. 开散列/哈希桶/拉链法
   6 26 36 46，
   把尾数为6的都挂起来,放到同一个桶里面，这样就不会出现争抢位置，现在我们出现的争抢就内部解决，不会互相影响了，从根源上更好的去管理这个东西

表长度100

控制负载因子，能够极大的控制住效率–负载因子到了就扩容,
但一个桶的长度超过一定的值之后，就把他转化成一个红黑树,这样效率就很高了

//极端场景下
struct Date
{
    forward_list<T> _list;
    set<T> _list;
    size_t len
};
len 大于一定值的时候，就把forward_list 里面的数据插入到set里面，再把单链表里面的数据给删除掉

极端场景

1. 存50个值，40个值冲突，挂在同一个桶上
2. 存储了10000个值，平均每个桶的长度100，阶段场景山有些桶可能有上千个值

哈希函数

• 除留余数法:我们将每个数和其对应vector长度进行取余，当达到负载因子就要进行重新扩容，重新映射
• 平方取中法

假如关键字1234，就把它平方=1522356，取中间3位，223，
如果它不够3位，就继续对他进行平方，直到取出3位位置，也存在哈希冲突
不常用

闭散列

使用线性探测；冲突的时候，就往后进行探测，直到到达空位置，

enum Status //状态标记
 {
     EXISTS,
     EMPTY,
     DELETE
 };

 template <class K, class V>

 struct HashData
 {
     pair<K, V> _kv;//里面的每一个元素都是一个pair
     Status _status = EMPTY;//一开始的节点都设置为空
 };

 template <class K>
 struct Hash//哈希函数，将其转化成为一个可以进行取余的数，仿函数
 {
     size_t operator()(const K &key)
     {
         return key; //返回一个无符号数,负数的话，也变成一个正数
     }
 };

 //如果是key是string走的就是这个特化版本
 //模板的特化，上面有一个基础的类模板
 template <>

 struct Hash<string> //把这个参数直接确定,因为string用的很经常
 {
     size_t operator()(const string &s)
     {
         size_t val = 0;
         for (auto e : s)
         {
             val *= 131;
             val += e;
         }
         return val;
     }
 };

 //这个hash表即可给map也可给set
 //找一个值，遇到空才停，遇到删除还要继续找
 //出现的问题
 // 1.删除一个值，这个值应该设置成多少
 // 2.删除完毕之后，后面冲突的值怎么办,现在，把一个值删除之后，就要把他的状态标记成删除，不清理数据

 template <class K, class V, class HashFunc = Hash<K>>//这个可以支持int和string两种，其他的要我们自己来写仿函数

 class HashTable
 {
 private:
     vector<HashData<K, V>> _table; //我们数据不是都是按顺序的存储
     size_t _n = 0;                 //有效数据的个数，直接在这里给一个缺省参数
 public:
     /*
     散列表的载荷因子a=表中元素的个数/散列表的长度,a越大，冲突的概率就越大，a越小，冲突的概率就越小，如果超过了一定值，就要扩容
     */
     HashData<K, V> *Find(const K &key)
     {
         if (_table.size() == 0)
         {
             return nullptr; //没找到
         }
         HashFunc hc;//仿函数,实现哈希函数
         size_t start = hc(key) % _table.size(); //模上它的vector的元素大小,如果模上它的容量的话，可能回超出size的范围，无法访问_table[i],只能访问size以内的
         size_t i = 0;
         size_t index = start;

         while (_table[index]._status != EMPTY) //在这里死循环了
         {
             //数据存在，就继续往下探测
             if (_table[index]._kv.first == key && _table[index]._status == EXISTS)
             {
                 return &_table[index];//存在且等于，就直接返回对于的数组的地址回去
             }
             i++;
             index = start + i * i; //这个是依次探测,二次探测
             //如果到最后还有数据的话，那就要绕回来
             index %= _table.size();
         }

         return nullptr;
     }

     bool  Erase(const K &key)
     {
         HashData<K, V> *ret = Find(key);
         if (ret == nullptr)
         {
             //找不到要删除的值
             return false;
         }
         else
         {
             //找到了那个值
             ret->_status = DELETE;//我们不需要进行手动删除，直接把它的状态设置为删除即可
             _n--;
             return true;
         }
     }

     bool Insert(const pair<K, V>& kv)
     {

         HashData<K, V> *ret = Find(kv.first);
         if (ret != nullptr)
         {
             return false; //有一个重复的值
         }

         if (_table.size() == 0 || _n * 10 / _table.size() >= 7)
         {
             //越小，冲突的概率就越低，效率越高，但是空间浪费越高
             //繁殖，冲突的概率越高，效率越低，浪费越小
             //载荷因子大于0.7就要进行扩容
             size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;//table的大小变小了，假如说一开始还没有给这个table进行赋值，这个就没有大小，所以写一个对0进行操作
             // vector<HashData<K,V>>  newtable;

             // newtable.resize(newsize);//扩完容，就会把没有元素的地方初始化成0
             // //扩容完，要重新改变值的位置，原来冲突的可能不冲突了，不冲突的可能就冲突了，建立新的映射关系
             // //遍历原表，把原表的数据重新映射到新表
            
             HashTable<K, V, HashFunc> newHT;//这里用一个新对象，调用自己
             newHT._table.resize(newsize);
             for (size_t i = 0; i < _table.size(); i++)
             {
                 if (_table[i]._status == EXISTS)
                 {
                     //数据存在,就往我们新的ht里面插入
                     // newHT._table.insert(_table[i]._kv);
                     newHT.Insert(_table[i]._kv);
                 }
             }
             _table.swap(newHT._table); //把两个进行交换即可，这样就可以把我们想要的table给转换过来了
         }
         HashFunc hc;
         size_t start = hc(kv.first) % _table.size(); //模上它的vector的元素大小,如果模上它的容量的话，可能回超出size的范围，无法访问_table[i],只能访问size以内的
         size_t i = 0;
         size_t index = start; //探测旁边
                               //现在我们可以用探测i平方
                               /*
                                   vector<int> v;
                                   v.reserve(10);
                                   for(int i=0;i<10;i++)
                                   {cin>>v[i]}//这样是不行的，因为[]必须要保证这个地址上是有数据的
                               */
         //如果这个位置没数据，就直接放进去，如果有数据，就要开始线性探测
         //空或者删除都可以放

         //线性探测的大逻辑,很容易拥堵在一起，尤其是相连的一块，你占我，我占你
         //二次探测

         while (_table[index]._status == EXISTS)
         {
             //数据存在，就继续往下探测
             i++;
             index = start + i * i; //这个是依次探测
             //如果到最后还有数据的话，那就要绕回来
             index %= _table.size();
         }
         //一定是在一个可以放数据的地方
         _table[index]._kv = kv;
         _table[index]._status = EXISTS; //插入设置存在
         _n++;

         //找空位置的代价会很大
         return true;
     }
 };

散列表（哈希桶）

将vector里面的数据结构换成单链表
把冲突的数据都串在一起

template <class K, class V>

struct HashNode
{
    pair<K, V> _kv;
    HashNode<K, V> *_next; //我们用一个单链表,我们自己弄的
    HashNode(const pair<K, V> &kv)
        : _kv(kv), _next(nullptr)
    {
    }
};

template <class K>
struct Hash
{
    size_t operator()(const K &key)
    {
        return key; //负数也给他转化成非负数
    }
};

template <class K, class V, class HashFunc = Hash<K>>
class HashTable
{
    typedef HashNode<K, V> Node;

private:
    vector<Node *> _table; //链表里面的元素挂起来,指针数组
    size_t _n = 0;         //有效数据，计算负载因子
public:
    Node *Find(const K &key)
    {
        if (_table.empty())
        {
            return nullptr;
        }
        HashFunc hc;
        size_t index = hc(key) % _table.size();
        if (_table[index] == nullptr)
        {
            //没找到
            return nullptr;
        }
        else
        {
            //在它对应的链表下面找，看看能不能找的到
            Node *cur = _table[index]; //_table[index]就是对应链表的头节点
            while (cur)
            {
                if (cur->_kv.first == key)
                    return cur;
                cur = cur->_next;
            }
            return nullptr;
        }
    }
    bool Erase(const K &key)
    {
        if (_table.empty())
        {
            return false;
        }
        //找到了，就把它给删除掉
        HashFunc hc;
        size_t index = hc(key) % _table.size();
        Node *cur = _table[index];
        Node *prev = nullptr;
        while (cur)
        {
            if (cur->_kv.first == key)
            {
                if(prev==nullptr)
                {
                    //头删除
                    _table[index]=cur->_next;
                }
                else
                prev->_next = cur->_next;
                delete cur;
                --_n;
                return true;
            }
            else
            {
                prev = cur;
                cur = cur->_next;
            }
        }
        return false;
    }
    bool Insert(const pair<K, V> &kv)
    {

        Node *ret = Find(kv.first);
        if (ret)
        {
            return false;
        }

        HashFunc hc;

        if (_n == _table.size()) //这里我们可以让负载因子变得大一点,负载因子=1的时候扩容`
        {
            size_t newcp = _table.size() == 0 ? 10 : _table.size() * 2;
            //这里就自己来挪动，使用和闭散列一样的方法，不好，因为会一直要new节点，
            vector<Node *> newTable;
            newTable.resize(newcp); //扩容后要进行重新映射
            for (size_t i = 0; i < _table.size(); i++)
            {
                if (_table[i])
                {
                    //有数据
                    Node *cur = _table[i];
                    while (cur)
                    {
                        //把这个数据弄下来，直接
                        Node *next = cur->_next;
                        size_t index = hc(cur->_kv.first) % newTable.size();
                        //然后进行头插
                        cur->_next = newTable[index];
                        newTable[index] = cur;
                        cur = next;
                    }
                }
                _table[i] = nullptr; //弄完了就把对应的数据给清空即可
            }
            // newcp里面的数据都是我们想要的
            _table.swap(newTable);
        }
        size_t index = hc(kv.first) % _table.size();
        //没有数据
        Node *newnode = new Node(kv); //新的头节点
        newnode->_next = _table[index];
        _table[index] = newnode; //
        //用头插法把数据插进去，因为重新映射代价比较大

        _table[index] = newnode;
        _n++;
        return true;
    }
};