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,//该位置存在元素 }; //处理基本类型 template struct 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; } }; template 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 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数据结构中哈希表的线性探测算法是什么,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注创新互联行业资讯频道。
本文标题:java数据结构中哈希表的线性探测算法是什么
文章转载:http://myzitong.com/article/jhsocs.html