武汉c培训
达内武汉中心

15271940953

热门课程

C++ 哈希表、线性探测、二次探测

  • 时间:2016-06-02
  • 发布:霜柒染
  • 来源:51CTO

#pragma once
#include<iostream>//含一次探测  二次探测
#include<vector>
#include<math.h>
 
using namespace std;
 
enum Status
{
    EXIST,
    EMPTY,
    DELET,
};
 
template <class K,class V> //key/value形式结构体
struct KV
{
    K _key;
    V _value;
    KV(const K& key = K(), const V& value = V())
        :_key(key)
        , _value(value)
    {}
};
 
template <class K, class V>
class HashTable
{
public:
    KV<K,V>* _tables;
    size_t _size;
    size_t _capacity;
    Status* _status;
 
public:
    HashTable()
        :_tables(NULL)
        ,_size(0)
        , _capacity(0)
        , _status(NULL)
    {}
    void  Insert(const K& key , const V& value )
    {
        if (_capacity == 0 || _size * 10 / _capacity > 7)
        {
            if(!_IncreaseCapacity())
                cout<<"线性探测散列表已满"<<endl;
        }
             
        size_t i = _HashFanction1(key);
        do
        {
             
            if (key == _tables[i]._key&&_status[i]==EXIST)
                    break;
            if (_status[i] != EXIST)
            {  
                _tables[i]._key = key;
                _tables[i]._value = value;
                _status[i] = EXIST;
                ++_size;
                break;
            }
            else if (++i >= _capacity)
                i = 0;
        } while (1);
         
    }
 
    void  Insert2(const K& key, const V& value)
    {
        if (_capacity == 0 || _size * 10 / _capacity > 7)
        {
            if (!_IncreaseCapacity())
                cout << "线性探测散列表已满" << endl;
        }
        int count = 0;//二次探测的计数器
        size_t i = _HashFanction2(key,count);
        do
        {
            if (i<0)
                i = _capacity + i;
            if (key == _tables[i]._key&&_status[i] == EXIST)
                break;
            if (_status[i] != EXIST)
            {
                _tables[i]._key = key;
                _tables[i]._value = value;
                _status[i] = EXIST;
                ++_size;
                break;
            }
            else 
                i = _HashFanction2(key, i);
        } while (1);
 
    }
 
    int Find(const K& key)
    {
        size_t i = _HashFanction1(key);
        size_t j = i;
        do
        {
             
            if (_status[i] == EXIST&&key==_tables[i]._key)
            {
                 
                return i;
            }
            else if (++i >= _capacity)
                i = 0;
        } while (i!=j);
        return -1;
 
    }
 
    void Remove(const K& key)
    {
        size_t i = _HashFanction1(key);
        size_t j = i;
        do
        {
 
            if (_status[i] == EXIST&&key == _tables[i]._key)
            {
                _status[i] = DELET;
                break;
            }
            else if (++i >= _capacity)
                i = 0;
        } while (i != j);
    }
     
    void print()
    {
        size_t i = 0;
        for (; i < _capacity; ++i)
        {
            printf("[%d] K: %d  V: %d S: %d \n",i, _tables[i]._key, _tables[i]._value, _status[i]);
        }
    }
     
protected:
    size_t _HashFanction1(const K& key)//一次探测 (线性探测)
    {
 
        return key%_capacity;
    }
 
    int _HashFanction2(const K& key,const int i)//二次次探测 (防止数据积累在一块内存)
    {
 
        return (key+(int)pow(-1,i)*i*i)%_capacity;
    }
 
    bool _IncreaseCapacity()
    {
        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 (int i = 0; i < _PrimeSize; ++i)
        {
            if (_PrimeList[i]>_capacity)
            {
                size_t newCapacity = _PrimeList[i];
                HashTable<K, V> newHash;
                newHash._tables = new KV<K,V>[newCapacity];
                newHash._status = new Status[newCapacity];
                newHash._capacity=_PrimeList[i];
                for (size_t j = 0; j < newCapacity; ++j)
                {
                    if (_status&&j<_capacity&&_status[j] == EXIST)
                    {
                        //newHash.Insert(_tables[j]._key, _tables[j]._value);//一次探测的增容调一次探测的插入函数
                        newHash.Insert2(_tables[j]._key, _tables[j]._value);//二次探测。。。。。。
                    }
                    else
                    {
                        newHash._status[j] = EMPTY;
                        newHash._tables[j]._key = 0;
                        newHash._tables[j]._value = 0;
                    }
                         
                }
                swap(_tables, newHash._tables);
                swap(newHash._status,_status);
                swap(newHash._capacity, _capacity);
 
 
                return true;
            }
        }
        return false;
 
    }
 
};
 
#pragma once
 
#include<iostream>//哈希桶
#include<vector>
#include<math.h>
#include<string>
 
using namespace std;
 
template <class K>
class GetKey
{
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++);
    }
    return (hash & 0x7FFFFFFF);
}
 
template <>
class GetKey<string>
{
public:
    size_t operator()(const string & key)
    {
        return BKDRHash(key.c_str());
    }
};
template <class K,class V> //key/value形式结构体
struct KeyValue
{
    K _key;
    V _value;
    KeyValue<K, V>* _next;
    KeyValue(const K& key = K(), const V& value = V())
        :_key(key)
        , _value(value)
        , _next(NULL)
    {}
};
 
template <class K, class V>
class HashBucket
{
public:
    vector<KeyValue<K, V>*> _tables;
    size_t _size;
 
public:
    HashBucket()
        :_size(0)
    {}
    void  Insert(const K& key , const V& value )
    {
        if (_tables.capacity()==0|| _size * 10 / _tables.capacity() > 7)
        {
            if(!_IncreaseCapacity())
                cout<<"线性探测散列表已满"<<endl;
        }
             
        size_t i = _HashFanction1(key);
        KeyValue<K, V>* cur = _tables[i];
        if (cur == NULL)
            _tables[i] = new KeyValue<K, V>(key, value);
        else
        {
            while (cur)
            {
 
                if (cur->_key == key)
                    return;
                else if (cur->_next == NULL)
                    break;
                else
                    cur = cur->_next;
            }
            cur->_next = new KeyValue<K, V>(key, value);
        }
        ++_size;
    }
 
    int Find(const K& key)
    {
        size_t i = _HashFanction1(key);
        KeyValue<K, V>* cur = _tables[i];
        while (cur)
        {
            if (cur->_key == key)
                return i;
            cur = cur->_next;
        }
        return -1;
 
    }
 
    void Remove(const K& key)
    {
        size_t i = _HashFanction1(key);
        KeyValue<K, V> * cur =_tables[i];
        KeyValue<K, V> * prev = NULL;
 
        while (cur)
        {
            if (cur->_key == key)
            {
                if (prev)
                {
                    prev->_next = cur->_next;
                }
                else
                    _tables[i] = NULL;
                    delete cur;
                    return;
            }
            prev = cur;
            cur = cur->_next;
             
        }
    }
     
    void print()
    {
        size_t i = 0;
        for (; i < _tables.capacity(); ++i)
        {
            KeyValue<K, V>* cur = _tables[i];
             
            if (cur == NULL)
                //printf("[%d]:K= %d V= %d ->", i, -1,-1);
                cout<< "[" << i << "] "<< -1 << " " << -1 << " " << "->";
            while (cur)
            {
                 
                //printf("[%d]:K= %d V= %d ", i, cur->_key,cur->_value);
                cout << "[" << i << "] "<< _tables[i]->_key << " " << _tables[i]->_value << " " << "->";
 
                cout << "->";
                cur = cur->_next;
            }
            cout <<" NULL"<<endl;
        }
 
    }
     
protected:
    size_t _GetKey(const K& key)
    {
        return GetKey<K>()(key);
    }
    size_t _HashFanction1(const K& key)//一次探测 (线性探测)
    {
        size_t k = _GetKey(key);
        return k%_tables.capacity();
    }
 
    bool _IncreaseCapacity()
    {
        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 (int i = 0; i < _PrimeSize; ++i)
        {
            if (_PrimeList[i]>_tables.size())
            {
                size_t newCapacity = _PrimeList[i];
                vector<KeyValue<K, V>*> newtables;
                newtables.resize(newCapacity, 0);
                for (size_t j = 0; j < _tables.capacity(); ++j)
                {
                    KeyValue<K, V>* cur = _tables[j];
                    while (cur)
                    {
                        size_t k = _HashFanction1(cur->_key);
                         
                        KeyValue<K, V>* tmp = cur;
                        KeyValue<K, V>* tmp2 = newtables[k];
                        if (tmp2 = NULL)
                        {
                            newtables[i] = cur;
                            break;
                        }
                        while (tmp2->_next)
                        {  
                            tmp2->_next = cur;
                        }
                        tmp->_next = cur;
                        cur->_next = NULL;
                          _tables[j] = tmp;
                       cur = tmp;
                    }
                     
                }
                swap(newtables, _tables);
            }
            return true;
        }
    return false;
 
}
 
};
 
#include"hashtable.hpp" //测试用例
#include"hashbucket.hpp"
 
using namespace std;
 
void test()
{
 
    HashTable<int, int> h1;
     
    for (int i = 0; i <30;++i)
        h1.Insert(i, i);
    h1.Insert(100,1);
    h1.Insert(170, 3);
    h1.Insert(223, 5);
    h1.Insert(56, 7);
    h1.Insert(550,9);
    h1.print();
    cout<<h1.Find(223)<<endl;
    cout << h1.Find(224) << endl;
    h1.Remove(56);
    h1.Remove(58);
 
    h1.print();
 
}
 
void test2()
{
 
    HashTable<int, int> h1;
 
    for (int i = 0; i < 30;++i)
    h1.Insert(i, i);
    h1.Insert2(100, 1);
    h1.Insert2(170, 3);
    h1.Insert2(223, 5);
    h1.Insert2(56, 7);
    h1.Insert2(550, 9);
    h1.print();
    cout << h1.Find(223) << endl;
    cout << h1.Find(224) << endl;
    h1.Remove(56);
    h1.Remove(58);
 
    h1.print();
}
 
void test3()
{
    HashBucket<int, int>  h1;
    h1.Insert(1,1);
    h1.Insert(3, 3);
    h1.Insert(5, 5);
    h1.Insert(7, 7);
    h1.Insert(54, 54);
    h1.Insert(107, 107);
    for (int i = 0; i < 99;i+=2)
        h1.Insert(i, i);
 
    h1.print();
    cout<<h1.Find(1)<<endl;
    cout<<h1.Find(107)<<endl;
    cout << h1.Find(5) << endl;
 
    h1.Remove(54);
    h1.print();
 
 
}
void test4()
{
    HashBucket<string, string>  h1;
    h1.Insert("裴培华", "帅哥");
    h1.Insert("农文彤", "大屌");
    h1.Insert("鸭仔", "舎宝");
    h1.Insert("童坤坤", "学霸");
    h1.print();
    cout<<h1.Find("裴培华")<<endl;
    h1.Remove("农文彤");
    h1.print();
 
 
}
 
int main()
{
    //test();
    //test2();
    //test3();
    test4();
    return 0;
}
上一篇:武汉C++培训:c++ 排序集合
下一篇:c++ 堆的创建和堆排序
选择城市和中心
贵州省

广西省

海南省