哈希之开散列,闭散列
先从数据查找开始说起吧,在线性结构,树形结构当中查找一个元素必须经过多次和一些元素进行比较,然后通过比较,查找到对应元素,这种方法多多少少,时间复杂度都是比较高的。
有没有一种方法时间复杂度,仅仅O(1)尼,那么我们就要构造一种存储结构,通过某种函数是之元素与它对应的关键码之间能建立一一映射的关系,那么自然通过之中一一映射的关系,我们就可以很快的找到我们需要的元素。
所以进入哈希这个这题首先我们需要一个我们下标,这个下表在哈希当中
我们就称之为哈希地址。而这个地址我们可以通过哈希函数的一些数学公式计算存储下标,通过哈希函数在对应哈希地址里面放对应的函数我们就叫之为哈希表。
例如:哈希函数设置为hash(key) = key % capacity
哈希冲突:哎,这些副都带的知识点介绍起来太麻烦了,就是通过哈希函数计算粗来的数组下标有两个数同时满足这个条件,同时都可以放入这个数组下标。
这些计算哈希地址的哈希函数就不多说了,反正蛮多的,说复杂的也有简单的也有
来看解决哈希冲突的常见的两种方式吧,闭散列,开散列。
闭散列:发生哈希冲突时候,当哈希表当中还有位置的时候,那么把这个数据放入哈希冲突的下一个位置,而如何探测空位置就需要线性探测。
-
插入
-通过哈希函数获取哈希函数在哈希表中的位置。 -
删除
-采用闭散列处理哈希冲突问题,不能随便物理删除哈希表当中已有元素,比如如果删除4,44查找起来就会受影响,一次线性探测删除一个元素时候还需要对删除位置进行一个新的标志。
画一张图吧,上面例子里面当中的4,44就在例子当中的哈希结构当中。
我们来看一下,发生哈希冲突的时候,我们线性探测怎么实现。
template<class K, class V>
class HashTable {
struct Elem
{
pair<K, V> _val;
State _state;
};
public:
HashTable(size_t capacity = 3)
: _ht(capacity)
, _size(0)
{
for (size_t i = 0; i < capacity; ++i)
_ht[i]._state = EMPTY;
}
bool Insert(const pair<K, V>& val)
{
// 检测哈希表底层空间是否充足
// _CheckCapacity();
size_t hashAddr = HashFunc(key);
// size_t startAddr = hashAddr;
while(_ht[hashAddr]._state != EMPTY)
{
if(_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == key)
return false;
hashAddr++;
// hashAddr %= _ht.capacity();
if(hashAddr == _ht.capacity())
hashAddr = 0;
if(hashAddr == startAddr)
return false;
*/
}
// 插入元素
_ht[hashAddr]._state = EXIST;
_ht[hashAddr]._val = val;
_size++;
return true;
}
int Find(const K& key)
{
size_t hashAddr = HashFunc(key);
while(_ht[hashAddr]._state != EMPTY)
{
if(_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == key)
return hashAddr;
hashAddr++;
}
return hashAddr;
}
bool Erase(const K& key)
{
int index = Find(key);
if (-1 != index)
{
_ht[index]._state = DELETE;
_size++;
return true;
}
return false;
}
size_t Size()const
{
return _size;
}
bool Empty() const
{
return 0 == _size;
}
void Swap(HashTable<K, V, HF>& ht)
{
swap(_ht, ht._ht);
swap(_size, ht._size);
}
private:
size_t HashFunc(const K& key)
{
return key % _ht.capacity();
}
private:
vector<Elem> _ht;
size_t _size;
};
** 转一圈也没有找到,注意:动态哈希表,该种情况可以不用考虑,哈希表中元素个数到达 一定的数量,哈希冲突概率会增大,需要扩容来降低哈希冲突,因此哈希表中元素是不会存满的 **
线性探测优点:实现简单
线性探测缺点:一旦发生哈希冲突,所有的元素连接在一起容易产生数据堆积,即不同数据占据可利用的空间位置,使得寻找某个关键码的位置需要多次比较,导致搜索效率降低。
二次线性探测
线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就 是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: = ( + )% m, 或者: = ( - )% m。其中:i = 1,2,3…, 是通过散列函数Hash(x)对元素的关键码 key 进行 计算得到的位置,m是表的大小。 对于2.1中如果要插入44,产生冲突,使用解决后的情况为:
注意:当表的长度为质数的且表装载的表项一定能够插入,而且任何一个位置都不会被线性探测两次,因此主要有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入是必须确保装载因子a不超过0.5,如果超出必须考虑增容。
因此闭散列最大的缺点就是空间利用率比较低,这也是哈希的缺陷。
开散列:首先有一个关键码集合,用散列函数计算散列地址,具有相同地址的关键码归于同一个子集,每个子集当中和称为一个桶,每个同当中的元素的元素通过一个单链表链接起来,个链表当中的头节点存在哈希表当中。
从图中可以看出开散列当中每个桶当中的元素都是发生哈希冲突的元素。
template<class V, class HF = DefHashF<T> >
class HashBucket {
typedef HashBucketNode<V> Node;
typedef Node* PNode;
public:
HashBucket(size_t capacity = 3)
: _size(0)
{
_ht.resize(GetNextPrime(capacity), nullptr);
}
// 哈希桶中的元素不能重复
PNode* Insert(const V& data)
{
// 确认是否需要扩容。。。
// _CheckCapacity();
// 1. 计算元素所在的桶号
size_t bucketNo = HashFunc(data);
// 2. 检测该元素是否在桶中
PNode pCur = _ht[bucketNo];
while(pCur)
{
if(pCur->_data == data)
return pCur;
pCur = pCur->_pNext;
}
// 3. 插入新元素
pCur = new Node(data);
// 采用头插法插入,效率高 比特科技
pCur->_pNext = _ht[bucketNo];
_ht[bucketNo] = pCur;
_size++;
return pCur;
}
// 删除哈希桶中为data的元素(data不会重复),返回删除元素的下一个节点
PNode* Erase(const V& data)
{
size_t bucketNo = HashFunc(data);
PNode pCur = _ht[bucketNo];
PNode pPrev = nullptr;
pNode pRet = nullptr;
while(pCur)
{
if(pCur->_data == data)
{
// 头删
if(pCur == _ht[bucketNo])
{
_ht[bucketNo] = pCur->_pNext;
}
else
{
pPrev->_pNext = pCur->_pNext;
}
pRet = pCur->_pNext;
delete pCur;
_size--;
return pRet;
}
}
return nullptr;
}
// 查找data是否在哈希桶中
PNode* Find(const V& data)
{
size_t bucketNo = HashFunc(data);
PNode pCur = _ht[bucketNo];
while(pCur)
{
if(pCur->_data == data)
return pCur;
pCur = pCur->_pNext;
}
return nullptr;
}
size_t Size()const
{
return _size;
}
bool Empty()const
{
return 0 == _size;
}
void Clear()
{
for (size_t bucketNo = 0; bucketNo < _ht.capacity(); ++bucketNo)
{
PNode pCur = _ht[bucketNo];
while (pCur)
{
_ht[bucketNo] = pCur->_pNext;
delete pCur;
pCur = _ht[bucketNo];
}
}
_size = 0;
}
bool BucketCount()const
{
return _ht.capacity();
}
void Swap(HashBucket<V, HF>& ht)
{
swap(_ht, ht._ht);
swap(_size, ht._size);
}
~HashBucket()
{
Clear();
}
private:
size_t HashFunc(const V& data)
{
return HF()(data) % _ht.BucketCount();
}
private:
vector<PNode*> _ht;
size_t _size; // 哈希表中有效元素的个数
};
开散列与闭散列比较:
应用链地址处理溢出,需要增设链接指针,似乎增加存储开销。事实上:由于开地址必须保存大量的空闲空间一保证搜索的效率,如二次探测法要求装载因子a <= 0.7,而表项所占空间又比指针的的多,所以使用链地址法反而比开地址发节省存储空间。