哈希表/散列表
哈希表/散列表,是根据关键字(key)直接访问在内存存储位置的数据结构。
创新互联公司是一家专业提供松北企业网站建设,专注与网站设计制作、网站设计、H5响应式网站、小程序制作等业务。10年已为松北众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。
构造哈希表的常用方法:
直接地址法---取关键字的某个线性函数为散列地址,Hash(Key) = Key或Hash(key) = A*Key + B,
A,B为常数。
除留余数法---取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。
Hash(key) = key % p。
若采用直接地址法(Hash(Key) = Key)存在一定的缺陷。
当Key值特别大时,而Key之前的数很少,就会造成空间浪费。大多时候采取除留余数法。
哈希冲突/哈希碰撞
不同的Key值经过哈希函数Hash(Key)处理以后可能产生相同的哈希地址,我们称这种情况为哈希冲突。任何的散列函数都不能避免产生冲突。
散列表的载荷因子定义为a = 填入表中元素的个数/散列表的长度
载荷因子越大,冲突的可能性就越大。
解决冲突的办法:
(1)线性探测
(2)二次探测
#pragma once #include#include using namespace std; enum State { EMPTY, DELETE, EXITS, }; //以key形式实现线性探测 template class HashTable { public: HashTable(T capacity = 10) :_tables(new T[capacity]) ,_states(new State[capacity]) ,_capacity(capacity) ,_size(0) { for(size_t i=0;i < _capacity;++i) { _states[i] = EMPTY; } } ~HashTable() { delete[] _tables; delete[] _states; _tables = NULL; _states = NULL; } HashTable(const HashTable & ht) //拷贝构造 { _tables = new T[ht._capacity]; _states = new State[ht._capacity]; for(size_t i=0;i & operator=(const HashTable & ht) //赋值操作符重载 //{ // if(this != &ht) // { // delete[] _tables; // delete[] _states; // _tables = new T[ht._capacity]; // _states = new State[ht._capacity]; // for(size_t i=0;i & operator=(HashTable ht) //赋值操作符重载 { this->Swap(ht); return *this; } public: bool Insert(const T& key) //插入 { _CheckCapacity(); size_t index = HashFunc(key); while(_states[index] == EXITS) { if(_tables[index] == key) //冗余 { return false; } ++index; if(index == _capacity) //到达哈希表尾部 { index = 0; } } _tables[index] = key; _states[index] = EXITS; ++_size; return true; } bool Find(const T& key) //查找 { size_t index = HashFunc(key); size_t start = index; while(_states[index] == EXITS) { if(_tables[index] == key) { return true; } ++index; if(index == _capacity) { index = 0; } if(start == index) //哈希表查完 { return false; } } return false; } bool Remove(const T& key) //删除 { size_t index = HashFunc(key); size_t start = index; while(_states[index] == EXITS) { if(_tables[index] == key) { _states[index] = DELETE; return true; } ++index; if(index == _capacity) //到达哈希表的尾部 { index = 0; } if(start == index) //哈希表查完 { return false; } } return false; } public: size_t HashFunc(const T& key) //哈希函数 { return key%10; } void _CheckCapacity() //检查容量 { if(_size*10 % _capacity == 7) //载荷因子 { HashTable tmp(2*_capacity); for(size_t i=0;i<_capacity;++i) { if(_states[i] == EXITS) { tmp.Insert(_tables[i]); } } Swap(tmp); } } void Swap(HashTable & ht) { swap(_tables,ht._tables); swap(_states,ht._states); swap(_size,ht._size); swap(_capacity,ht._capacity); } void Print() { for(size_t i=0;i<_capacity;++i) { cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<" "; } cout< //class HashTableSecond //{ //public: // HashTableSecond(T capacity = 10) // :_tables(new T[capacity]) // ,_states(new State[capacity]) // ,_capacity(capacity) // ,_size(0) // { // for(size_t i=0;i < _capacity;++i) // { // _states[i] = EMPTY; // } // } // // ~HashTableSecond() // { // delete[] _tables; // delete[] _states; // _tables = NULL; // _states = NULL; // } // // HashTableSecond(const HashTableSecond& ht) //拷贝构造 // { // _tables = new T[ht._capacity]; // _states = new State[ht._capacity]; // for(size_t i=0;i tmp(2*_capacity); // for(size_t i=0;i<_capacity;++i) // { // if(_states[i] == EXITS) // { // tmp.Insert(_tables[i]); // } // } // Swap(tmp); // } // } // // void Swap(HashTableSecond & ht) // { // swap(_tables,ht._tables); // swap(_states,ht._states); // swap(_size,ht._size); // swap(_capacity,ht._capacity); // } // // void Print() // { // for(size_t i=0;i<_capacity;++i) // { // cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<" "; // } // cout< struct HashTableNode //节点 { T key; K value; }; template struct __HashFunc //重载() { size_t operator()(const T& key) { return key; } }; template<> struct __HashFunc //特化 { size_t operator()(const string& key) { size_t hash = 0; for(size_t i=0;i > class HashTableSecond { public: HashTableSecond(size_t capacity = 10) :_tables(new HashTableNode [capacity]) ,_states(new State[capacity]) ,_capacity(capacity) ,_size(0) { for(size_t i=0;i < _capacity;++i) { _states[i] = EMPTY; } } ~HashTableSecond() { delete[] _tables; delete[] _states; _tables = NULL; _states = NULL; } public: bool Insert(const T& key,const K& value) //插入 { _CheckCapacity(); size_t start = __HashFunc(key); size_t index = start; size_t i = 1; while(_states[index] == EXITS) { if(_tables[index].key == key) { return false; } index = start + i * i; ++i; index %= _capacity; } _tables[index].key = key; _tables[index].value = value; _states[index] = EXITS; ++_size; return true; } HashTableNode * Find(const T& key) //查找 { size_t start = __HashFunc(key); size_t index = start; size_t i = 1; while(_states[index] == EXITS) { if(_tables[index].key == key) { return &(_tables[index]); } index = start + i * i; ++i; index %= _capacity; } return NULL; } bool Remove(const T& key) //删除 { size_t start = __HashFunc(key); size_t index = start; size_t i = 1; while(_states[index] == EXITS) { if(_tables[index].key == key) { _states[index] = DELETE; return true; } index = start + i * i; ++i; } return false; } public: size_t __HashFunc(const T& key) //哈希函数 { HashFunc hfun; return hfun(key)%_capacity; } void _CheckCapacity() //检测容量 { if(_size*10 % _capacity == 7) { HashTableSecond tmp(2*_capacity); for(size_t i=0;i<_capacity;++i) { if(_states[i] == EXITS) { tmp.Insert(_tables[i].key,_tables[i].value); } } Swap(tmp); } } void Swap(HashTableSecond & ht) { swap(_tables,ht._tables); swap(_states,ht._states); swap(_size,ht._size); swap(_capacity,ht._capacity); } void Print() { for(size_t i=0;i<_capacity;++i) { cout<<"["<<_tables[i].key<<","<<_tables[i].value<<"]"<<" "; } cout< * _tables; //哈希表 State* _states; //状态表 size_t _size; //数据的个数 size_t _capacity; //容量 };
分享标题:哈希表/散列表
URL链接:http://scyanting.com/article/jgdgjg.html