增加 HashSet 的容量会导致冲突吗？

Question

我正在尝试使用 C++ 向量作为基础数据结构来实现一个简单的 HashSet。为了简单起见，每当用户插入一个导致冲突的新元素时（即，当我尝试添加新元素的索引处已经存在另一个元素时，我将向量的大小加倍并重新散列所有现有元素元素）。这是通过我的函数 increaseCapacityAndRehash().

完成的

我的问题是：简单地将桶的数量（a.k.a。向量的大小）加倍的行为是否可能会在已经存在的元素之间引入冲突HashSet（假设在容量增加之前没有冲突）？ 如果是这样，我想每次我将桶的数量加倍时我都需要测试冲突，然后继续加倍直到有没有更多的碰撞。但我更愿意尽可能简化代码。

非常感谢提供证明！

作为参考，这是我将元素添加到我的 HashSet 的代码：

// Buckets that elements will be hashed into
struct Bucket
{
   Bucket() : value(0), isFilled(false) { }
   Bucket(int val) : value(val), isFilled(true) { }
   
   int value;
   bool isFilled;
};

// Underlying data structure for the hashset
std::vector<Bucket> buckets;

// Get the index at which a given element should be stored
std::size_t hash(int x)
{
   return std::abs(x) % buckets.size();
}

// Function to add elements to hash set
void add(int x)
{
   // Hash the element to determine which bucket to search
   std::size_t key = hash(x);
   
   // If the bucket is filled with some element other than x, then the new element creates collision
   if (buckets[key].isFilled && buckets[key].value != x)
   {
      // Double the capacity of the hash set until the collision goes away
      bool collisionExists = true;
      while (collisionExists)
      {
         increaseCapacityAndRehash();
         key = hash(x);
         if (!buckets[key].isFilled)
         {
            collisionExists = false;
         }
      }
   }
   
   // Add the new element to the hash set
   buckets[key].value = x;
   buckets[key].isFilled = true;
}

// Function to double the size of the vector and rehash all elements
void increaseCapacityAndRehash()
{
   // Save all elements currently in the hash set
   std::vector<int> save(size(), 0);
   for (std::size_t i = 0, save_i; i < buckets.size(); ++i)
   {
      // If element is a valid entry in the hash set, save it off
      if (buckets[i].isFilled)
      {
         save[save_i++] = buckets[i].value;
      }
   }
   
   // Double the number of buckets
   const std::size_t newCapacity = buckets.size() * 2;
   buckets = std::vector<Bucket>(newCapacity, Bucket());
   
   // Re-hash all elements
   for (int x : save)
   {
      const std::size_t key = hash(x);
      assert(buckets[key].isFilled == false);  // Can increasing number of buckets cause collisions???
      buckets[key].value = x;
      buckets[key].isFilled = true;
   }
}

Answer 1

如果将桶的数量加倍，您将不会遇到任何新的碰撞，但您可能无法解决当前的碰撞。

原始哈希值计算为

hash = x % N;

其中 x 是某个值，N 是桶的数量。当你把桶的数量加倍时，这就变成了

new_hash = x % (2*N);

new_hash 要么是 hash，要么是 hash + N。由于只有一个值具有哈希值 hash，而所有其他值的哈希值都小于 N，因此新值不会与任何其他新值发生冲突（可能除了之前的提到了新元素）。

另一种查看方式是两个哈希值之间的关系：

hash == new_hash % N

因此，如果任何新哈希值发生冲突，它们将与原始哈希值发生冲突。

但是，一般来说，哈希集可以容忍一定程度的冲突，因为冲突是不可避免的。增长不仅仅是桶数量的翻倍，而且新的哈希值可能会在它们最初没有发生冲突的地方发生冲突。

增加 HashSet 的容量会导致冲突吗？

Can increasing the capacity of a HashSet create Collisions?

c++

hashset

data-structures