长沙本土网站制作公司,西安建设工程信息网平台变更,软件开发工程师证书有用吗,国学底蕴的公司名字目录
链地址法Separate Chaining——哈希桶的模拟实现
超大重点分析#xff1a;
两种方法对比 由于在上次的哈希表的底层实现(1)---C版已经详细的阐述了相关的结构和原理#xff0c;哈希表的实现方法主要分为链地址法和开放定址法。开放定址法上次已经实现过了#xff0c…目录
链地址法Separate Chaining——哈希桶的模拟实现
超大重点分析
两种方法对比 由于在上次的哈希表的底层实现(1)---C版已经详细的阐述了相关的结构和原理哈希表的实现方法主要分为链地址法和开放定址法。开放定址法上次已经实现过了这次我们实现一下链地址法。
链地址法Separate Chaining——哈希桶的模拟实现 哈希桶的结构和链表是完全一样的我们这边选择在每个vector里面装入单链表就可以了比较简单嘛所以每个结点和成员都是指针。
#includeiostream #includevector using namespace std;
templateclass K struct Hashfunc//仿函数 { int operator()(const K key) { return (int)key; } };
struct Hashfuncstring//结构体名字必须一致才省略模板 { int operator()(const string key) { int hashi 0; for (auto e : key) { hashi hashi * 31; hashi hashi e; } return hashi; } }; templateclass K, class V struct Hashnode { pairK, V _kv; HashnodeK, V* _next; Hashnode(const pairK, V kv) :_kv(kv) ,_next(nullptr) {} };
templateclass K, class V, class hash HashfuncK class Hashtable { typedef HashnodeK, V node; public: Hashtable() { _tables.resize(10, nullptr);//先初始化存有10个空指针的数组 } ~Hashtable()//需要自己写析构函数的 { for (int i 0; i _tables.size(); i) { node* cur _tables[i]; while (cur) { node* next cur-_next; delete cur; cur next; } _tables[i] nullptr; } } bool Insert(const pairK, V kv) { hash ha; // 负载因子1扩容 if (n _tables[size]) { /*HashtableK, V newHT; newHT._tables.resize(_tables.size() * 2); for (size_t i 0; i _tables.size(); i) { node* cur _tables[i]; while(cur) { newHT.Insert(cur-_kv);//用以前复用的逻辑有点浪费空间了 cur cur-_next; } }*/ vectornode*newht.resize(_tables.size() * 2, nullptr); for (int i 0; i _tables.size(); i) { node* cur _tables[i]; while (cur) { node* next cur-_next; // 旧表中节点挪动新表重新映射的位置 size_t hashi ha(cur-_kv.first) % newht.size(); // 头插到新表当然使用尾插也可以 cur-_next newht[hashi];//头插的逻辑 newht[hashi] cur; cur next; } _tables[i] nullptr;//置空了头结点后面的结点也就找不到了其实感觉不置空也没什么问题 } _tables.swap(newht);//再交换一下 } size_t hashi ha(kv.first) % _tables.size(); //头插 node* newnode new(kv);//通过kv构造一个新结点需要合适的构造函数 newnode-_next _tables[hashi]; _tables[hashi] newnode; n; } Node* Find(const K key) { hash he; size_t hashi he(K) % _tables.size(); node* cur _table[hashi]; while (cur) { if (cur-_kv.first key) { return cur; } cur cur-_next; } return nullptr; } bool Erase(const K key) { hash ha; if (Find(key) nullptr) { return false; } else { size_t hashi ha(K) % _tables.size(); node* cur _table[hashi]; node* prev nullptr; while (cur) { if (cur-_kv.first key) { if (prev nullptr) { _tables[hashi] cur-_next; } else { prev-_next cur-_next; } delete cur; cur nullptr; --n; return true; } prev cur; cur cur-_next } } } private: vectornode* _tables;// 使用指针数组 size_t n 0;//负载因子 };
超大重点分析 为什么需要自己写析构函数呢因为如果让系统调用默认构造的话成员中负载因子属于内置类型编译器不处理然后vector属于自定义类型编译器会调用vector的默认构造这样vector里面的单链表就没有办法析构了就会照成内存泄漏。 为什么扩容不复用insert了呢先说一下为什么会需要扩容随着数据的不断大量的插入单链表肯定在某种情况下会使得某个链表过于长这样在查找哈希表的时候会使得时间复杂度过于大了所以引入负载因子n进行控制当n size时就扩容为什么在扩容时不建议复用呢因为这样不断的创造新的结点而放着旧结点不直接拿来用的话会比较浪费空间创造一个结点的消耗还是比较大的。 为什么这边需要写构造函数因为insert传的是pair那根据这个pair构造新结点的话需要自己写一个构造默认构造用不上。
为什么这边哈希桶状的结构是单链表而不是直接使用list或者C11新加入的forward_list呢首先没说不可以但是用单链表不是更简单吗forward_list尽量少用。
vectorlistpairK, V _tables; // 指针数组
像上面这种就是使用list的写法但是到时候封装的iterator实现起来会比较困难
struct Bucket//联合体 { listpairK, V _lt; mapK, V _m; size_t _bucketsize; // 8 map 8 list
}; vectorBucket _tables;
但是呢就算是有扩容操作还是会有人故意使用一些很极端的数据使得即使多次扩容还是显得某个链表的插入数据很多导致每个链表插入数据的数目不平衡。所以为了解决这种情况有些人会选择当负载因子过大时转而使用搜索树map来代替list实现存储如上 最后一个问题为什么使用头插呢因为其实无论是头插还是尾插在Find还是erase都没什么显著差别的但是在扩容时头插会比尾插更有优势因为每个结点刚开始初始化时的_next结点都是空
这样当头插到开头时每次指向的都是空这样就不会把多余的结点带出来了如果是尾插就需要最后再手动将_next置空。
两种方法对比
应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上 由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间。
