哈希桶处理哈希冲突

哈希桶：哈希桶就是盛放不同key链表的容器（即是哈希表），我们可以把每个key的位置看作是一个指针，该指针所指向的位置里放了一个链表，可以认为是指针数组，故该方法也叫开链式。

相比闭散列，哈希桶提高了空间利用率：在实现哈希表时，常见的方法是线性探测、二次探测，这两个算法的具体实现可以查看我的博客。但是这两个算法有一个共同点就是：空间利用率低。为什么这么说呢？线性探测、二次探测的高效性很大程度上要取决于它的载荷因子，载荷因子即：存放关键字个数 / 空间大小。

通过查阅资料，我发现，使用素数做除数可以减少哈希冲突。见下：

素数表：使用素数做除数可以减少哈希冲突

// 使用素数表对齐做哈希表的容量，降低哈希冲突

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

};

下图进行哈希桶处理哈希冲突的展示

下面通过库中的vactor进行存放指向链表的指针，每个结点里包含_key,_value和_next。

#pragmatemplatestruct DefaultHashFunc{        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 + (unsigned int)(*str++);        }        return (hash & 0x7FFFFFFF);}template<>struct DefaultHashFunc{        size_t operator()(const string& str)        {                return BKDRHash(str.c_str());        }};templatestruct HashTableNode//结点{        K _key;        V _value;        HashTableNode* _next;        HashTableNode(const K& key, const V& value)                :_key(key)                , _value(value)                , _next(NULL)        {}};template>class HashTableBucket{        typedef HashTableNode Node;public:        HashTableBucket();        HashTableBucket(const HashTableBucket& htb);        HashTableBucket& operator=(HashTableBucket htb);        void PrintTables();        bool Insert(const K& key,const V& value);//防冗余，在删除和查找时只需要key        Node* Find(const K& key);        bool Remove(const K& key);protected:        size_t _HashFunc(const K& key);        size_t _GetNextPrime(size_t size);//获取下一个素数（利用素数表，使用素数做除数可以减少哈希冲突）        void _CheckExpand();private:        vector _tables;//开链式为指针数组，指针指向链表        size_t _size;//有效数据数，vector中的size()为有效空间数};

实现_HashFunc(const K& key)，通过伪函数来判断不同类型的key所在链表的位置。

template>size_t HashTableBucket::_HashFunc(const K& key){        HashFunc htb;        return htb(key) % (_tables.size());//htb(key)伪函数}

1. 插入函数的实现（Insert）

（1）检查容量。调用_CheckExpand()函数检查负载因子a，考虑是否扩张，当a为1时进行扩容。

（2）检查插入的key是否已经存在，不存在返回false，存在进行（3）操作。

（3）进行头插。

template>bool HashTableBucket::Insert(const K& key, const V& value){//防冗余，在删除和查找时只需要key        _CheckExpand();//检查是否扩容        for (size_t i = 0; i < _tables.size(); ++i)        {                Node* cur = _tables[i];                while (cur)                {//如果插入的元素存在就返回false                        if (cur->_key == key)                        {                                return false;                        }                        cur = cur->_next;                }        }               //头插        size_t index = _HashFunc(key);        Node* tmp = new Node(key, value);        tmp->_next = _tables[index];        _tables[index] = tmp;        ++_size;        return true;

2. 查找函数的实现（Find）

（1）调用_HashFunc()函数找到要寻找的Key所在的链表位置。

（2）通过遍历链表查找key。

template>HashTableNode* HashTableBucket::Find(const K& key)//查找{        size_t index = _HashFunc(key);//链表结点位置        Node* cur = _tables[index];        while (cur)        {                if (cur->_key == key)                {                        return cur;                }                cur = cur->_next;        }        return NULL;}

3. 删除函数的实现（Remove）

（1）调用Find（）函数，判断需要删除的key是否存在，不存在就返回false，存在就进行（2）操作。

（2）调用_HashFunc()函数找到key所在链表的位置，先通过遍历链表找到del结点的上一个结点prev，然后使prev的下一个结点指向del的下一个结点。

template>bool HashTableBucket::Remove(const K& key)//删除{        if (Find(key) == NULL)        {                return false;        }        size_t index = _HashFunc(key);        //需要找到删除结点的前后结点        Node* del = Find(key);        Node* next = del->_next;        Node* prev = _tables[index];        while (prev)        {                if (prev->_next == del)                {                        break;                }                prev = prev->_next;        }        if (next)//如果next存在时，进行链接        {                prev->_next = next;        }        del = NULL;        return true;}

检查是否需要扩容_CheckExpand()的实现。

template>void HashTableBucket::_CheckExpand()//检查负载因子，考虑是否扩容{        if (_size >= _tables.size())//负载因子达到了1，进行扩容        {                size_t NewSize = _GetNextPrime(_size);                //进行结点复制                vector NewTables;                NewTables.resize(NewSize);                for (size_t i = 0; i < _tables.size(); ++i)                {                        Node* cur = _tables[i];                        while (cur)//头插                        {                                Node* tmp = cur;                                cur = cur->_next;                                size_t index = _HashFunc(tmp->_key);//重新确定元素在表中位置                                tmp->_next = NewTables[index];                                NewTables[index] = tmp;                        }                }                _tables.swap(NewTables);//调用vector中的swap接口进行交换        }}template>size_t HashTableBucket::_GetNextPrime(size_t size){//获取下一个素数（利用素数表，使用素数做除数可以减少哈希冲突）        //使用素数表对齐做哈希表的容量，降低哈希冲突        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        };        for (size_t i = 0; i < _PrimeSize; ++i)        {                if (_PrimeList[i] > size)                {                        return _PrimeList[i];                }                return _PrimeList[i - 1];        }        return _PrimeList[_PrimeSize];//如果size大于或等于素数表中数据，就返回表中最大数}

测试用例如下，实现字典（可以一对多）查询。

HashTableBucket> dict;        vector v;        v.push_back("manager");        dict.Insert("经理", v);        v.clear();        v.push_back("移动");        v.push_back("距离");        dict.Insert("remove",v);        HashTableNode>* ret = dict.Find("remove");        ret->_value.push_back("搬家");        vector& words = ret->_value;        for (size_t i = 0; i < words.size(); ++i)//打印对应的多个字符串        {                cout << words[i].c_str() << endl;        }