【数据结构】哈希
我们经常会在一堆数据中搜索我们需要的数据元素,用于搜索的数据集合称为搜索结构。常见的查找方法有:从前往后依次遍历,二分查找,平衡二叉树,B树等。今天,我们看一种更高效的查找方法。 哈希查找在线性表,二叉搜索树,AVL树等结构中,元素在存储结构中的位置与元素的关键码之间不存在直接的对应关系。我们知道在数据结构中搜索一个元素需要进行一系列的关键码比较,因此搜索的效率取决于搜索过程中比较的次数。如果我们可以不比较或者减少比较次数,那么效率就会大大提高了。 我们可以建立一个确定的函数关系:addr=Hash(key)
哈希冲突对于哈希冲突,我们肯定是要尽量减少的,因此哈希函数就至关重要了,我们要求哈希函数计算出来的地址能均匀分布在整个空间中,同时应该比较简单。常见的哈希函数方法:
虽然这些方法可以减少哈希冲突,但终究还是避免不了,因此,我们还是要选择好的解决冲突溢出的方法:
不管使用哪种方法,当表中的元素较多的时候,就越容易发生冲突,因此,我们定义一个载荷因子:载荷因子=填入表中的元素个数/散列表的长度;当载荷因子达到一定数时,就需要对哈希表增大容量了。 开散列法:又叫链地址法,在这一篇博客中介绍。 闭散列: 开散列: //静态实现
#pragma once
#include <iostream>
using namespace std;
#define MAX_SIZE 10
typedef enum State { EXIST,DELETE,EMPTY };
template <class K>
struct Elem
{
K _key;
State _state;
};
template <class K,bool IsLine = true>
class HashTable
{
public:
HashTable()
: _size(0)
{
for (size_t i = 0; i < MAX_SIZE; i++)
_hashTable[i]._state = EMPTY;
}
bool Insert(const K& key)
{
if (_size * 10 / MAX_SIZE > 7)
return false;
size_t addr = HashFunc(key);
size_t i = 1;
while (_hashTable[addr]._state != EMPTY)
{
if (_hashTable[addr]._state == EXIST && key == _hashTable[addr]._key)
return false;
if (IsLine)
LineCheck(addr);//线性探测
else
SecondCheck(addr,i++);//二次探查
}
_hashTable[addr]._key = key;
_hashTable[addr]._state = EXIST;
_size++;
return true;
}
bool Delete(const K& key)
{
int ret = Find(key);
if (ret == -1)
return false;//不存在
_size--;
_hashTable[ret]._state = DELETE;
return true;
}
int Find(const K& key)
{
size_t addr = HashFunc(key);
size_t i = 1;
while (_hashTable[addr]._state != EMPTY)
{
if (_hashTable[addr]._state == EXIST && _hashTable[addr]._key == key)
return addr;
if (IsLine)
LineCheck(addr);
else
SecondCheck(addr,i++);
}
return -1;
}
size_t Size()const
{
return _size;
}
bool Empty()const
{
return 0 == _size;
}
private:
size_t HashFunc(const K& key)
{
return key % MAX_SIZE;
}
void LineCheck(size_t& addr)
{
++addr;
if (addr >= MAX_SIZE)
addr = 0;
}
void SecondCheck(size_t& addr,size_t i)
{
addr = addr + ((i << 1) + 1);
if (addr >= MAX_SIZE)
addr %= MAX_SIZE;
}
private:
Elem<K> _hashTable[MAX_SIZE];
size_t _size;
};
void test()
{
int arr[] = { 12,22,33,9,29,55 };
HashTable<int> ht;
if (ht.Empty())
{
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
ht.Insert(arr[i]);
}
cout << ht.Size() << endl;
ht.Delete(22);
ht.Insert(33);
cout << ht.Size() << endl;
}
}
上面的代码写的是一个静态的哈希表,用数组创建,它有以下三个缺陷:
这三个问题怎么解决呢?
以下是动态的代码实现: #pragma once
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 获得素数
const int _PrimeSize = 28;
static const unsigned long _PrimeList[_PrimeSize] =
{
53ul,97ul,193ul,389ul,769ul,1543ul,3079ul,6151ul,12289ul,24593ul,49157ul,98317ul,196613ul,393241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,201326611ul,402653189ul,805306457ul,1610612741ul,3221225473ul,4294967291ul
};
size_t GetNextPrime(size_t num)
{
for (size_t i = 0; i < _PrimeSize; i++)
{
if (_PrimeList[i]>num)
return _PrimeList[i];
}
return _PrimeList[_PrimeSize - 1];
}
//字符串转整型
static size_t BKDRHash(const char * str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
size_t ret = (hash & 0x7FFFFFFF);
return ret;
}
template <class K>
class KeyToIntDef
{
public:
size_t operator()(const K& key)
{
return key;
}
};
class StringToInt
{
public:
size_t operator()(const string& key)
{
return BKDRHash(key.c_str());
}
};
typedef enum State { EXIST,EMPTY };
template <class K>
struct Elem
{
K _key;
State _state;
};
template <class K,class KeyToInt,bool IsLine = true>
class HashTable
{
public:
HashTable(size_t capacity = 4)
{
capacity = GetNextPrime(capacity);
_hashTable.resize(capacity);
for (size_t i = 0; i < capacity; i++)
_hashTable[i]._state = EMPTY;
_size = 0;
_capacity = capacity;
}
bool Insert(const K& key)
{
CheckCapacity();
size_t addr = HashFunc(key);
size_t i = 1;
while (_hashTable[addr]._state != EMPTY)
{
if (_hashTable[addr]._key == key && _hashTable[addr]._state == EXIST)
return false;
if (IsLine)
LineCheck(addr);
else
SecondCheck(addr,i++);
}
_hashTable[addr]._state = EXIST;
_hashTable[addr]._key = key;
_size++;
return true;
}
bool Delete(const K& key)
{
int ret = Find(key);
if (ret == -1)
return false;//不存在
_size--;
_hashTable[ret]._state = DELETE;
return true;
}
int Find(const K& key)
{
size_t addr = HashFunc(key);
size_t i = 1;
while (_hashTable[addr]._state != EMPTY)
{
if (_hashTable[addr]._state == EXIST && _hashTable[addr]._key == key)
return addr;
if (IsLine)
LineCheck(addr);
else
SecondCheck(addr,i++);
}
return -1;
}
size_t Size()const
{
return _size;
}
bool Empty()const
{
return 0 == _size;
}
~HashTable()
{
_hashTable.~vector();
_size = 0;
_capacity = 0;
}
private:
void CheckCapacity()
{
if (_size * 10 / _capacity >= 7)
{
size_t newCapacity = GetNextPrime(_capacity);
HashTable<K,KeyToInt> newHt(newCapacity);
for (size_t i = 0; i < _capacity; i++)
{
if (_hashTable[i]._state == EXIST)
newHt.Insert(_hashTable[i]._key);
}
_capacity = newCapacity;
Swap(newHt);
}
}
void Swap(HashTable<K,KeyToInt>& ht)
{
swap(_hashTable,ht._hashTable);
swap(_capacity,ht._capacity);
swap(_size,ht._size);
}
size_t HashFunc(const K& key)
{
return KeyToInt()(key) % _capacity;
}
void LineCheck(size_t& addr)
{
++addr;
if (addr >= _capacity)
addr = 0;
}
void SecondCheck(size_t& addr,size_t i)
{
addr = addr + ((i << 1) + 1);
if (addr >= _capacity)
addr %= _capacity;
}
private:
vector<Elem<K>> _hashTable;
size_t _size;
size_t _capacity;
};
void test()
{
HashTable<string,StringToInt> ht1;
ht1.Insert("111");
ht1.Insert("222");
ht1.Insert("333");
ht1.Insert("abc");
ht1.Insert("你好");
cout << ht1.Size() << endl;
if (ht1.Find("111") != -1)
cout << "找到了" << endl;
else
cout << "没有找到" << endl;
ht1.Delete("333");
cout << ht1.Size() << endl;
} (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |