装填因子：a=n/m 其中n 为关键字个数，m为表长。
加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.
冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.
因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.
-
哈希的装填因子
2018-03-20 16:05:00装填因子：a=n/m 其中n 为关键字个数，m为表长。加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:...展开全文转载于:https://www.cnblogs.com/jinhui666/p/8609868.html
-
Redis 哈希表中负载因子问题
2021-02-15 20:19:23最近在看Redis设计与实现，发现Redis中的哈希表也是根据负载因子的扩容和收缩。 当以下条件中的任意一个被满足时， 程序会自动开始对哈希表执行扩展操作： 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令...展开全文最近在看Redis设计与实现，发现Redis中的哈希表也是根据负载因子的扩容和收缩。
当以下条件中的任意一个被满足时， 程序会自动开始对哈希表执行扩展操作：
服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1 ；
服务器目前正在执行BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5 ；上面意思是Redis在进行rdb快照备份的时候，负载因子为5。没有执行rdb快照时负载因子为1。
为什么负载因子可以大于1，并且达到5？HashMap也就0.75而已。
# 负载因子 = 哈希表已保存节点数量 / 哈希表大小 load_factor = ht[0].used / ht[0].size因为已保存节点数量是包括冲突的节点数量，所以已保存节点数量是有可能大于哈希表大小的，所以也就可以达到5。
为什么在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 负载因子要大于等于 5？而未执行时大于等于1？
书中的解释是：
根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行， 服务器执行扩展操作所需的负载因子并不相同， 这是因为在执行BGSAVE 命令或BGREWRITEAOF 命令的过程中， Redis 需要创建当前服务器进程的子进程，
而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率， 所以在子进程存在期间，
服务器会提高执行扩展操作所需的负载因子， 从而尽可能地避免在子进程存在期间进行哈希表扩展操作， 这可以避免不必要的内存写入操作，最大限度地节约内存。
又又又触及到知识盲区了，什么是写时复制？这就要拿linux系统来讲了。首先了解什么是fork？
在linux系统中，fork是类Unix操作系统上创建进程的主要方法。fork用于创建子进程(等同于当前进程的副本)。
Copy On Write原理：
fork创建出的子进程，与父进程共享内存空间。也就是说，如果子进程不对内存空间进行写入操作的话，内存空间中的数据并不会复制给子进程，这样创建子进程的速度就很快了！(不用复制，直接引用父进程的物理空间)。
Copy On Write技术实现原理：
fork()之后，kernel（内核）把父进程中所有的内存页的权限都设为read-only，然后子进程的地址空间指向父进程。当父子进程都只读内存时，相安无事。当其中某个进程写内存时，CPU硬件检测到内存页是read-only的，于是触发页异常中断（page-fault），陷入kernel（内核）的一个中断例程。中断例程中，kernel就会把触发的异常的页复制一份，于是父子进程各自持有独立的一份。
Copy On Write技术好处是什么？
COW技术可减少分配和复制大量资源时带来的瞬间延时。
COW技术可减少不必要的资源分配。比如fork进程时，并不是所有的页面都需要复制，父进程的代码段和只读数据段都不被允许修改，所以无需复制。
Copy On Write技术缺点是什么？
如果在fork()之后，父子进程都还需要继续进行写操作，那么会产生大量的分页错误(页异常中断page-fault)，这样就得不偿失。
-
高级数据结构与算法 | 哈希 ：哈希冲突、负载因子、哈希函数、哈希表、哈希桶
2020-07-12 21:20:19文章目录 哈希 哈希函数 常见的哈希函数 字符串哈希函数 哈希冲突 闭散列的解决方法 开散列的解决方法 负载因子以及增容 对于闭散列 对于开散列结构 具体实现 哈希表（闭散列） 插入 查找 删除 完整代码实现 哈希桶...展开全文文章目录
哈希
在之前介绍的数据结构中，元素与其所存储的位置之间没有对应的关系，所以在查找的时候就需要经过多次的比较，才能找到具体的位置。对于顺序结构来说，这样查找的时间复杂度一般都是O（N）,而对于树形结构的如搜索树等则也需要O（logN）。
但是，还存在着这样一种数据结构，他通过某种方法的处理，使得元素存储的位置与元素本身建立起了映射关系，此时如果要查找改数据，就可以直接到对应的位置去，使得时间复杂度达到了O（1），这就是哈希（散列）。
哈希函数
哈希函数就是建立起元素与其存储位置的映射关系。
对于哈希函数来说，必须具有以下特点;- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0 到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中（防止产生密集的哈希冲突）
- 哈希函数应该比较简单
哈希冲突大量出现往往都是因为哈希函数设计的不够合理，但是即使再优秀的哈希函数，也只能减少哈希冲突的次数，无法避免哈希冲突
常见的哈希函数
- 直接定址法（常见）
哈希函数：Hash（Key）= A*Key + B;
这是最简单的哈希函数，直接取关键字本身或者他的线性函数来作为散列地址。 - 除留余数法（常见）
哈希函数 ：Hash(key) = key % capacity
几乎是最常用的哈希函数，用一个数来对key取模，一般来说这个数都是容量。 - 平方取中法
对关键字进行平方，然后取中间的几位来作为地址。 - 折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加
求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况** - 随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为
随机数函数。
通常应用于关键字长度不等时采用此法 - 数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能
在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出
现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址
字符串哈希函数
因为哈希函数的常用方法如直接定址、除留余数、平方取中等方法需要用的key值为整型，而大部分时候我们的key都是string，对于string来说，上面的方法都行不通，因为无法对string进行算数运算，所以需要考虑新的方法。
常见的字符串哈希算法有BKD,SDB,RS等，这些算法大多通过一些公式来对字符串每一个字符的ascii值或者字符串的大小进行计算，来推导出一个不容易产生冲突的key值。
例如BKDHash
struct _Hash<std::string> { const size_t& operator()(const std::string& key) { //BKDR字符串哈希函数 size_t hash = 0; for (size_t i = 0; i < key.size(); i++) { hash *= 131; hash += key[i]; } return hash; } };这里推荐两篇文章，一篇具体对比各类字符串哈希函数的效率，一篇是实现。
哈希冲突
哈希冲突就是两个不同的数据通过同一个哈希函数计算出了相同的位置，这种现象就是哈希冲突。
哈希冲突使得多个数据映射的位置相同，但是每个位置又只能存储一个数据，所以就需要通过某种方法来解决哈希冲突。
对于哈希冲突的解决方法，一般根据不同的结构，分为以下几种
闭散列的解决方法
因为闭散列是顺序的结构，所以可以通过遍历哈希表，来将冲突的数据放到空的位置上
-
线性探测
线性探测即为从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
这种方法实现起来极为简单，但是效率也不高，因为如果同一位置产生了大量的哈希冲突，就会导致每次都在同一个位置进行探测，例如我在10这里连续冲突100次，此时所有探测的次数加起来就会高达100!，这样方法效率十分的低下。 -
二次探测
线性探测即为从发生冲突的位置开始，每次往后探测i^2个位置，如1， 2， 4， 8等，这样的话就将每次探测的效率从O（N）提升到了O（logN）,即使有着大量的冲突堆积，也不会导致效率过低。
开散列的解决方法
因为开散列本身就是一种链式的结构，所以其本身就是一种解决方法，这种方法也叫做链地址法
链地址法
链地址法在每一个映射位置都建立起一个链表（数据过多时可能会转为建立红黑树），将每次插入的数据都直接连接上这个链表，这样就不会像闭散列一样进行大量的探测，但是如果链表过长也会导致效率低下。
负载因子以及增容
哈希冲突出现的较为密集，往往代表着此时数据过多，而能够映射的地址过少，这就导致了随着数据的增多，冲突的次数就越来越多，而要想解决这个问题，就需要通过负载因子的判断来进行增容。
负载因子的大小 = 表中数据个数 / 表的容量
对于闭散列
对于闭散列来说，因为其是一种线性的结构，所以一旦负载因子过高，就很容易出现哈希冲突的堆积，所以当负载因子达到一定程度时就需要进行增容，并且增容后，为了保证映射关系，还需要将数据重新映射到新位置。
经过算法科学家的计算， 负载因子应当严格的控制在0.7-0.8以下，所以一旦负载因子到达这个范围，就需要进行增容。
因为除留余数法等方法通常是按照表的容量来计算，所以科学家的计算，当对一个质数取模时，冲突的几率会大大的降低，并且因为增容的区间一般是1.5-2倍，所以算法科学家列出了一个增容质数表，按照这样的规律增容，冲突的几率会大大的降低。
这也是STL中unordered_map/unordered_set使用的增容方法。
//算法科学家总结出的一个增容质数表，按照这样增容的效率更高 const int PRIMECOUNT = 28; const size_t primeList[PRIMECOUNT] = { 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 };对于开散列结构
因为哈希桶是开散列的链式结构，发生了哈希冲突是直接在对应位置位置进行头插，而桶的个数是固定的，而插入的数据会不断增多，随着数据的增多，就可能会导致某一个桶过重，使得效率过低。
所以最理想的情况，就是每个桶都有一个数据。这种情况下，如果往任何一个地方插入，都会产生哈希冲突，所以当数据个数与桶的个数相同时，也就是负载因子为1时就需要进行扩容
具体实现
哈希表（闭散列）
对于闭散列，我们需要通过状态来记录一个数据是否在表中，所以这里会使用枚举来实现。
enum State { EMPTY,//空 EXITS,//存在 DELETE,//已经删除 }; template<class T> struct HashData { HashData(const T& data = T(), const State& state = EMPTY) : _data(data) , _state(state) {} T _data; State _state; };插入
插入的思路很简单，计算出映射的地址后，开始遍历判断下面几种状态
- 如果映射位置已存在数据，并且状态为存在，则说明产生冲突，继续往后查找
- 如果映射位置的数据与插入的数据相同，并且状态为存在，则说明此时数据已经插入过，此时就不需要再次插入
- 如果映射位置的状态为删除或者空，则代表着此时表中没有这个数据，在这个位置插入即可
bool Insert(const T& data) { KeyOfT koft; //判断此时是否需要增容 //当装填因子大于0.7时增容 if (_size * 10 / _table.size() >= 7) { //增容的大小按照别人算好的近似两倍的素数来增，这样效率更高，也可以直接2倍或者1.5倍。 std::vector<HashData> newTable(getNextPrime(_size)); for (size_t i = 0; i < _table.size(); i++) { //将旧表中的数据全部重新映射到新表中 if (_table[i]._state == EXITS) { //如果产生冲突，则找到一个合适的位置 size_t index = HashFunc(koft(_table[i]._data)); while (newTable[i]._state == EXITS) { i++; if (i == _table.size()) { i = 0; } } newTable[i] = _table[i]; } } //最后直接将数据进行交换即可，原来的数据会随着函数栈帧一起销毁 _table.swap(newTable); } //用哈希函数计算出映射的位置 size_t index = HashFunc(koft(data)); //从那个位置开始探测, 如果该位置已经存在时，有两种情况，一种是已经存在，一种是冲突，这里使用的是线性探测 while (_table[index]._state == EXITS) { //如果已经存在了，则说明不用插入 if (koft(_table[index]._data) == koft(data)) { return false; } else { index++; index = HashFunc(index); } } //如果走到这里，说明这个位置是空的或者已经被删除的位置，可以在这里插入 _table[index]._data = data; _table[index]._state = EXITS; _size++; return true; }查找
查找也分几种情况
- 如果映射的位置为空，则说明查找失败
- 如果映射的位置的数据不同，并且状态为存在，则说明产生冲突，继续向后查找
- 如果映射的位置的数据相同，如果状态为删除，则说明数据已经删除，查找失败，而如果数据为存在，则说明查找成功。
HashData* Find(const K& key) { KeyOfT koft; size_t index = HashFunc(key); //遍历，如果查找的位置为空，则说明查找失败 while (_table[index]._state != EMPTY) { //此时判断这个位置的数据是否相同，如果不同则说明出现哈希冲突，继续往后查找 if (koft(_table[index]._data) == key) { //此时有两个状态，一种是数据已经被删除，一种是数据存在。 if (_table[index]._state == EXITS) { return &_table[index]; } else if (_table[index]._state == DELETE) { return nullptr; } } index++; //如果index越界，则归零 if (index == _table.size()) { index = 0; } } return nullptr; }删除
直接遍历查找数据，如果找不到则说明已经被删除，如果找到了则直接将状态改为删除即可
bool Erase(const K& key) { HashData* del = Find(key); //如果找不到则说明已经被删除 if (del == nullptr) { return false; } else { //找到了则直接更改状态即可 del->_state = DELETE; _size--; return true; } }完整代码实现
#pragma once #include<vector> namespace lee { //算法科学家总结出的一个增容质数表，按照这样增容的效率更高 const int PRIMECOUNT = 28; const size_t primeList[PRIMECOUNT] = { 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 }; enum State { EMPTY, EXITS, DELETE, }; template<class T> struct HashData { HashData(const T& data = T(), const State& state = EMPTY) : _data(data) , _state(state) {} T _data; State _state; }; template<class K, class T, class KeyOfT> class HashTable { public: typedef HashData<T> HashData; HashTable(size_t capacity = 10) : _table(capacity) , _size(0) {} size_t getNextPrime(size_t num) { size_t i = 0; for (i = 0; i < PRIMECOUNT; i++) { //返回比那个数大的下一个质数 if (primeList[i] > num) { return primeList[i]; } } //如果比所有都大，还是返回最后一个，因为最后一个已经是32位最大容量 return primeList[PRIMECOUNT - 1]; } //除留余数法 size_t HashFunc(const K& key) { return key % _table.size(); } bool Insert(const T& data) { KeyOfT koft; //判断此时是否需要增容 //当装填因子大于0.7时增容 if (_size * 10 / _table.size() >= 7) { //增容的大小按照别人算好的近似两倍的素数来增，这样效率更高，也可以直接2倍或者1.5倍。 std::vector<HashData> newTable(getNextPrime(_size)); for (size_t i = 0; i < _table.size(); i++) { //将旧表中的数据全部重新映射到新表中 if (_table[i]._state == EXITS) { //如果产生冲突，则找到一个合适的位置 size_t index = HashFunc(koft(_table[i]._data)); while (newTable[i]._state == EXITS) { i++; if (i == _table.size()) { i = 0; } } newTable[i] = _table[i]; } } //最后直接将数据进行交换即可，原来的数据会随着函数栈帧一起销毁 _table.swap(newTable); } //用哈希函数计算出映射的位置 size_t index = HashFunc(koft(data)); //从那个位置开始探测, 如果该位置已经存在时，有两种情况，一种是已经存在，一种是冲突，这里使用的是线性探测 while (_table[index]._state == EXITS) { //如果已经存在了，则说明不用插入 if (koft(_table[index]._data) == koft(data)) { return false; } else { index++; index = HashFunc(index); } } //如果走到这里，说明这个位置是空的或者已经被删除的位置，可以在这里插入 _table[index]._data = data; _table[index]._state = EXITS; _size++; return true; } HashData* Find(const K& key) { KeyOfT koft; size_t index = HashFunc(key); //遍历，如果查找的位置为空，则说明查找失败 while (_table[index]._state != EMPTY) { //此时判断这个位置的数据是否相同，如果不同则说明出现哈希冲突，继续往后查找 if (koft(_table[index]._data) == key) { //此时有两个状态，一种是数据已经被删除，一种是数据存在。 if (_table[index]._state == EXITS) { return &_table[index]; } else if (_table[index]._state == DELETE) { return nullptr; } } index++; //如果index越界，则归零 if (index == _table.size()) { index = 0; } } return nullptr; } bool Erase(const K& key) { HashData* del = Find(key); //如果找不到则说明已经被删除 if (del == nullptr) { return false; } else { //找到了则直接更改状态即可 del->_state = DELETE; _size--; return true; } } private: std::vector<HashData> _table; size_t _size; }; };哈希桶（开散列）
开散列也叫哈希桶，桶为每一个映射的位置，桶一般用链表或者红黑树实现（这里我用的是链表）。当我们通过映射的地址，找到存放数据的桶，再对桶进行插入或者删除操作即可。
插入
通过计算映射位置找到对应的桶，再判断数据是否存在后将数据头插进去即可（也可以尾插）
bool Insert(const T& data) { KeyofT koft; /* 因为哈希桶是开散列的链式结构，发生了哈希冲突是直接在对应位置位置进行头插，而桶的个数是固定的，而插入的数据会不断增多， 随着数据的增多，就可能会导致某一个桶过重，使得效率过低。 所以最理想的情况，就是每个桶都有一个数据。这种情况下，如果往任何一个地方插入，都会产生哈希冲突，所以当数据个数与桶的个数相同时，也就是负载因子为1时就需要进行扩容。 */ if (_size == _table.size()) { //按照素数表来增容 size_t newSize = getNextPrime(_table.size()); size_t oldSize = _table.size(); std::vector<Node*> newTable(newSize); _table.resize(newSize); //接着将数据重新映射过去 for (size_t i = 0; i < oldSize; i++) { Node* cur = _table[i]; while (cur) { //重新计算映射的位置 size_t pos = HashFunc(koft(cur->_data)); //找到位置后头插进对应位置 Node* next = cur->_next; cur->_next = newTable[pos]; newTable[pos] = cur; cur = next; } //原数据置空 _table[i] == nullptr; } //直接和新表交换，交换过去的旧表会和函数栈帧一块销毁。 _table.swap(newTable); } size_t pos = HashFunc(koft(data)); Node* cur = _table[pos]; //因为哈希桶key值唯一，如果已经在桶中则返回false while (cur) { if (koft(cur->_data) == koft(data)) { return false; } else { cur = cur->_next; } } //检查完成，此时开始插入，这里选择的是头插，这样就可以减少数据遍历的次数。 Node* newNode = new Node(data); newNode->_next = _table[pos]; _table[pos] = newNode; ++_size; return true; }查找
直接根据映射的位置到桶中查找数据即可
Node* Find(const K& key) { KeyofT koft; size_t pos = HashFunc(key); Node* cur = _table[pos]; while (cur) { if (koft(cur->_data) == key) { return cur; } else { cur = cur->_next; } } return nullptr; }删除
bool Erase(const K& key) { KeyofT koft; size_t pos = HashFunc(key); Node* cur = _table[pos]; Node* prev = nullptr; while (cur) { if (koft(cur->_data) == key) { //如果要删除的是第一个节点，就让下一个节点成为新的头节点，否则直接删除。 if (prev == nullptr) { _table[pos] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_size; return true; } else { prev = cur; cur = cur->_next; } } return false; }完整代码实现
#pragma once #include<vector> #include<string> namespace lee { //算法科学家总结出的一个增容质数表，按照这样增容的效率更高 const int PRIMECOUNT = 28; const size_t primeList[PRIMECOUNT] = { 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 }; /* 因为哈希函数的常用方法如直接定地、除留余数、平方取中等方法需要用的key值为整型，而大部分时候我们的key都是string， 或者某些自定义类型，这个时候就可以提供一个仿函数的接口给外部，让他自己处理如何将key转换成我们需要的整型 */ template<class K> struct Hash { const K& operator()(const K& key) { return key; } }; template<> struct Hash<std::string> { const size_t & operator()(const std::string& key) { //BKDR字符串哈希函数 size_t hash = 0; for (size_t i = 0; i < key.size(); i++) { hash *= 131; hash += key[i]; } return hash; } }; template<class T> struct HashNode { HashNode(const T& data = T()) : _data(data) , _next(nullptr) {} T _data; HashNode<T>* _next; }; template<class K, class T, class KeyofT, class Hash = Hash<K>> class HashBucket { public: typedef HashNode<T> Node; HashBucket(size_t capacity = 10) : _table(capacity) , _size(0) {} ~HashBucket() { Clear(); } size_t getNextPrime(size_t num) { size_t i = 0; for (i = 0; i < PRIMECOUNT; i++) { //返回比那个数大的下一个质数 if (primeList[i] > num) { return primeList[i]; } } //如果比所有都大，还是返回最后一个，因为最后一个已经是32位最大容量 return primeList[PRIMECOUNT - 1]; } size_t HashFunc(const K& key) { Hash hash; return hash(key) % _table.size(); } bool Insert(const T& data) { KeyofT koft; /* 因为哈希桶是开散列的链式结构，发生了哈希冲突是直接在对应位置位置进行头插，而桶的个数是固定的，而插入的数据会不断增多， 随着数据的增多，就可能会导致某一个桶过重，使得效率过低。 所以最理想的情况，就是每个桶都有一个数据。这种情况下，如果往任何一个地方插入，都会产生哈希冲突，所以当数据个数与桶的个数相同时，也就是负载因子为1时就需要进行扩容。 */ if (_size == _table.size()) { //按照素数表来增容 size_t newSize = getNextPrime(_table.size()); size_t oldSize = _table.size(); std::vector<Node*> newTable(newSize); _table.resize(newSize); //接着将数据重新映射过去 for (size_t i = 0; i < oldSize; i++) { Node* cur = _table[i]; while (cur) { //重新计算映射的位置 size_t pos = HashFunc(koft(cur->_data)); //找到位置后头插进对应位置 Node* next = cur->_next; cur->_next = newTable[pos]; newTable[pos] = cur; cur = next; } //原数据置空 _table[i] == nullptr; } //直接和新表交换，交换过去的旧表会和函数栈帧一块销毁。 _table.swap(newTable); } size_t pos = HashFunc(koft(data)); Node* cur = _table[pos]; //因为哈希桶key值唯一，如果已经在桶中则返回false while (cur) { if (koft(cur->_data) == koft(data)) { return false; } else { cur = cur->_next; } } //检查完成，此时开始插入，这里选择的是头插，这样就可以减少数据遍历的次数。 Node* newNode = new Node(data); newNode->_next = _table[pos]; _table[pos] = newNode; ++_size; return true; } bool Erase(const K& key) { KeyofT koft; size_t pos = HashFunc(key); Node* cur = _table[pos]; Node* prev = nullptr; while (cur) { if (koft(cur->_data) == key) { //如果要删除的是第一个节点，就让下一个节点成为新的头节点，否则直接删除。 if (prev == nullptr) { _table[pos] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_size; return true; } else { prev = cur; cur = cur->_next; } } return false; } Node* Find(const K& key) { KeyofT koft; size_t pos = HashFunc(key); Node* cur = _table[pos]; while (cur) { if (koft(cur->_data) == key) { return cur; } else { cur = cur->_next; } } return nullptr; } void Clear() { //删除所有节点 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; } } private: std::vector<Node*> _table; size_t _size; }; };
-
哈希表中的装填因子
2020-05-30 15:57:24装填因子：a=n/m 其中n 为关键字个数，m为表长。 加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:...展开全文装填因子：a=n/m 其中n 为关键字个数，m为表长。
加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.
冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.
因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.
-
哈希表
2017-05-26 22:46:19哈希表的结构是这样的 //HashTable.h #ifndef _HASHTABLE_H_ ...#define HASHTABLE_SIZE 17 //哈希表中基桶个数，为了使得出的哈希因子在所有可得的值中得出任一值的概率相同，所以使用素数作为基桶个数 #define -
Java~ 哈希冲突的避免-哈希函数设计、负载因子调节&&哈希冲突的的解决-开散列、闭散列
2020-05-15 17:37:11什么是哈希冲突： 不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词” 哈希冲突的避免： 首先，我们需要明确一点，... -
哈希
2016-09-23 17:21:55哈希哈希冲突解决办法链式...哈希方法的目的将键均匀，随机分布到表中的哈希函数1 取余法，选择因子 k mod m 2 乘法 m*(k*a mod 1)--0 开放地址hasha = n/m a2 = 1/(1-a)哈希负载因子，均匀分布程度h(k,i) = x (0<i<m- -
（详细介绍）什么叫做哈希冲突？什么是负载因子？如何解决哈希冲突？？？
2020-02-12 00:51:34哈希表 概念： 顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2Nlog_2 Nlog2N)，... -
哈希映射的负载因子_将工作负载映射到云
2020-07-04 10:56:25当团队采用云技术时，他们通常会在技术和项目计划讨论中大意扔掉术语“ 工作量” 。 问题在于该术语对具有不同角色的人而言意味着不同的事物，从而导致分歧和不正确的期望。 本文探讨了这些不同的观点。... -
哈希表插入失败。加载因子太高。
2012-09-05 22:45:04哈希表插入失败。加载因子太高。 在 System.Collections.Hashtable.Insert 在 System.Collections.Hashtable.set_Item 在 System.ComponentModel.ReflectTypeDescriptionProvider.ReflectGetAttributes 在 ... -
解决哈希冲突的方法，Hash的介绍，散列因子的介绍
2018-08-31 13:31:46哈希 哈希算法理解为一种将很大的数据块经过哈希计算，用一个很小的字符串来标识这个很大的数据块 对应的&amp;amp;lt;key,value&amp;amp;gt;模型 key表示计算的哈希值，value表示存放的... -
Java哈希表以及哈希冲突
2020-04-29 14:32:19文章目录Java哈希表概念冲突避免冲突哈希函数的设计方法常见哈希函数负载因子调节解决哈希冲突两种常见的方法是：闭散列和开散列哈希表和 java 类集的关系 Java哈希表 概念 顺序结构以及平衡树中，元素关键码与其... -
全域哈希和完全哈希
2017-02-19 19:22:031、直接映射表 查找数据时，直接定位，时间复杂度为：O(1)； 局限性：浪费大量的内存空间；2、哈希表 (1)、用一个哈希...a：装载因子 哈希函数的选取：除留余数法； ii、开放寻址法，没有链表； 利用多次哈希函数...
收藏数
1,025
精华内容
410