【数据结构】哈希桶

标签: 数据结构  哈希桶

  在上一篇博客中,我们简单地介绍了哈希表,以及解决哈希冲突的办法;今天我们介绍解决哈希冲突的另一种方法——开散列法。开散列法又叫链地址法,首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点组成一个向量。说起来可能很复杂,其实很简单,看一个图就明白了:假设哈希函数为Hash(key)=key%10
这里写图片描述

  • 假如哈希函数被**了,可能会对哈希桶进行攻击,从而将哈希桶退化成单链表,此时查找效率将会大大降低,我们可以把单链表换成红黑树,提高查找效率。
  • 当哈希桶的个数与插入的结点个数相等时,我们就增加容量。

以下是我实现的哈希桶:

// 获得一个适合的素数
const int _PrimeSize = 28;//素数表
static const unsigned long _PrimeList[_PrimeSize] =
{
    53ul, 97ul, 193ul, 389ul, 769ul,
    1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    1610612741ul, 3221225473ul, 4294967291ul
};
size_t GetNextPrime(size_t num)
{
    for (size_t i = 0; i < _PrimeSize; i++)
    {
        if (_PrimeList[i]>num)
            return _PrimeList[i];
    }
    return _PrimeList[_PrimeSize - 1];
}

template <class K>
class KeyToIntDef
{
public:
    size_t operator()(const K& key)
    {
        return key;
    }
};
// 将字符串转换成整型
static size_t BKDRHash(const char * str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313
    unsigned int hash = 0;
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
    size_t ret = (hash & 0x7FFFFFFF);
    return ret;
}
class StringToInt
{
public:
    size_t operator()(const string& key)
    {
        return BKDRHash(key.c_str());
    }
};


#include <iostream>
#include <vector>
#include <string>
using namespace std;
template <class K, class V>
struct HashNode//结点
{
    pair<K, V> _kv;
    HashNode<K, V>* _pNext;
    HashNode(const pair<K, V>& kv)
        : _kv(kv)
        , _pNext(NULL)
    {}
};

template <class K, class V, class KeyToInt>
class HashTable;//前置声明
//迭代器
template <class K, class V, class KeyToInt = KeyToIntDef<K>>
struct HashTableIterator
{
    typedef HashNode<K, V> Node;
    typedef Node* PNode;
    typedef HashTableIterator<K, V, KeyToInt> Self;

    PNode _pCur;
    HashTable<K, V, KeyToInt>* _ht;
public:
    HashTableIterator()
        : _pCur(NULL)
        , _ht(NULL)
    {}

    HashTableIterator(const PNode pCur, HashTable<K, V, KeyToInt>* ht)
        : _pCur(pCur)
        , _ht(ht)
    {}

    HashTableIterator(Self& s)
        : _pCur(s._pCur)
        , _ht(s._ht)
    {}

    Self& operator++()
    {
        Next();
        return *this;
    }

    Self operator++(int)
    {
        HashTableIterator temp(*this);
        Next();
        return temp;
    }

    pair<K, V>& operator*()
    {
        return _pCur->_kv;
    }

    pair<K, V>* operator->()
    {
        return &(operator*());
    }

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

    bool operator!=(const Self& s)
    {
        return _pCur != s._pCur;
    }
private:
    void Next()
    {
        if (_pCur->_pNext)
            _pCur = _pCur->_pNext;
        else
        {//找下一个非空桶
            size_t bucketNo = _ht->HashFunc(_pCur->_kv.first) + 1;
            for (; bucketNo < _ht->_hashTable.capacity(); bucketNo++)
            {
                if (_ht->_hashTable[bucketNo])
                {
                    _pCur = _ht->_hashTable[bucketNo];
                    return;
                }
            }
            _pCur = NULL;//没有找到
        }
        return;
    }
};
//哈希桶
template <class K, class V, class KeyToInt = KeyToIntDef<K>>
class HashTable
{
    typedef HashNode<K, V> Node;
    typedef Node* PNode;
    friend HashTableIterator<K, V, KeyToInt>;
public:
    typedef HashTableIterator<K, V, KeyToInt> Iterator;
public:
    HashTable(size_t capacity = 10)
    {
        capacity = GetNextPrimer(capacity);
        _hashTable.resize(capacity);
        _size = 0;
    }

    Iterator Begin()
    {
        for (size_t bucketNo = 0; bucketNo < _hashTable.capacity(); bucketNo++)
        {
            if (_hashTable[bucketNo])
                return Iterator(_hashTable[bucketNo], this);
        }
        return Iterator(NULL, this);
    }

    Iterator End()
    {
        return Iterator(NULL, this);
    }
//////////////////////////插入,查找及删除/////////////////////////////////
    pair<Iterator, bool> InsertEqual(const pair<K, V>& kv)//允许重复
    {
        CheckCapacity();
        size_t bucketNo = HashFunc(kv.first);
        PNode pNewNode = new Node(kv);
        pNewNode->_pNext = _hashTable[bucketNo];//头插
        _hashTable[bucketNo] = pNewNode;
        _size++;
        return make_pair(Iterator(pNewNode, this), true);
    }

    pair<Iterator, bool> InsertUnique(const pair<K, V>& kv)//key值唯一
    {
        CheckCapacity();
        size_t bucketNo = HashFunc(kv.first);
        PNode pCur = _hashTable[bucketNo];
        while (pCur)
        {
            if (kv.first == pCur->_kv.first)
                return make_pair(Iterator(pCur, this), false);
            pCur = pCur->_pNext;
        }
        pCur = new Node(kv);
        pCur->_pNext = _hashTable[bucketNo];
        _hashTable[bucketNo] = pCur;
        _size++;
        return make_pair(Iterator(pCur, this), true);
    }

    Iterator Find(const K& key)
    {
        size_t bucketNo = HashFunc(key);
        PNode pCur = _hashTable[bucketNo];

        while (pCur)
        {
            if (pCur->_kv.first == key)
                return Iterator(pCur, this);
            pCur = pCur->_pNext;
        }
        return Iterator(NULL, this);
    }

    Iterator Erase(Iterator pos)//key值唯一
    {
        if (pos._pCur == NULL)
            return Iterator(NULL, this);
        size_t key = pos._pCur->_kv.first;
        size_t bucketNo = HashFunc(key);
        PNode pCur = _hashTable[bucketNo];
        PNode pPre = NULL;
        while (pCur)
        {
            if (pCur->_kv.first == key)
            {
                if (_hashTable[bucketNo] == pCur)//pCur是首元素结点
                    _hashTable[bucketNo] = pCur->_pNext;
                else
                    pPre->_pNext = pCur->_pNext;
                delete pCur;
                pCur = NULL;
                _size--;
                return Iterator(pPre, this);
            }
            else
            {
                pPre = pCur;
                pCur = pCur->_pNext;
            }
        }
        return Iterator(NULL, this);
    }

    size_t Erase(const K& key)//key值可以重复
    {
        size_t oldsize = _size;
        size_t bucketNo = HashFunc(key);
        PNode pCur = _hashTable[bucketNo];
        PNode pPre = NULL;
        while (pCur)
        {
            if (pCur->_kv.first == key)
            {
                if (pCur == _hashTable[bucketNo])
                {
                    _hashTable[bucketNo] = pCur->_pNext;
                    delete pCur;
                    pCur = _hashTable[bucketNo];
                }
                else
                {
                    pPre->_pNext = pCur->_pNext;
                    delete pCur;
                    pCur = pPre->_pNext;
                }
                _size--;
            }
            else
            {
                pPre = pCur;
                pCur = pPre->_pNext;
            }
        }
        if (oldsize == _size)
            return 0;
        else
            return oldsize - _size;
    }
///////////////////////////其它常用函数///////////////////////////////
    size_t Count(const K key)//值为key的元素个数
    {
        size_t count = 0;
        size_t bucketNo = HashFunc(key);
        PNode pCur = _hashTable[bucketNo];
        while (pCur)
        {
            if (pCur->_kv.first == key)
                count++;
            pCur = pCur->_pNext;
        }
        return count;
    }

    size_t BucketCount()const//桶的个数
    {
        return _hashTable.capacity();
    }

    size_t BucketSize(size_t bucketNo)const//桶内元素个数
    {
        size_t count = 0;
        PNode pCur = _hashTable[bucketNo];
        while (pCur)
        {
            count++;
            pCur = pCur->_pNext;
        }
        return count;
    }

    V& FindORInsert(const K& key)//查找值为key,如果找到了,返回对应的value,
                                 //如果没有找到插入该结点,返回缺省的value
    {
        Iterator ret = InsertUnique(make_pair(key, V())).first;
        return (*ret).second;
    }

    bool Empty()const//是否为空
    {
        return _size == 0;
    }

    size_t Size()const//插入的总数
    {
        return _size;
    }

    void Clear()//清空
    {
        for (size_t bucketNo = 0; bucketNo < _hashTable.capacity(); bucketNo++)
        {
            PNode pCur = _hashTable[bucketNo];
            while (pCur)
            {
                _hashTable[bucketNo] = pCur->_pNext;
                delete pCur;
                pCur = _hashTable[bucketNo];
                _size--;
            }
        }
    }

    ~HashTable()
    {
        Clear();
    }
private:
    size_t HashFunc(const K& key)//哈希函数
    {
        return KeyToInt()(key) % _hashTable.capacity();
    }

    void CheckCapacity()//扩容
    {
        size_t capacity = _hashTable.capacity();
        if (_size == capacity)
        {
            HashTable<K, V, KeyToInt> newHt(GetNextPrime(capacity));
            for (size_t bucketNo = 0; bucketNo < capacity; bucketNo++)
            {
                PNode pCur = _hashTable[bucketNo];
                while (pCur)
                {
                    newHt.InsertEqual(pCur->_kv);
                    pCur = pCur->_pNext;
                }
            }
            _hashTable.swap(newHt._hashTable);
        }
    }
private:
    vector<PNode> _hashTable;
    size_t _size;
};

void test()
{
    HashTable<int, int> ht;
    ht.InsertEqual(make_pair(1, 1));
    ht.InsertEqual(make_pair(5, 5));
    ht.InsertEqual(make_pair(15, 15));
    ht.InsertEqual(make_pair(15, 15));
    ht.InsertEqual(make_pair(35, 35));
    ht.InsertEqual(make_pair(9, 9));
    HashTable<int, int>::Iterator it = ht.Begin();
    if (!ht.Empty())
    {
        while (it != ht.End())
        {
            cout << it->first << " " ;
            cout << (*it).second << endl;
            it++;
        }
        cout << endl;
        cout << ht.BucketSize(5) << endl;
        cout << ht.BucketCount() << endl;
        cout << ht.Count(15) << endl;
    }
    it = ht.Begin();
    cout << ht.Erase(15) << endl;
    HashTable<int, int>::Iterator ret = ht.Find(1);
    ht.Erase(ret);
    cout << ht.Size() << endl;
    ht.Clear();

    HashTable<string, string, StringToInt> ht1;
    ht1.InsertUnique(make_pair("111", "111"));
    ht1.InsertUnique(make_pair("111", "111"));
    cout << ht1.FindORInsert("111") << endl;
}
版权声明:本文为wei_cheng18原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wei_cheng18/article/details/79821965

智能推荐

phpstudy的mysql版本升级至5.7

phpstudy安装的mysql版本一般都是5.5或5.4的,但是有时候做项目又必须用到mysql5.7版本,所以我们现在来看一下如何在phpstudy的环境下将mysql版本升级至5.7   温馨提醒: 先删掉所有环境变量,如果是之前有的话,不然怎么安装cmd上指向的还是原来的版本。安装完再设新的环境变量。 并且卸载掉mysqld服务mysqld remove。如果不先删除的话,可能会...

RIP/DHCP/ACL综合实验

组播: 加入组的组成员才会接受到消息,只需要将流量发送一次到组播地址 减少控制面流量,减少头部复制, RIP1  广播   有类  不支持认证 RIP2  组播   无类  (支持VLAN)、支持认证 所有距离矢量路由协议:具有距离矢量特征的协议,都会在边界自动汇总 控制平面  路由的产生是控制平面的流量 数据平面  ...

【Sublime】使用 Sublime 工具时运行python文件

使用 Sublime 工具时报Decode error - output not utf-8解决办法   在菜单中tools中第四项编译系统 内最后一项增添新的编译系统 自动新建 Python.sublime-build文件,并添加"encoding":"cp936"这一行,保存即可 使用python2 则注释encoding改为utf-8 ctr...

java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的,也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包, 比如:import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令:lock...

Python 中各种imread函数的区别与联系

  原博客:https://blog.csdn.net/renelian1572/article/details/78761278 最近一直在用python做图像处理相关的东西,被各种imread函数搞得很头疼,因此今天决定将这些imread总结一下,以免以后因此犯些愚蠢的错误。如果你正好也对此感到困惑可以看下这篇总结。当然,要了解具体的细节,还是应该 read the fuc...

猜你喜欢

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...