公司网站费怎么做分录,河北邯郸大风,建筑人才网官网96877,网站建设客户好评信哈希 一.unordered_map二.底层结构1.哈希概念2.解决哈希冲突1.闭散列2.开散列 在C98中#xff0c;STL提供了底层为红黑树结构的一系列关联式容器#xff0c;在查询时效率可达到 l o g 2 N log_2N log2N#xff0c;即最差情况下需要比较红黑树的高度次#xff0c;当树中的… 哈希 一.unordered_map二.底层结构1.哈希概念2.解决哈希冲突1.闭散列2.开散列 在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到 l o g 2 N log_2N log2N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同本文中只对unordered_map和unordered_set进行介绍。 一.unordered_map
unordered_map是存储key, value键值对的关联式容器其允许通过keys快速的索引到与其对应的value。在unordered_map中键值通常用于惟一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。在内部,unordered_map没有对kye, value按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。unordered_maps实现了直接访问操作符(operator[])它允许使用key作为参数直接访问value。它的迭代器至少是前向迭代器。它的使用几乎与map一致。
二.底层结构
1.哈希概念
复杂的说
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表)
简单的说 上述就是一种k,v的映射关系为了避免数组越界我们还会对K(铅笔的号数)进行取模(%capcity)。相信大家也能发现铅笔的号数肯定远远不止5个例如5号铅笔和10号铅笔都会储存在0号位置这就是下哈希冲突。 2.解决哈希冲突
1.闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。
第一种线性探测 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。 总的来说将数据放入hash表时如果该位置被占据就向后查找直到找到空位置进行插入。在查询数据时一直查询直到找到或者找到空位置或者原点时停止。基于查找时找到空位置时停止所以删除时就不能直接置空需要标记该位置已被删除。接下来还有一个难点就是扩容。 根据查找规则来看如果等hash表填满才扩容毫无疑问会发生很多冲突这是很低效的所以必须有一个扩容规则来判断何时扩容。 enum State
{EXIST,DELETE,EMPTY
};templateclass K,class V
struct HashData//创建hash表的类型
{pairK, V _kv;State _stateEMPTY;
};templateclass K,class V
class Hash
{
public:Hash(){_table.resize(10);//初始开10给空间}void insert(const pairK, V kv){//判断是否需要扩容if (n * 10 / _table.size() 7){//开一个新的表容量为原来二倍size_t newHash _table.size() * 2;HashK, VnewHT;newHT._table.resize(newHash);//将旧表的值插入到新表里for (size_t i 0; i _table.size(); i){if (_table[i]._state EXIST)newHT.insert(_table[i]._kv);}//交换新旧表_table.swap(newHT._table);}//线性探测size_t hashi kv.first % _table.size();//插入位置while (_table[hashi]._state EXIST)//判断应该插入的位置{hashi;hashi % _table.size();}_table[hashi]._state EXIST;_table[hashi]._kv kv;n;//有效长度加一}
private:vectorHashDataK, V_table;//创建hash表size_t n 0;//记录有效长度
};第二种二次探测 二次探测与线性探测基本一致只是线性探测在找空位时依次向后找而二次探测在找空位时一次走i的平方。 2.开散列
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链 接起来各链表的头结点存储在哈希表中。 接下来是扩容操作其实开散表即使不扩容也能正常使用但如果数据插入过多会导致桶越来越长最终变成长链表导致查找效率降低。所以我们需要引入负载因子来判断何时应该扩容负载因子计算看与闭散表一致。
整个扩容需要遍历所有链表把它们的指针都指向新链表就可以了。 这里需要补充一点因为我们的K值不一定都是int类型所以需要写仿函数来将它转成int这样才能对应数组下标。 又因为字符串是我们常用的数据类型所以我们可以将它进行一个特例化单独将字符串转化拎出来字符串转化规则是根据字符串哈希转化规则进行转化的不明白的可以自行百度。 接下来删除和查找都比较简单直接看完整源代码。
Hash.h
#includeiostream
#includevector
using namespace std;templateclass K
struct DefaultHashFunc//仿函数
{size_t operator()(const K key){return (size_t)key;}
};template
struct DefaultHashFuncstring//特例化
{size_t operator()(const string str){// BKDRsize_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};namespace open_adress
{enum State{EXIST,DELETE,EMPTY};templateclass K, class Vstruct HashData//创建hash表的类型{pairK, V _kv;State _state EMPTY;};templateclass K, class Vclass Hash{public:Hash(){_table.resize(10);//初始开10给空间}void insert(const pairK, V kv){//判断是否需要扩容if (n * 10 / _table.size() 7){//开一个新的表容量为原来二倍size_t newHash _table.size() * 2;HashK, VnewHT;newHT._table.resize(newHash);//将旧表的值插入到新表里for (size_t i 0; i _table.size(); i){if (_table[i]._state EXIST)newHT.insert(_table[i]._kv);}//交换新旧表_table.swap(newHT._table);}//线性探测size_t hashi kv.first % _table.size();//插入位置while (_table[hashi]._state EXIST)//判断应该插入的位置{hashi;hashi % _table.size();}_table[hashi]._state EXIST;_table[hashi]._kv kv;n;//有效长度加一}private:vectorHashDataK, V_table;//创建hash表size_t n 0;//记录有效长度};
}namespace hash_bucket
{templateclass K,class Vstruct HashData//创建节点{HashDataK, V* next;pairK, V_kv;HashData(const pairK,Vkv):next(nullptr),_kv(kv){}};templateclass K,class V,class HashFunc DefaultHashFuncKclass Hash{typedef HashDataK, V Node;public:Hash(){_table.resize(10,nullptr);}~Hash(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-next;delete cur;cur next;}_table[i] nullptr;}}HashFunc hf;bool Insert(const pairK, V kv){//如果重复插入返回falseif (Find(kv.first)){return false;}//扩容if (_n _table.size()){vectorNode*newTable;newTable.resize(_table.size() * 2, nullptr);//遍历所有节点for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){size_t hashi hf(cur-_kv.first) % newTable.size();cur-next newTable[hashi];newTable[hashi] cur;cur cur-next;}_table[i] nullptr;}_table.swap(newTable);}size_t hashi hf(kv.first) % _table.size();//头插Node*newNode new Node(kv);newNode-next _table[hashi];_table[hashi] newNode;_n;return true;}Node* Find(const Kkey){size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (cur-_kv.first key)return cur;cur cur-next;}return nullptr;}bool Erase(const K key){size_t hashi hf(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){if (prev nullptr){_table[hashi] cur-next;}else{prev-next cur-next;}delete cur;return true;}prev cur;cur cur-next;}--_n;return false;}void Print(){for (size_t i 0; i _table.size(); i){printf([%d]-, i);Node* cur _table[i];while (cur){cout cur-_kv.first : cur-_kv.second -;cur cur-next;}printf(NULL\n);}cout endl;}private:vectorNode*_table;size_t _n 0;};}test.cpp
int main()
{hash_bucket::Hashint, int ht;int a[] { 1,111,4,7,15,25,44,9 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Print();ht.Insert(make_pair(14, 14));ht.Print();ht.Insert(make_pair(24, 24));ht.Print();ht.Insert(make_pair(34, 34));ht.Print();ht.Erase(44);ht.Erase(4);ht.Erase(24);ht.Print();hash_bucket::Hashstring, string dict;dict.Insert(make_pair(sort, 排序));dict.Insert(make_pair(left, xxx));dict.Insert(make_pair(insert, 插入));dict.Insert(make_pair(string, 字符串));dict.Insert(make_pair(bucket, 桶));auto dret dict.Find(left);//dret-_kv.first xx;dret-_kv.second 左边;dict.Print();return 0;
}
