当前位置： 首页 > news >正文

【C++】关联式容器

news 2024/11/1 21:11:17

1.Set和Map

1.1 set的介绍

set是一个常用的关联式容器，它存储唯一的元素，这些元素默认情况下按照升序排序。其底层是一种自平衡的二叉搜索树(红黑树)。

  • set元素的键值就是实值，实值就是键值。
  • set的元素允许插入删除但是不允许修改(具有const属性)。
1.1.1 set的模版参数列表
template<class Key,class Compare = std::less<Key>,class Allocator = std::allocator<Key>
> class set;`
  • Key：set 中存储元素的类型。实际存储的是 <key, key> 这样的键值对，键和值相同。
  • Compare：用于比较元素的函数对象，默认使用 std::less<Key> 进行升序排序。可以通过传入自定义比较器（如 std::greater<Key>）改变排序方式。
  • Allocator：用于管理元素存储空间的分配器，通常使用 STL 提供的默认分配器 std::allocator<Key>。
1.1.2 set常用功能
构造函数：
  • set<int> a：默认构造函数
  • set<int> b(a.begin(), a.end())：利用迭代器范围构造函数。
  • set<int> c{2, 3, 1, 4, 5}：初始化式列表构造函数。
  • set<int> d(c)：拷贝构造函数。
成员函数：
  • 插入元素：
auto ret = s.insert(val);
// ret 是一个 pair<iterator, bool>
// 如果插入成功，ret.second 为 true，ret.first 指向新插入的元素
// 如果插入失败（元素已存在），ret.second 为 false，ret.first 指向已存在的元素
  • 删除元素：
s.erase(s.find(val));	// 删除指定位置的元素。
s.erase(val);			// 删除set中的val，返回删除的元素的个数(0或1)。
s.erase(first, last);	// 删除set中[first, last)区间中的元素
  • 查找元素：
auto it = s.find(val); 		// 查找元素，存在则返回迭代器，否则返回 s.end()
bool found = s.count(val); 	// 检查元素是否存在，返回 0 或 1
  • 边界查找：
auto it_low = s.lower_bound(val); // 返回第一个不小于 val 的元素迭代器
auto it_up = s.upper_bound(val);  // 返回第一个大于 val 的元素迭代器
  • 其他操作：
size_t size = s.size();    // 返回 set 的元素数量
bool empty = s.empty();    // 判断 set 是否为空
s.clear();                 // 清空 set 中的所有元素
  • 遍历元素：
for(const auto &elem : s) {std::cout << elem << " ";
}

multiset：和set基本相同，不同之处在于：容器中的元素可以重复(依然有序)。

1.2 map的介绍

map是另一个常用的关联式容器，它存储键值对，其中每个键都是唯一的，并且默认情况下键按升序排序。其底层实现通常是一种自平衡的二叉搜索树（通常是红黑树）。

1.2.1 map的模板参数列表
template<class Key,class T,class Compare = std::less<Key>,class Allocator = std::allocator<std::pair<const Key,T>>
> class map;
  • Key：键的类型，用于唯一标识一个元素。
  • T：值的类型，与键相关联的数据。
  • Compare：用于比较键的比较器，默认使用 std::less<Key> 进行升序排序(同样可以通过构造模版修改ps：map<int, string, greater<int>> p)。
  • Allocator：管理元素存储空间的分配器，通常使用STL提供的默认分配器。std::allocator<std::pair<const Key, T>>.
1.2.2 map常用功能
构造函数：
  • map<Key, T> a;：默认构造函数。
  • map<Key, T> b(a.begin(), a.end());：通过迭代器范围构造。
  • map<Key, T> c{ {key1, value1}, {key2, value2} };：使用初始化列表构造。
  • map<Key, T> d(c);：拷贝构造函数。
成员函数：
  • 插入函数：
auto ret = m.insert({key, value});
// ret 是一个 pair<iterator, bool>
// 如果插入成功，ret.second 为 true，ret.first 指向新插入的元素
// 如果插入失败（键已存在），ret.second 为 false，ret.first 指向已存在的元素
  • 原位构造元素：
m.emplace(key, value); // 在容器内部直接构造元素，避免额外的复制或移动
  • 删除元素：
m.erase(m.find(key)); // 删除指定键的元素
m.erase(key);         // 删除指定键的元素，返回被删除的元素个数（0 或 1）
m.erase(first, last); // 删除区间 [first, last) 的元素
  • 查找元素：
auto it = m.find(key); 		// 查找键，存在则返回迭代器，否则返回 m.end()
bool found = m.count(key); 	// 检查键是否存在，返回 0 或 1
// 等范围查找
auto range = m.equal_range(key); // 返回键等于给定键的元素范围（对于 map，至多一个元素）
  • 其他操作：
size_t size = m.size();    // 返回 map 的元素数量
bool empty = m.empty();    // 判断 map 是否为空
m.clear();                 // 清空 map 中的所有元素
  • 元素访问：
m[key] = value; 	// 插入或修改键对应的值，如果键不存在则插入
T val = m.at(key); 	// 访问键对应的值，如果键不存在则抛出 std::out_of_range 异常
  • 遍历元素：
for(const auto &pair : m) {std::cout << pair.first << ": " << pair.second << std::endl;
}

1.3 set和map的基本区别

特性setmap
存储结构存储唯一的元素，元素即键值（<key, key>）存储唯一的键值对（<key, value>）
元素唯一性每个元素唯一每个键唯一
排序方式元素按键的升序（或自定义排序）键按升序（或自定义排序）
访问方式通过迭代器遍历，不支持通过键访问支持通过键访问对应的值（operator[] 和 at）
插入与删除允许插入和删除，不允许直接修改元素允许插入、删除和修改值，但键不可修改
查找操作使用 find、count、lower_bound、upper_bound 等使用 find、count、lower_bound、upper_bound 等
内存管理使用 std::allocator<Key>使用 std::allocator<std::pair<const Key, T>>
常用应用场景需要存储唯一且有序的元素，如集合操作需要通过键快速访问和管理相关联的数据，如字典

1.4 元素访问(重点)

1.4.1 map的operator[]和at

  • operator[]：通过键访问对应的值。如果键不存在，则会创建一个新的键值对，并对值进行默认初始化。

    map<std::string, int> m;
m["apple"] = 5;    // 插入键 "apple" 并赋值为 5
int count = m["banana"]; // 如果 "banana" 不存在，插入并初始化为 0
    • 插入修改：operator[]既可以用于插入新元素，也可以用于修改已有元素。
    • 效率问题：如果仅用于查找，且不希望插入新元素，应使用find或at，以避免不必要的插入操作。

  • at方法：通过键访问对应的值。如果键不存在，则抛出out_of_range异常。

    std::map<std::string, int> m;
m["apple"] = 5;
try {int count = m.at("banana"); // 如果 "banana" 不存在，抛出异常
} catch (const std::out_of_range& e) {std::cerr << "Key not found: " << e.what() << std::endl;
}
    • 使用场景：适用于确保键存在的场景，避免隐式插入新元素。
    • 异常处理：使用时需要处理可能抛出的异常。
1.4.2 set的元素访问

set不支持通过下标运算符访问元素，因为它进存储唯一的键，不关联任何值。元素访问通常通过迭代器或查找函数实现。

std::set<std::string> s;
s.insert("apple");
s.insert("banana");auto it = s.find("banana");
if(it != s.end()) {std::cout << "Found: " << *it << std::endl;
} else {std::cout << "Not found." << std::endl;
}
1.4.3 **operator[]**的底层实现

和set的另一个不同点是map支持[]/at元素访问，map的下下标运算符接受一个索引(即一个key)，获取于此关键字相关联的值。但是与其他下标预算符不同的是，如果索引不在map中，就会为它创建一个元素插入到map中，并对值进行初始化。

map的operator[]底层等价于一下操作：

return (*((this->insert(make_pair(k,mapped_type()))).first));
  1. 分析：

底层通过insert实现下面操作:

  • 查找键：

    • 使用 insert 方法尝试插入一个键值对。如果键 k 已存在，插入操作将失败，并返回指向已有元素的迭代器。
    • 如果键 k 不存在，则插入新的键值对，并返回指向新元素的迭代器。

  • 返回引用：

  • insert 返回一个 std::pair<iterator, bool>，其中 first 是指向插入或找到的元素的迭代器。

  • *iterator 解引用迭代器，得到 std::pair<const Key, T>。

  • 返回 second 成员的引用，即与键关联的值。

  1. 注意：
  • operator[]返回值是与键关联的值的引用(mapped_type&)，因此修改返回的引用将直接影响map中对应的键的值。
  • 对于const map对象，应使用at或find进行访问。
1.4.4 代码示例

image-20240728135640791

这里关键在于理解ret.first->second的含义。让我们来逐步分析：

  1. ret：Inset方法返回一个pair<iterator, bool>，其中first成员是一个迭代器，指向插入或找到的元素；second成员是一个布尔值，指示是否成功插入了一个新元素。
  2. ret.first：这是一个迭代器，指向上面定义的RBTree中的一个节点。
  3. ret.first->first：这是通过迭代器访问到键值对中的键的部分。因为节点类型是pair<const K, V>，所以可以通过->first方式访问键K。
  4. ret.first->second：这是通过迭代器访问到键值对中的值部分。同样的因为节点类型是pair<const K, V>，所以可以通过->second方式访问键V。

同时在RBTree 实现中，迭代器类 __RBTreeIterator 中定义了operator->()返回指向_node->_data的指针。因此当我们使用迭代器ret.first并调用ret.first->second是，实际上是在访问_node->_data.second，而_data在RBtree中的类型是T，但在map类中实例化为一个pair<const K, V>的键值对，因此也就访问到了值的部分。

1.5 完整代码（内含注释）

限于篇幅和笔记的简洁性考量，这里就不直接附上代码，而是给出自己写的相关代码地址：

  • 自定义红黑树头文件代码
  • 基于红黑树自定义Map代码
  • 基于红黑树自定义Set代码
  • Map Set 测试代码

另外补充：在自定义map类中，有个MapKeyOfT的内部结构体，定义如下：

struct MapKeyOfT {const K& operator()(const pair<const K, V>& kv) const { return kv.first; }
};

作用：

MapKeyOfT的主要目的是从pair<K, V>类型的键值对中提取键K。它通过重载函数调用运算符operator()来实现这一点，它为RBTree提供了一种一致且高效的方法来访问和比较键。

RBTree<K, pair<const K, V>, MapKeyOfT> _t;

这里MapKeyOfT作为第三个参数模版传递给了RBTree。RBTree需要知道如何从存储的元素中提取键，以便正确地比较和查找键。在 operator[] 的实现中，当插入一个新的键值对时，RBTree 会使用 MapKeyOfT 来提取键，并确保键的唯一性。

2.二叉搜索树(BSTree)

二叉搜索树又称二叉排序树，具有一下性质：

  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
  • 它的左右子树也都是二叉搜索树。

2.1 二叉搜索树的基本操作

  • 插入操作：
    1. 从根节点开始，比较插入值与当前节点的值。
    2. 若插入值小于当前节点，移动到左子树；若大于，移动到右子树。
    3. 重复上述步骤，直到找到一个空的位置，将新节点插入。
  • 查找操作：
    1. 从根节点开始，比较目标节点与当前节点的值。
    2. 若相等，查找成功。
    3. 若目标小于当前节点，移动到左子树；若大于，移动到右子树。
    4. 重复上述操作，直到找到目标值或遍历完整颗树。
  • 删除操纵：
    1. 查找要删除的节点。
    2. 根据节点的子节点情况，执行不同的删除策略：
      • 节点无子节点：直接删除节点。
      • 节点有一个子节点：用子节点替代节点。
      • 节点有两个子节点：找到节点的中序后继(右子树的最小节点)，用后继节点的值替换当前节点，然后删除后继节点。

2.2 完整代码(内含注释)

  • 自定义二叉搜索树
  • 测试代码

3.自平衡二叉搜索树(AVLTree)

AVL tree是一个”加上了额外平衡条件“的二叉搜索树。通过引入额外的平衡条件，确保整颗树的高度为O(logN)。AVL tree要求任何节点的左右子树高度相差最多1。

3.1 平衡因子

平衡因子(Balance Factor，BF)：即在构建树的过程中用来记录节点左右子树节点高度差值的数，即平衡因子=(右子树高度-左子树高度)。

因此为了使树平衡，平衡因子的取值范围应当是**-1、0、1**。

  • 平衡因子 = 0： 左右子树高度相等。
  • 平衡因子 = 1： 右子树比左子树高1；
  • 平衡因子 = -1： 左子树比右子树高1；

3.2 不平衡的情况

然而实际使用过程中难免会存在下图情况导致整颗树的高度大于等于2，例如：

image-20240724161008637

由于节点只有插入节点至根节点路径上的各个节点可能改变平衡状态，因此只要调整最深的不平衡节点即可使整颗树重新平衡。

假设这个左右子树不平衡的节点为X，由于节点最多拥有两个子节点，而所谓的平衡被破坏意味着X的左右两颗子树的高度相差2，因此我们可以推断出有且仅有一下四种情况：

  1. 左左（LL）：插入点在X的左子节点的左子树上。
  2. 右右（RR）：插入点在X的右子节点的右子树上。
  3. 左右（LR）：插入点在X的左子节点的右子树上。
  4. 右左（RL）：插入点在X的右子节点的左子树上。

image-20240724195505644

3.3 旋转操作

为了解决平衡被破坏的问题，需要引入旋转的概念，旋转的本质就是调节平衡因子使其在正确的取值范围。

3.3.1 单旋转

插入点所在位置总共有四种情况，但其实又是两两对称分为外侧和内侧，外侧也就是左左和右右的情况，解决方法如出一辙，下图以外侧插入(左左/LL)为例，为了调整平衡状态，我们希望将A子树上升一层，C子树下降一层。为了实现这一操作 我们可以想象一下将k1提起来(升为这个小群体的老大)，让k2低于k1(成为14的右白虎)，并根据左小右大原则把k1的右子树挂给到k2的左侧(这关键 但也很好理解，左小右大嘛)

image-20240724201702935

3.3.2 示例代码

光说不练家把什，上代码！（左旋转，适用于右右情况，即插入点在不平衡子树的右子树的右节点上），右右会了，左左是对称关系如法炮制即可。

void RotateL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;// P1parent->_right = subRL;if (subRL) {subRL->_parent = parent;}Node* ppnode = parent->_parent;// P2subR->_left = parent;parent->_parent = subR;// 当传入的节点就是根节点时的情况if (ppnode == nullptr) {_root = subR;_root->_parent = nullptr;}// 处理传入节点为根节点的子树群else {if (ppnode->_left == parent)ppnode->_left = subR;elseppnode->_right = subR;subR->_parent = ppnode;}// 更新这个已经处理平衡了的子树群的平衡因子ppnode->_bf = subR->_bf = 0;
}
3.3.3 图解

image-20240724203523894

3.4 双旋转

实际应用场景中我们会发现有些问题一次单旋无法解决问题这就需要用到双旋的概念，有了对单旋的理解双旋就很容易理解了，下图的左右不平衡状态单旋转无法解决这种情况，因为会发现插入15后不管对谁单旋转都还是不平衡，唯一的可能是以k2为新的跟节点 让k1成为k2的左节点，k3成为k2的有节点，因此我们可以先对k1做左旋，再对k3做右旋以此达到目的。

image-20240724221954578

3.4.1 示例代码

先右旋转，再左旋转，适用于RL情况：

void RotateRL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;// 这里记录一下旋转前的插入点的父节点的平衡因子，作为后序更新平衡因子的依据int bf = subRL->_bf;// 先右旋子节点，将右左问题 处理成 右右问题RotateR(subR);// 在将右右的子树左旋RotateL(parent);// 更新节点 -> 1.左小右大 2.平衡因子=(右树高-左树高)if (bf == 1) {	// 说明插入的节点在右节点subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == -1) {subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}/*	不可能出现这种情况，bf等于0也就意味着在插入这个*	新节点的之前subRL已经存在一个左或右节点才使得插入后的*	subRL得平衡因子保持平衡，而这是不可能的因为再此之前就已经*	不平衡应当被单旋或双旋处理了，再此写出是为了让代码更清晰直观*/else if (bf == 0) {subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}else {assert(false);}
}

image-20240724215752426

一个小技巧判断是单旋问题还是双旋问题：不平衡节点到插入点之前的连线->如果是直线就是单旋，如果是折线就是双旋。

3.5 完整代码(内含注释)

  • 自定义AVL树
  • 测试代码

4.红黑树

AVL-tree之外，另一个运用颇为广泛的的平衡二叉树是RB-tree，RB-tree满足二叉树的同时还有以下规则：

  1. 满足平衡二叉树(左小右大)。
  2. 根节点和叶子节点(NULL)是黑色。
  3. 如果一个节点是红色的则它的两个孩子节点必须是黑色的，即不存在两个连续红色节点。
  4. 任一节点到叶子节点(NULL)的任何路径，所含的黑色节点数必须相同。

由于红黑树的性质使得它最长的路径(一黑一红的组合)绝不会超过最短路径(全黑)的两倍。

理论上来说红黑树性能不如AVL-tree，但是由于当今PC硬件的性能提升，这点性能上的差距已经非常小了，而之所以红黑树比AVL-tree应用更为广泛的原因是因为：同样的插入删除操作红黑树要比AVL-tree效率高，且旋转更少，控制实现相对简单。因为AVL-tree更严格的平衡其实是通过频繁的旋转达到的。其次就是红黑树在实现上更容易控制。由相较而言：AVL树查询更高效，维护严格平衡，频繁旋转而红黑树插入删除更高效。

4.1 插入

红黑树的插入默认是红色，然后再根据树的情况是否做调节。这是因为如果默认是黑色有极大概率会违反规则需要考虑的因素和影响更大，而默认红色会有概率无需调整。

插入节点使得红黑树的性质遭到破坏此时需要根据下面三种情况做调整：

  • 插入点是根节点：cur == root;
  • 插入点的叔叔节点是红色： (cur->parent->parent->right/left).colour == red;
  • 插入点的叔叔节点是黑色： (cur->parent->parent->right/left).colour == black;

image-20240726220040465

4.2 插入流程图*

image-20240820101704566

4.3 插入完整代码

为方便理解学习，下面代码是原始版本，之后链接中完整代码再做优化：

bool Insert(const pair<K, V>& kv) {if (_root == nullptr) {_root = new Node(kv);_root->_col = BLACK;	// 根节点必须为黑色return true;}Node* parent = nullptr;Node* cur = _root;// 先定位到要插入的位置while (cur){parent = cur;if (kv.first < cur->_kv.first) {cur = cur->_left;}else if (kv.first > cur->_kv.first) {cur = cur->_right;}else {return false;	// 相等}}// 插入对应的位置cur = new Node(kv);cur->_col = RED;	// 添加默认红色if (kv.first > parent->_kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;// parent是黑色可以直接结束while (parent != nullptr && parent->_col == RED) {Node* grandfather = parent->_parent;// 要判断是左叔还是右叔if (parent == grandfather->_left) {Node* uncle = grandfather->_right;	// 右叔// 右叔存在且为红if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}// 右叔不在或为黑else {if (cur == parent->_left) {/* LLgp   uc*/RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {/* LRgp   uc*/RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else {Node* uncle = grandfather->_left;	// 左叔// 左叔在且为红if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}// 左叔不在或为黑else {if (cur == parent->_right) {/* RRgu   pc*/RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {/* RLgu   pc*/RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 根节点必须为黑_root->_col = BLACK;return true;
}

4.4 完整代码(内含注释)

  • 自定义红黑树代码
  • 测试代码

5.哈希

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2 N)，搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中:

  • 插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
  • 搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable/散列表).

注意：例如在集合 {4, 2, 6, 9999} 这种数据分布不均匀的情况，那么给每个值的映射位置就可能会造成巨大的空间浪费。

5.1 哈希函数

哈希函数是一种将输入(字符或数字)转换为固定长度值的算法。这个固定长度值通常用来作为哈希表的索引，以便在数据存储和检索时实现高效的查找操作。

一个解决方法是除留余数法：不再给每个值映射一个位置，而是在限定大小的空间中将我们的值映射进去。

哈希函数表现为：hash(key) = key % capacity

其中capacity默认设置为10，这样简单也方便取模运算。

然而这又会带来一个问题：不同的值可能会映射到相同的位置上去，导致哈希冲突，哈希冲突越多对整体而言效率就越低。

那么如何解决哈希冲突呢？

5.2 负载因子

负载因子：是哈希表中元素个数与表大小的比率，定义为：负载因子=表中数据个数/表的大小。

即闭散列表中的元素越接近满的状态，冲突的概率就越大，效率也就也低。因此提出负载因子的概念。负载因子越接近1，表示哈希表越满，冲突的概率越高，效率越低。因此一般情况闭散列的哈希表中，负载因子到0.7就开始增容是比较合理的。

一般情况下，负载因子越小，冲突概率就越低。但是如果负载因子控制的太小，会导致大量空间的浪费(如：负载因子设为0.3，那就意味着总是会有70%的空间空着)，因此可以看出负载因子就是一种空间换时间的思路。

5.3 哈希冲突的解决

哈希冲突是指多个关键码经过哈希函数计算后映射到同一个位置。常见的冲突解决方法包括：

5.3.1 闭散列(开放地址法)

在闭散列中，当冲突时就按照某种规则再找下一个空位置（抢占式）

  • 线性探测：紧接着往后找（i+1、i+2...），直到找到下一个空位。线性探测有个弊端就是可能会导致连续的冲突(例如：只插入9、19、29、39…会导致冲突区域集中)，从而降低查找效率，平均插入成本的成长幅度远高于负载因子的成长幅度。
  • 二次探测：主要是用来缓解冲突区域集中的问题，按照平方跳跃（i^2）着往后找，直到找到空位置，即根据公式：i = (hash(key)+i^2)%capacity。这种方法减少了冲突区域的集中，提升了插入和查找的均匀性。

示例：

image-20240729200231472

ps.(i为插入值的索引位置)，下面文字方式对上图示例加以解释(暂时不考虑插入满的情况)：

分别以线性探测和二次探测的方式插入{89, 18, 49, 58, 9, 69}

线性探测：

  • 插入18：h(18) = 18%10=8;
  • 插入89：h(89) = 89%10=9;
  • 插入49：取模后等于9，但9已经被占了就找到下一个没有被占领的地方i++;
  • 后面插入的同上，没空就往后排。

二次探测：

  • 插入18…;插入89…;
  • 插入49：发现位置9被占用，进行二次探测：
    • i=(9+1^2)%10=0，0没被占 插入。
  • 插入58：位置8被占了，进行二次探测：
    • i=(8+1^2)%10=9，被占了 继续。
    • i=(8+2^2)%10=2，2没被占 插入。
  • 后面插入的同上，函数映射位置被占就进行二次探测。

下面介绍闭散列的插入查找删除操作，但再次之前还有引入元素状态概念

元素状态

哈希表中的元素状态（EMPTY、EXISTS、DELETE）的设计主要是为了处理插入、查找和删除操作中的特殊情况和冲突。这种状态管理是开放地址法（如二次探测法）的一部分，用于解决哈希冲突。下面解释每种状态的作用：

EMPTY：

  • 表示哈希表中该位置从未被使用过。
  • 当插入新元素时，如果找到一个状态为 EMPTY 的位置，就可以安全地插入新元素。
  • 查找元素时，如果遇到一个状态为 EMPTY 的位置，表示该元素不存在于哈希表中，因为它从未被占用过。

EXISTS：

  • 表示该位置当前存储着一个有效的元素。
  • 插入新元素时，如果找到一个状态为 EXISTS 的位置，并且键相同，可以更新该位置的值；如果键不同，则需要继续探测下一个位置（解决冲突）。
  • 查找元素时，如果找到一个状态为 EXISTS 的位置，并且键匹配，就找到了目标元素。

DELETE：

  • 表示该位置之前存储过一个元素，但该元素已被删除。
  • 插入新元素时，如果找到一个状态为 DELETE 的位置，可以安全地插入新元素。
  • 查找元素时，如果遇到一个状态为 DELETE 的位置，表示这个位置曾经被使用过，但现在已被删除。查找不能停止，需要继续探测下一个位置。

ps.那为什么还要判断删除状态呢？那是因为hash采用惰性删除(只是对删除位置进行标记)，当您删除一个元素时，通常不会真正从哈希表中移除它，而是将其标记为已删除（例如，设置为 DELETE 状态）。这是因为，如果一个位置被完全清空，它可能会影响到其他元素的探测路径。特别是当两个或多个元素的哈希值相同时，它们可能会被放置在同一位置附近，或者它们的探测路径可能重叠。

例如插入1和11，如在查找11之前把1删了，那么去找11的哈希值"1"时就发现找不到了，此时无法以更优的性能去知道11究竟是否存在，而将删除元素定义为DELETE就知道后面可能还会有哈希值相同的元素，也就方便继续探测。

5.2.2 开散列/拉链法(哈希桶)

我们可以发现上述的闭散列也并非是一个好的解决办法，因为当每次插入发现元素的哈希索引被占用都必然会抢占式的占用其他元素的索引位置，从而不断的冲突，没完没了，整体效率偏低，不能作为最终解决方案。

进而引出哈希桶的概念：

开散列法又称链地址池(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合成为一个桶，各个桶中的元素通过一个单链表链接起来，各个链表的头结点存储在哈希表中。

image-20240730124454994

image-20240730124825297

从上图可以看出，开散列每个桶放的都是发生哈希冲突的元素。

完整代码(基础版)：

#include <utility>
#include <vector>
#include <functional>template<class T>
struct HashNode {T _data;HashNode<T>* _next;HashNode(const T& data): _data(data), _next(nullptr){}
};
// 自定义类型提取器
template <class K>
struct HashFunc {const K& operator()(const K& key) { return key; }
};
template<class K, class T, class KeyOfT>
class HashTable {using Node = HashNode<T>;
public:HashTable(size_t capacity = 10) : _tables(capacity), _num(0) {}bool Insert(const T& data) {KeyOfT koft;// 控制桶的负载因子：如果等于1，就对表增容，避免大量冲突。if (_tables.size() <= _num) {resize();}size_t index = koft(data) % _tables.size();// 1.先查找这个值在不在表中Node* cur = _tables[index];while (cur) {if (koft(cur->_data) == koft(data))return false;cur = cur->_next;}// 2.头插到挂的链表中(也可尾插)Node* newnode = new Node(data);newnode->_next = _tables[index];_tables[index] = newnode;++_num;return true;}Node* Find(const K& key) {KeyOfT koft;size_t index = key % _tables.size();Node* cur = _tables[index];while (cur) {if (koft(cur->_data) == key)return cur;cur = cur->_next;}return nullptr;}bool Erase(const K& key) {KeyOfT koft;size_t index = key % _tables.size();Node* prev = nullptr;Node* cur = _tables[index];while (cur) {if (koft(cur->_data) == key) {if (prev == nullptr)_tables[index] = cur->_next;elseprev->_next = cur->_next;delete cur;return true;}else {prev = cur;cur = cur->_next;}}return false;}
private:void resize() {KeyOfT koft;std::vector<Node*> newTables(_tables.size() * 2, nullptr);for (auto& cur : _tables) {while (cur) {Node* next = cur->_next;size_t index = koft(cur->_data) % newTables.size();cur->_next = newTables[index];newTables[index] = cur;cur = next;}}_tables.swap(newTables);}private:std::vector<Node*> _tables;size_t _num = 0;	// 记录表中存储的数据个数。
};

5.4 完整代码(内含注释)

  • 自定义闭散列哈希表
  • 自定义开散列哈希表（进阶）
  • 测试代码

6.海量数据

6.1 位图(BitSet)

bitset是hash在位图上的应用，主要用于在大规模数据中高效查找和统计。

位图的概念：位图是一中非常紧凑的数据结构，它使用二进制位来表示集合中的元素。每个元素对应一个位，如果该元素存在于集合中，则对应的位设置为1；否则为0。从而节省了大量的内存空间。一般用来解决在海量数据中查找统计。

image-20240805125915357

注意：bitset的下标编号与通常习惯恰好相反：下标法中最大的字符(最右字符)用来初始化bitset中的地位(下标为0的二进制位)。

6.1.1 代码实现
#pragma once
#include <vector>namespace cl {// N为bit的位图template<size_t N>class bitset {public:// 初始化_bits向量中的每个元素为0// +1避免不能被整除时造成的比特位丢失bitset() { _bits.resize(N/8 + 1, 0); }// 设置指定位置的位为1void set(size_t x) {// x映射的比特位在第几个int对象size_t index = x / 8;// x在int的第几个比特位。size_t pos = x % 8;_bits[index] |= (1 << pos);}// 重置指定位置的位为0void reset(size_t x) {size_t index = x / 8;size_t pos = x % 8;_bits[index] &= (~(1 << pos));}// 获取指定位置的状态bool test(size_t x) {size_t index = x / 8;size_t pos = x % 8;return _bits[index] & (1 << pos);}private:std::vector<int> _bits;};
}

应用场景：例如，【腾讯】面试题：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。此时使用位图存储只需要500mb空间即可快速判断。

6.2 布隆过滤器(bloomFilter)

一种紧凑型的比较巧妙的概率型数据结构，特点是高效的插入和查询，其主旨是采用一个很长的二进制数组，通过一系列的Hash函数，将一个数据映射到位图结构中，从而达到确定该数据是否存在的目的。此方法不仅可以提升查询效率也可以节省大量的内存空间。

下面是位图与布隆过滤器的对比：

特性位图（BitSet）布隆过滤器（Bloom Filter）
数据结构位数组，每个元素占用一位位数组和多个哈希函数
空间效率高，对于稀疏集合效率低高，对于大规模数据更节省内存
查询结果确定性，无误报或漏报概率性，可能有误报，无漏报
插入操作O(1)O(k)，k是哈希函数数量
查询操作O(1)O(k)
删除操作O(1)不支持简单删除，需要使用计数布隆过滤器
应用场景适用于确定性的数据存储和查询，特别适合于固定大小的集合，如：内存分页管理、整数集合表示、哈希表位标记适用于需要快速查询和节省空间的场景，特别是允许有一定的误报率的情况下，如：缓存系统、垃圾邮件过滤、数据库查询优化、大规模数据快速判断
内存使用与元素范围直接相关与元素数量和误报率相关
典型用法表示整数集合、内存管理判断元素是否可能存在于集合中，适用于大数据应用
误报率无有误报率，通过调整参数控制
6.2.1 创建与使用

通过图文的方式介绍布隆过滤器的创建于使用：

假设场景：商城中有1000个商品，商品编号0~1000，针对这个场景模拟一个二进制数组，其每个位的初识值都是0。那么这个数组该如何使用呢？布隆过滤器在初始化的时候，实际上就是对每个商品编号进行若干次的hash来确定它们的位置。

例如编号1：我们对其进行三次哈希(所谓哈希就是将数据通过特定的哈希函数转换确定一个具体的位置)，比如hash1()当对编号1进行哈希时，它会定位到二进制数组的第2位上，并将其数值从0改为1；那hash2()函数它定位到索引值为5的位置，并将0改为1；hash3()函数定位到索引为99的位置上，将其从0改为1。

之后是2号商品，经过三轮哈希后分别定位到索引为 1、3、98号位置上，原始数据中1号因为刚才已经变成了1，现在它不变，而3号位和98号位原始数据从0变为1。这里衍生出一个哈希新的规则：

如果在哈希后原始位它是0的话，将其从0变为1，如果本身这一位就是1的话，则保持不变。(这点很重要)

1号2号处理完成之后，3~1000号如法炮制。

image-20240805145603449

全部处理完成之后作为布隆过滤器存储在我们的计算机中，那么该如何使用呢？

6.2.2 判断与使用

我们先看一个已存在的，比如此时某一个用户要查询858号商品数据，那么布隆过滤器按照原始的三个哈希分别定位到了1 5和98号位，当每一个哈希位的数值都是1的时候，则代表对应的编号它是存在的。

image-20240805151347014

那下面我们再看一个不存在的情况，例如这里要查询8888。对于8888这个数值经过三次哈希以后，定位到了3、6和100这三个位置，此时索引为100的数值是0。在多次哈希时，有任何一个位为0，则代表这个数据是不存在的。

image-20240805151704063

简单总结一下，如果布隆过滤器所有哈希位的值都是1的话，则代表这个数据**可能存在(注意我的用词它是可能存在)，但是如果某一位的数值是0的话它是一定不存在**的。在布隆过滤器设计之初，它就不是一个精确的判断，因为布隆过滤器存在误判的情况。

那下面我们看一个误判情况，比如现在我要查询8889的情况，经过三次哈希，正好每一位上都是1。尽管在数据库中8889这个商品是不存在的，但是在布隆过滤器中，它会被判定为存在，这是这在布隆过滤器中会出现的小概率的误判情况。

image-20240805152048438

那如何减少误判的产生呢？其实方法有两个，

  1. 增加二进制位数，在原始情况下，我们设置索引位到达了100，但是如果我们把它放大1万倍，到达了100万，是不是哈希以后的数据会变得更加的分散，那出现重复的情况就会更小，这是第一种方式。
  2. 增加哈希的次数，其实每一次哈希处理都是在增加这个数据的特征，特征越多，出现误判的概率就越小。现在我们是做了3次哈希，如果做10次哈希它出现的概率就会小非常非常多。但是在这个过程中，代价便是CPU需要进行更多的运算，会让布隆过滤器的性能有所降低。

一个延伸的小问题:假如布隆过滤器在初始化以后对应的商品被删除了该怎么办呢？

这是一个布隆过滤器的难点，因为布隆过滤器某一位的二进制数据可能被多个编号的哈希来进行引用，比如说布隆过滤器中二号位是1，但是它可能被3、5、100、1000这四个商品编号同时引用，这里是不允许直接对布隆过滤器某一位进行删除的，否则数据就乱了。那怎么办呢？在实际应用中有两种常见的解决方案：

第一种是定时异步重建布隆过滤器，比如说每过4个小时，在额外的一台服务器上异步的去执行一个任务调度，来重新生成布隆过滤器，替换掉已有的布隆过滤器。而另外一种做法叫做计数布隆过滤器，在标准的布隆过滤器下，是无法得知当前某一位它是被哪些具体数据进行了引用。但是计数布隆过。滤器，它是在这一位上额外了附加的计数信息，表达出该位被几个数据进行了引用。

6.2.3 代码实现
#pragma once
#include <string>
#include <bitset>namespace cl {// 哈希函数结构体，用于计算字符串的哈希值struct BKDRhash {size_t operator()(const std::string& s) const {size_t value = 0;// 遍历字符串中的每个字符，计算哈希值for (auto ch : s) {value *= 131; // 乘以131，常用的质数value += ch;  // 加上当前字符的ASCII值}return value;}};struct APHhash {size_t operator()(const std::string& s) const {size_t hash = 0;// 遍历字符串，按位置的奇偶性分别处理for (long i = 0; i < s.size(); i++) {if ((i & 1) == 0) { // 偶数位置hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));}else { // 奇数位置hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));}}return hash;}};struct DJBhash {size_t operator()(const std::string& s) const {size_t hash = 5381; // 初始化哈希值// 遍历字符串中的每个字符，计算哈希值for (auto ch : s) {hash += (hash << 5) + ch; // 乘以33加上当前字符的ASCII值}return hash;}};struct JSHash {size_t operator()(const std::string& s) const {size_t hash = 1315423911; // 初始化哈希值// 遍历字符串中的每个字符，计算哈希值for (auto ch : s) {hash ^= ((hash << 5) + ch + (hash >> 2)); // 进行移位和异或操作}return hash;}};// 布隆过滤器模板类，用于判断一个元素是否存在于集合中template<size_t M, class K = std::string,class HashFunc1 = BKDRhash,class HashFunc2 = APHhash,class HashFunc3 = DJBhash,class HashFunc4 = JSHash>class BloomFilter {public:// 将元素插入布隆过滤器void Set(const K& key) {// 计算元素的四个哈希值，并取模到位数组的大小size_t hash1 = HashFunc1()(key) % M;size_t hash2 = HashFunc2()(key) % M;size_t hash3 = HashFunc3()(key) % M;size_t hash4 = HashFunc4()(key) % M;// 设置位数组相应位置为1_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);_bs.set(hash4);}// 测试元素是否存在于布隆过滤器中bool Test(const K& key) {// 计算元素的四个哈希值，并取模到位数组的大小size_t hash1 = HashFunc1()(key) % M;if (_bs.test(hash1) == false) { return false; }size_t hash2 = HashFunc2()(key) % M;if (_bs.test(hash2) == false) { return false; }size_t hash3 = HashFunc3()(key) % M;if (_bs.test(hash3) == false) { return false; }size_t hash4 = HashFunc4()(key) % M;if (_bs.test(hash4) == false) { return false; }// 如果所有位都为1，则可能存在（存在误判的可能性）return true;}// 重置元素在布隆过滤器中的位置（不可用，因为可能误删其他数据）bool Reset(const K& key) {// 该功能在布隆过滤器中通常不可用，无法确保准确性return false; // 返回false，指示无法重置}private:std::bitset<M> _bs; // 位数组，用于表示集合};
}

6.3 海量数据面试题

6.3.1 哈希切割
  1. 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
    • 将log文件分割成多个小文件（如100M）。
    • 对每个小文件进行单独处理，使用哈希表记录每个IP的出现次数。
    • 合并所有小文件的结果，统计每个IP的总出现次数，找到出现次数最多的IP。
  2. 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？
    • 类似于上述步骤，先统计每个IP的出现次数，然后使用小顶堆（min-heap）维护Top K的IP。
    • 使用优先队列（priority_queue）实现小顶堆。
    • 每次统计时，若出现次数超过当前堆顶，则替换堆顶，保持堆的大小为K。
6.3.2 位图应用

  1. 给定100亿个整数，设计算法找到只出现一次的整数？

    • 使用位图存储整数的出现情况，使用第二个位图记录重复的整数。

    • 遍历所有整数，设置对应的位，若再次出现则标记为重复。

    • 最后遍历位图，找出未标记的位即为只出现一次的整数。

  2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

    • 读取第一个文件中的所有整数并建立位图。
    • 遍历第二个文件，检查位图中对应的位，记录交集。

  3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。

    • 使用两个位图，一个用于记录出现次数为1的整数，另一个记录出现次数为2的整数。

    • 遍历文件，更新位图状态，最后取出两个位图中标记为1的整数

6.3.3 布隆过滤器

  1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

    • 精确算法：使用哈希表存储第一个文件的所有整数，然后遍历第二个文件，检查每个整数是否在哈希表中。

    • 近似算法：使用布隆过滤器存储第一个文件的所有整数，然后遍历第二个文件，检查每个整数在布隆过滤器中是否可能存在。

  2. 如何扩展BloomFilter使得它支持删除元素的操作？

    • 使用计数布隆过滤器，每个哈希位置存储一个计数值，而不是一个位。
    • 插入时增加计数，删除时减少计数，当计数为0时认为该元素已被删除。

6.4 一致性哈希问题

一致性哈希是一种用于分布式系统中数据分配和负载均衡的方法。它的主要优点在于能有效减少节点变动时对已有数据的影响，降低系统的重分配成本。

6.4.1 一致性哈希的背景

在分布式系统中，数据往往被分散存储在多个节点上。随着系统的扩展（添加或移除节点），如何高效地管理数据的分布成为一个重要问题。传统的哈希方法在节点变化时可能导致大量数据重新分配，造成性能瓶颈。

6.4.2 基本概念

一致性哈希的核心思想是将整个哈希空间视为一个圆环（或环形哈希空间），而节点和数据都被映射到这个环上。其基本步骤如下：

  • 哈希空间：定义一个哈希值的范围，通常是一个大整数（例如0到2^32-1）。
  • 节点映射：将每个节点通过哈希函数映射到这个哈希空间的某个点。
  • 数据映射：同样地，数据对象（如用户请求或存储的文件）也通过哈希函数映射到环上的某个点。
  • 数据存储：每个数据对象存储在顺时针方向上第一个遇到的节点。
6.4.3 节点变动的影响

添加节点：当一个新节点加入时，它会接管顺时针方向上某些数据对象，这意味着只有这些对象需要重新分配，其他对象保持不变。

移除节点：当节点移除时，原本由该节点存储的数据会转移到顺时针方向上的下一个节点。

6.4.4 虚拟节点

为了进一步提高负载均衡，一致性哈希通常会引入虚拟节点的概念。每个实际节点在哈希环上对应多个虚拟节点。这样做的好处包括：

  • 减少热点：通过增加虚拟节点，能够更均匀地分布数据，避免某些节点负载过重。
  • 平滑数据分布：即使在节点数目较少时，虚拟节点也能帮助实现较为均匀的数据分布。
6.4.5 应用场景

一致性哈希广泛应用于分布式缓存系统（如Redis）、分布式存储（如Amazon DynamoDB）、CDN（内容分发网络）等场景，能够有效应对大规模数据存储和访问中的节点管理问题。


http://www.mrgr.cn/news/63534.html

相关文章：

  • Java第二阶段---15异常---第三节 自定义异常
  • Linux(Cent OS)环境离线安装mkfontscale mkfontdir命令 解决java项目在linux系统下无法获取中文字体问题
  • 程序中怎样用最简单方法实现写excel文档
  • 【elkb】索引生命周期管理
  • 【Android】Android 性能分析利器 - Perfetto
  • 【AI开源项目】FastGPT- 快速部署FastGPT以及使用知识库的两种方式！
  • [ 问题解决篇 ] win11中本地组策略编辑器gpedit.msc打不开(gpedit.msc缺失)
  • ElementUI中el-table双击单元格显示输入框
  • 提升安全上网体验：Windows 11 启用 DOH（阿里公共DNS）
  • 多SpringBoot项目同进程下统一启动
  • 华为认证HCIE通过需要考到多少分？_博睿谷·博睿慕课
  • layui 自定义验证单选框必填
  • Raspberry Pi 树莓派产品系列说明
  • Django入门教程——用户管理实现
  • 【C语言学习笔记】
  • 现货白银实时行情怎么看？首先搞清楚这个原则
  • @Async(“asyncTaskExecutor“) 注解介绍
  • 链栈的引用
  • C# 两个不同文件路径的同步
  • Latex中Reference的卷号加粗的问题
  • 指令系统 II（程序的机器级代码表示、CISC 和 RISC）
  • 写一个小日历
  • 中电金信：GienTech动态|丰收之秋，公司多项目获得荣誉
  • 如何解决docker镜像下载失败问题
  • （9）位运算
  • 用友U8采购入库单与旺店通·企业奇门集成方案解析