散列表(HashTable)

  散列表

    i. 散列函数

    i. 冲突解决

      ii. 分离链表法

      ii. 开放地址法

        iii. 线性探测法

        iii. 平方探测法

        iii. 双散列

      ii. 再散列

      ii. 可扩散列

    i. 装填因子:元素个数 / 散列表大小

 

  C++实现

   1. 冲突解决:分离链表法

      散列函数:key % tableSize

《散列表(HashTable)》
《散列表(HashTable)》

/*
    散列函数: key % tableSize
    冲突解决: 分离链表法
*/
#include <iostream>
#include <vector>
#include <list>

using namespace std;

typedef int value;

class HashTable
{
public:
    HashTable(unsigned size) : _size(size) 
    {
        _table = new vector<list<value>* >(size);

        for (size_t i = 0; i < _size; i++)
        {
            (*_table)[i] = new list<value>;
        }
    }

    void insert(value val)
    {
        (*_table)[ val % _size ]->push_back(val);
    }

    value find(value val)
    {
        list<value>::const_iterator it = (*_table)[val % _size]->cbegin();

        while (it != (*_table)[val % _size]->cend())
        {
            if (*it == val)
                return *it;

            it++;
        }

        return NULL;
    }

    ~HashTable()
    {
        for (size_t i = 0; i < _size; i++)
        {
            delete (*_table)[i];
        }

        delete _table;
    }

private:
    vector<list<value>* >* _table;
    unsigned _size;
};

int main()
{
    HashTable h(11);

    h.insert(4);
    h.insert(4 + 11);

    cout << h.find(4 + 11);

    return 0;
}

View Code

 

  2. 冲突解决:开放地址法 之 线性探测

   散列函数:(key + collisionNum) % TableSize

   装填因子:散列大小 > 元素个数 × 2

《散列表(HashTable)》
《散列表(HashTable)》

/*
冲突解决:开放地址法 之 线性探测
散列函数:(key + collisionNum) % TableSize
装填因子:散列大小 > 元素个数 × 2
*/

#include <iostream>
#include <vector>

using namespace std;

class HashTable
{
    friend void dump(const HashTable&);

public:
    HashTable(size_t size = 10) : _size(size)
    {
        _table = new vector<int>(_size);

        for (size_t i = 0; i < _size; i++)
        {
            _table->operator[](i) = NULL;
        }
    }

    void insert(int val)
    {
        for (unsigned i = 0; i < _size; i++)
        {
            if (_table->operator[](_hash(val, i)) == NULL)
            {
                _table->operator[](_hash(val, i)) = val;

                return;
            }
        }
    }

    int find(int val) const
    {
        for (unsigned i = 0; i < _size; i++)
        {
            if (_table->operator[](_hash(val, i)) == val)
            {
                return _table->operator[](_hash(val, i));
            }
        }

        return NULL;
    }

    ~HashTable()
    {
        delete _table;
    }

private:
    size_t _hash(size_t val, unsigned collision) const
    {
        return (val + collision) % _size; //散列函数 线性探测
    }

    vector<int>* _table;
    size_t _size;
};

void dump(const HashTable& h)
{
    vector<int>::const_iterator it = h._table->cbegin();

    while (it != h._table->cend())
    {
        cout << it - h._table->cbegin() << " " << *it++ << endl;
    }
}

int main()
{
    HashTable h(10);

    h.insert(89);
    h.insert(18);
    h.insert(49);
    h.insert(58);
    h.insert(69);

    dump(h);

    cout << h.find(49) << endl;
    cout << h.find(58) << endl;

    return 0;
}

View Code

 

  3. 冲突解决:开放地址法 之 平方探测

  散列函数:(key + collisionNum ^ 2) % TableSize

  装填因子:散列大小 > 元素个数 × 2

《散列表(HashTable)》
《散列表(HashTable)》

/*
    冲突解决:开放地址法 之 平方探测
    散列函数:(key + collisionNum ^ 2) % TableSize
    装填因子:散列大小 > 元素个数 × 2
*/

#include <iostream>
#include <vector>

using namespace std;

class HashTable
{
    friend void dump(const HashTable&);

public:
    HashTable(size_t size = 10) : _size(size)
    {
        _table = new vector<int>(_size);

        for (size_t i = 0; i < _size; i++)
        {
            _table->operator[](i) = NULL;
        }
    }

    void insert(int val)
    {
        for (unsigned i = 0; i < _size; i++)
        {
            if (_table->operator[]( _hash(val, i)) == NULL)
            {
                _table->operator[]( _hash(val, i)) = val;

                return;
            }
        }
    }

    int find(int val) const
    {
        for (unsigned i = 0; i < _size; i++)
        {
            if (_table->operator[](_hash(val, i)) == val)
            {
                return _table->operator[](_hash(val, i));
            }
        }

        return NULL;
    }

    ~HashTable()
    {
        delete _table;
    }

private:
    size_t _hash(size_t val, unsigned collision) const
    {
        return (val + collision * collision) % _size; //散列函数,平方探测
    }

    vector<int>* _table;
    size_t _size;
};

void dump(const HashTable& h) 
{
    vector<int>::const_iterator it = h._table->cbegin();

    while (it != h._table->cend())
    {
        cout << it - h._table->cbegin() << " " << *it++ << endl;
    }
}

int main()
{
    HashTable h(10);

    h.insert(89);
    h.insert(18);
    h.insert(49);
    h.insert(58);
    h.insert(69);

    dump(h);

    cout << h.find(49) << endl;
    cout << h.find(58) << endl;

    return 0;
}

View Code

 

    原文作者:冯煜博
    原文地址: https://www.cnblogs.com/fengyubo/p/5107511.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞