java数据结构中哈希表的线性探测算法是什么

本篇文章给大家分享的是有关java数据结构中哈希表的线性探测算法是什么，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。

构造哈希表常用的方法是：

除留余数法--取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。HashKey= Key % P。

直接定址法--取关键字的某个线性函数为散列地址HashKey= Key 或 HashKey= A*Key + BA、B为常数。

我在这里主要使用一下除留余数法Hash(key) =Key%P，（P这里是哈希表的长度）p最好是素数考虑降低哈希冲突的原因，我并没有在这上面过于追究此处哈希表长度10，见线性探测图。

哈希表经常遇到的一个问题就是哈希冲突。

哈希冲突是什么呢？哈希冲突指的是：不同的关键字经过相同的哈希函数映射到相同的的哈希地址处。

要解决哈希冲突闭散列方法主要有两个：线性探测与二次探测。

在这里，我将线性探测的原理用下图表述：

线性探测

线性探测代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include<string>

//线性探测的特化处理可以处理自定义类型的数据
enum State
{
   EMPTY,//该位置未存放元素
   DELETE,//该位置元素已被删除
   EXIST,//该位置存在元素
};

//处理基本类型
template<class K>
struct DefaultFuncer
{
    size_t operator()(const K& key)
    {
        return key;
    }
};

//处理自定义类型
template<>
struct DefaultFuncer<string>
{
    size_t value = 0;
    size_t operator()(const string& str)
    {
        for (int i = 0; i < str.size(); i++)
        {
            value += str[i];
        }
        return value;
    }    
};


template<class K, template<class>class HashFuncer = DefaultFuncer>
class HashTable
{
public:
    HashTable()
        :_size(0)
        , _capacity(0)
        , _state(NULL)
        , _table(NULL)
    {}

       HashTable(size_t size)
            :_size(0)
            , _capacity(size)
            , _state(new State[size])
            , _table(new K[size])
        {
            for (int i = 0; i < _capacity; i++)//全部状态初始化成EMPTY
            {
                _state[i] = EMPTY;
            }
        }


        //线性探测计算出元素存放位置（假设不哈希冲突）
        int _HashFunc(const K& key)
        {
            HashFuncer<K> hf;
            return hf(key) % _capacity;
    
            //匿名对象调用operator()
            /*return HashFuncer<K>()(key) % _capacity;*/
        }
    
        void Swap(HashTable<K> tmp)
        {
            swap(_size, tmp._size);
            swap(_capacity, tmp._capacity);
            swap(_state, tmp._state);
            swap(_table, tmp._table);
        }
    
    
        void _CheckCapacity()
        {                
            HashTable<K> tmp(2*_capacity);
            for (int i = 0; i < _capacity; i++)
            {
                tmp.Insert(_table[i]);
            }
            Swap(tmp);
        }
        
    
        bool Insert(const K& key)
        {
            //静态哈希表
            /*if (_size == _capacity)
            {
                cout<<"HashTable is full!"<<endl;
                return false;
            }*/
    
            //动态哈希表
            //高效哈希表的载荷因子大概稳定在0.7-0.8较好
            if (10 * _size >= 7 * _capacity)
            {
                _CheckCapacity();
            }
    
            int index = _HashFunc(key);
        
            while (_state[index] == EXIST)
            {        
                index++;
                if (index == _capacity)
                {
                    index = 0;
                }
            }
    
            _table[index] = key;
            _state[index] = EXIST;
            _size++;
            return true;    
        }
    
    
        int Find(const K& key)
        {
            int index = _HashFunc(key);
            while (_state[index] == EXIST || _state[index]== DELETE)
            //while(_state[index] != EMPTY)    //空状态找不到，非空状态找得到
            {
                if (_table[index] == key && _state[index] == EXIST)
                {
                    return index;
                }
                ++index;
                if (index == _capacity)
                {
                    index = 0;
                }
            }
            return -1;    
        }
    
    
        bool Remove(const K& key)
        {
            int index = Find(key);
            if (index != -1)
            {
                _state[index] = DELETE;
                --_size;
                return true;
            }
            return false;
        }
    
    
        void PrintTable()
        {
            for (int i = 0; i < _capacity; i++)
            {
                if (_state[i] == EXIST )
                {
                    cout << i << "(EXIST):" << _table[i] << endl;
                }
                /*我将DELETE状态元素也打印出来，便于观察。
                而Insert处理时，DELETE状态下的位置可以插上新的元素*/
                else if (_state[i] == DELETE)
                {
                    cout << i << "(DELETE):" << _table[i] << endl;
                }
                else
                {
                    cout << i << "(EMPTY):" << _table[i] << endl;
                }
            }
        }

private:
        size_t _size;//实际存放元素个数
        size_t _capacity;//哈希表长度
        State* _state;
        K* _table;
};


//POD(基本类型)的测试用例
void TestHashTablePOD()
{
    HashTable<int> ht(10);
    ht.Insert(89);
    ht.Insert(18);
    ht.Insert(49);
    ht.Insert(58);
    ht.Insert(9);
    ht.PrintTable();

    int ret = ht.Find(89);
    cout << ret << endl; 

    ht.Remove(89);
    ht.PrintTable();

    ht.Remove(18);
    ht.PrintTable();
}


//自定义类型的测试用例
void TestHashTable()
{
    HashTable<string,DefaultFuncer> ht(10);
    ht.Insert("信息化");
    ht.Insert("时代");
    ht.Insert("电脑");
    ht.Insert("测试工程师");
    ht.PrintTable();

    int ret = ht.Find("测试工程师");
    cout << ret << endl;

    ht.Remove("电脑");
    ht.PrintTable();

    ht.Remove("时代");
    ht.PrintTable();
}


int main()
{
    TestHashTable();
    system("pause");
    return 0;
}

以上就是java数据结构中哈希表的线性探测算法是什么，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。