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#includeusing namespace std;#include//线性探测的特化处理可以处理自定义类型的数据enum State{   EMPTY,//该位置未存放元素   DELETE,//该位置元素已被删除   EXIST,//该位置存在元素};//处理基本类型templatestruct DefaultFuncer{    size_t operator()(const K& key)    {        return key;    }};//处理自定义类型template<>struct DefaultFuncer{    size_t value = 0;    size_t operator()(const string& str)    {        for (int i = 0; i < str.size(); i++)        {            value += str[i];        }        return value;    }    };templateclass 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 hf;            return hf(key) % _capacity;                //匿名对象调用operator()            /*return HashFuncer()(key) % _capacity;*/        }            void Swap(HashTable tmp)        {            swap(_size, tmp._size);            swap(_capacity, tmp._capacity);            swap(_state, tmp._state);            swap(_table, tmp._table);        }                void _CheckCapacity()        {                            HashTable 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!"<= 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 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 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数据结构中哈希表的线性探测算法是什么，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注行业资讯频道。