哈希表如何在相同值或冲突值上呈线性？
How hashtables are linear on same or collision values?
我正在查看 this Whosebug 答案以更好地理解散列并看到以下内容（关于我们需要在恒定时间内获取桶大小的事实）：
如果您使用线性探测或双重散列之类的方法，找到散列为相同值的所有项目意味着您需要对该值进行散列，然后遍历 "chain" 个非空项目table 找出有多少哈希值相同。不过，这与散列为相同值的项目数量不是线性关系——它与散列为相同值或冲突值的项目数量成线性关系。
"linear on the number of items that hashed to the same or a colliding value" 是什么意思？它不会与散列中的项目总数呈线性关系 table，因为在线性探测期间可能需要遍历每个值？我不明白为什么它只需要经过碰撞的那些。
例如，如果我在散列上使用线性探测（步长 1）table，并且我有不同的键（不冲突，所有散列到唯一值）映射到奇数索引槽1,3,5,7,9..... 然后，我想插入许多哈希值都为 2 的键，所以我用这些键填充了所有偶数索引点。如果我想知道有多少个键散列为 2，我不需要遍历整个散列 table 吗？但我不只是遍历散列为相同或冲突值的项目，因为奇数索引槽没有冲突。
散列table在概念上类似于链表数组（table）（table中的bucket）。区别在于您管理和访问该数组的方式：使用函数生成用于计算数组索引的数字。
一旦你将两个元素放在同一个桶中（相同的计算值，即碰撞），那么问题就变成了列表中的搜索。列表中的元素数量希望低于散列中的元素总数table（意味着其他元素存在于其他桶中）。
但是，您跳过了该段中的重要介绍：
If you use something like linear probing or double hashing, finding all the items that hashed to the same value means you need to hash the value, then walk through the "chain" of non-empty items in your table to find how many of those hashed to the same value. That's not linear on the number of items that hashed to the same value though -- it's linear on the number of items that hashed to the same or a colliding value.
Linear probing 是散列 table 的另一种实现，其中您不使用任何列表（链）进行碰撞。相反，您只需找到阵列中最近的可用点，从预期位置开始并向前移动。数组填充的越多，越有可能发现下一个位置也在被使用，所以你只需要继续搜索。这些位置由 散列为相同或冲突值 的项目使用，尽管您永远不会（并且您并不真正关心）这两种情况中的哪一种，除非您明确看到现有元素的哈希值。
This CppCon presentation video对hashtables做了很好的介绍和深入分析
我正在查看 this Whosebug 答案以更好地理解散列并看到以下内容（关于我们需要在恒定时间内获取桶大小的事实）：
如果您使用线性探测或双重散列之类的方法，找到散列为相同值的所有项目意味着您需要对该值进行散列，然后遍历 "chain" 个非空项目table 找出有多少哈希值相同。不过，这与散列为相同值的项目数量不是线性关系——它与散列为相同值或冲突值的项目数量成线性关系。
"linear on the number of items that hashed to the same or a colliding value" 是什么意思？它不会与散列中的项目总数呈线性关系 table，因为在线性探测期间可能需要遍历每个值？我不明白为什么它只需要经过碰撞的那些。
例如，如果我在散列上使用线性探测（步长 1）table，并且我有不同的键（不冲突，所有散列到唯一值）映射到奇数索引槽1,3,5,7,9..... 然后，我想插入许多哈希值都为 2 的键，所以我用这些键填充了所有偶数索引点。如果我想知道有多少个键散列为 2，我不需要遍历整个散列 table 吗？但我不只是遍历散列为相同或冲突值的项目，因为奇数索引槽没有冲突。
散列table在概念上类似于链表数组（table）（table中的bucket）。区别在于您管理和访问该数组的方式：使用函数生成用于计算数组索引的数字。
一旦你将两个元素放在同一个桶中（相同的计算值，即碰撞），那么问题就变成了列表中的搜索。列表中的元素数量希望低于散列中的元素总数table（意味着其他元素存在于其他桶中）。
但是，您跳过了该段中的重要介绍：
If you use something like linear probing or double hashing, finding all the items that hashed to the same value means you need to hash the value, then walk through the "chain" of non-empty items in your table to find how many of those hashed to the same value. That's not linear on the number of items that hashed to the same value though -- it's linear on the number of items that hashed to the same or a colliding value.
Linear probing 是散列 table 的另一种实现，其中您不使用任何列表（链）进行碰撞。相反，您只需找到阵列中最近的可用点，从预期位置开始并向前移动。数组填充的越多，越有可能发现下一个位置也在被使用，所以你只需要继续搜索。这些位置由 散列为相同或冲突值 的项目使用，尽管您永远不会（并且您并不真正关心）这两种情况中的哪一种，除非您明确看到现有元素的哈希值。
This CppCon presentation video对hashtables做了很好的介绍和深入分析