网站开发和软件开发工作,怎么做网络销售的网站,河南城乡建设网站,怀柔成都网站建设哈希表概念
哈希表可以简单理解为#xff1a;把数据转化为数组的下标#xff0c;然后用数组的下标对应的值来表示这个数据。如果我们想要搜索这个数据#xff0c;直接计算出这个数据的下标#xff0c;然后就可以直接访问数组对应的位置#xff0c;所以可以用O(1)的复杂度…哈希表概念
哈希表可以简单理解为把数据转化为数组的下标然后用数组的下标对应的值来表示这个数据。如果我们想要搜索这个数据直接计算出这个数据的下标然后就可以直接访问数组对应的位置所以可以用O(1)的复杂度直接找到数据。
其中这个数据对应的数字叫做关键码(Key)这个把关键码转化为下标的规则叫做哈希函数(Hash)。
要注意的是有一些数据并不是整型比如字符串对象等等。对于这种数据我们要先用一套规则把它们转化为整数关键码然后再通过哈希函数映射为数组下标。 哈希函数
哈希函数原则
哈希函数转换后生成的地址下标必须小于哈希表的最大地址下标哈希函数计算出来的地址下标必须均匀地分布哈希函数尽可能简单
直接定址法 取关键字的某个线性函数为哈希表的地址 除留余数法 假设哈希表的地址数目为m取Key对m取模后得到的值作为下标 闭散列 - 开放定址法
闭散列也叫做开放定址法当发生哈希冲突时如果哈希表没有被装满说明哈希表中还有空位置那么我们可以把发生冲突的数据放到下一个空位置去。
基本结构
首先我们需要一个枚举来标识哈希表的不同状态
enum State
{EMPTY,EXIST,DELETE
};EMPTY空节点EXIST数值存在DELETE数值被删除 哈希表的基本结构
enum State
{EMPTY,EXIST,DELETE
};templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY;//标记状态
};templateclass K, class V
class HashTable
{
public:HashTable(size_t size 10){_tables.resize(size);}private:vectorHashDataK, V _tables;//哈希表size_t _n 0;//元素个数
};HashTable构造函数
HashTable(size_t size 10)
{_tables.resize(size);
} 查找
想要在哈希表中查找数据无非就遵顼以下规则 通过哈希函数计算出数据对应的地址 去地址处查找如果地址处不是目标值往后继续查找 遇到EMPTY还没有找到说明数据不存在哈希表中 遇到DELETE和EXIST继续往后查找 代码如下
HashDataK, V* Find(const K key)
{size_t hashi key % _tables.size();while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._kv.first key _tables[hashi]._state EXIST)return _tables[hashi];hashi;hashi % _tables.size();}return nullptr;
}但是当前的代码存在一个问题哈希表作用于泛型key % _tables.size()有可能是违法的行为因为key可能不是一个数字。
对此我们可以在模板中多加一个仿函数的参数用户可以在仿函数中自定义数据 - 整型的转换规则然后我们在对这个整型使用除留余数法获取地址。
在那之前我们可以先写一个仿函数用于处理整型 - 整型的转化
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};在STL中整型- 整型转化的函数被写为了一个模板而这个string - 整型被写为了一个模板特化
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s)//把字符串的每一个字符ASCII码值加起来{hash e;hash * 131; // 31, 131313(任意由13间断排列的数字)}return hash;}
};我们将这个HashFuncK仿函数作为哈希表的第三个模板参数的默认值
templateclass K, class V, class Hash HashFuncK
class HashTable
{};
通过仿函数来统一获得整型再进行除留余数操作
Hash hs;
size_t hashi hs(key) % _tables.size(); 插入
插入的基本逻辑如下 先通过Find接口查找目标值在不在哈希表中如果目标值已经存在返回flse表示插入失败通过哈希函数计算出目标值对应的下标向下标中插入数据如果下标对应的位置已经有数据往后查找直到某一个位置为EMPTY或者DELETE.如果下标对应的位置没有数据直接插入插入后把对应位置的状态转化为EXIST 代码如下
bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;Hash hs;//仿函数实例化出的对象size_t hashi hs(kv.first) % _tables.size();//获得目标值对应的下标while (_tables[hashi]._state EXIST)//往后查找合适的位置插入{hashi;hashi % _tables.size();}_tables[hashi]._kv kv;//插入_tables[hashi]._state EXIST;//改变状态_n;//哈希表中的元素个数1return true;
}当这个哈希表越满我们查找数据的效率就越低甚至说如果查找一个不存在的数据我们可能要用O(N)的复杂度遍历整个哈希表.因此我们因该把哈希表的负载率控制在一定值当超过一定值我们就要进行扩容操作。
if ((double)_n / _tables.size() 0.7)
{size_t newSize _tables.size() * 2;HashTableK, V, Hash newHT(newSize);for (auto e : _tables){if (e._state EXIST)newHT.Insert(e._kv);}_tables.swap(newHT._tables);
}插入总代码
bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;if ((double)_n / _tables.size() 0.7){size_t newSize _tables.size() * 2;HashTableK, V, Hash newHT(newSize);for (auto e : _tables){if (e._state EXIST)newHT.Insert(e._kv);}_tables.swap(newHT._tables);}Hash hs;size_t hashi hs(kv.first) % _tables.size();while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;
}删除 先通过Find接口找到要删除的值 如果没找到返回false表示删除失败如果找到把对应节点的状态改为DELETE 最后再把哈希表的_n - 1表示存在的节点数少了一个。 代码如下
bool Erase(const K key)
{HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;_n--;return true;}return false;
}总代码展示
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s)//把字符串的每一个字符ASCII码值加起来{hash e;hash * 131; // 31, 131313(任意由13间断排列的数字)}return hash;}
};enum State
{EMPTY,EXIST,DELETE
};templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY;//标记状态
};templateclass K, class V, class Hash HashFuncK
class HashTable
{
public:HashTable(size_t size 10){_tables.resize(size);}HashDataK, V* Find(const K key){Hash hs;size_t hashi hs(key) % _tables.size();while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._kv.first key _tables[hashi]._state EXIST)return _tables[hashi];hashi;hashi % _tables.size();}return nullptr;}bool Insert(const pairK, V kv){if (Find(kv.first))return false;if ((double)_n / _tables.size() 0.7){size_t newSize _tables.size() * 2;HashTableK, V, Hash newHT(newSize);for (auto e : _tables){if (e._state EXIST)newHT.Insert(e._kv);}_tables.swap(newHT._tables);}Hash hs;size_t hashi hs(kv.first) % _tables.size();while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;_n--;return true;}return false;}private:vectorHashDataK, V _tables;size_t _n 0;//元素个数
};开散列 - 哈希桶
在STL库中采用的是更加优秀的开散列方案。
哈希表的数组vector中不再直接存储数据而是存储一个链表的指针。当一个数值映射到对应的下标后就插入到这个链表中。其中每一个链表称为一个哈希桶每个哈希桶中存放着哈希冲突的元素. 基本结构
对于每一个节点其要存储当前节点的值也要存储下一个节点的指针基本结构如下
templateclass K, class V
struct HashNode
{HashNodeK, V* _next;pairK, V _kv;HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}
};哈希表
templateclass K, class V, class Hash HashFuncK
class HashTable
{typedef HashNodeK, V Node;
public:HashTable(size_t size 10){_tables.resize(size);}private:vectorNode* _tables; //链表指针数组size_t _n 0;//元素个数
};析构函数防止内存泄漏
~HashTable()
{for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}
}查找
查找的基本逻辑如下 先通过哈希函数计算出数据对应的下标通过下标找到对应的链表遍历链表找数据:如果某个节点的数据匹配上了返回该节点指针,如果遍历到了nullptr返回空指针表示没找到 代码如下
Node* Find(const K key)
{Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key)return cur;cur cur-_next;}return nullptr;
}插入
插入的基本逻辑如下 先通过Find接口查找目标值在不在哈希表中如果目标值已经存在返回flse表示插入失败通过哈希函数计算出目标值对应的下标向下标中插入数据 代码如下
bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;Hash hs;size_t hashi hs(kv.first) % _tables.size();//计算下标Node* newNode new Node(kv);//创建节点newNode-_next _tables[hashi];//头插_tables[hashi] newNode;_n;//更新元素个数return true;
}关于扩容:如果我们单纯的进行插入就要把原先的所有节点释放掉再创建新的节点。这样会浪费很多时间。我们最好把原先创建的节点利用起来因此我们要重写一个逻辑把原先的节点进行迁移。
if (_n _tables.size())
{vectorNode* newTables(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi hs(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr; //防止移交的节点被析构}_tables.swap(newTables);
}删除
删除逻辑 通过哈希函数计算出对应的下标到对应的哈希桶中查找目标值 如果找到删除对应的节点如果没找到返回false表示删除失败_n - 1表示删除了一个元素 代码如下
bool Erase(const K key)
{Hash hs;size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){if (prev)prev-_next cur-_next;else_tables[hashi] cur-_next;delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;
}代码展示
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s)//把字符串的每一个字符ASCII码值加起来{hash e;hash * 131; // 31, 131313(任意由13间断排列的数字)}return hash;}
};templateclass K, class V
struct HashNode
{HashNodeK, V* _next;pairK, V _kv;HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}
};templateclass K, class V, class Hash HashFuncK
class HashTable
{typedef HashNodeK, V Node;
public:HashTable(size_t size 10){_tables.resize(size);}~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}Node* Find(const K key){Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key)return cur;cur cur-_next;}return nullptr;}bool Insert(const pairK, V kv){if (Find(kv.first))return false;Hash hs;//哈希桶情况下负载因子到1才扩容if (_n _tables.size()){vectorNode* newTables(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi hs(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr; //防止移交的节点被析构}_tables.swap(newTables);}size_t hashi hs(kv.first) % _tables.size();Node* newNode new Node(kv);newNode-_next _tables[hashi];_tables[hashi] newNode;_n;return true;}bool Erase(const K key){Hash hs;size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){if (prev)prev-_next cur-_next;else_tables[hashi] cur-_next;delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;}private:vectorNode* _tables; //链表指针数组size_t _n 0;//元素个数
};
