C++ 代码查找哈希冲突的索引

2025 年 3 月 24 日 | 4 分钟阅读

在本文中，我们将讨论如何使用几个示例在 C++ 中查找哈希冲突的索引。

问题陈述

假设我们有一个数字 a 和一个包含 n 个元素的数组 P。有一个哈希表，其中包含 'a' 个桶，桶的编号从 0 到 (a-1)。我们的目标是添加数组 (P[]) 中的 (n) 个数字。我们假设哈希函数 (h(P[i]))，其中 (P(k) = k mod a)，将确定 (P[i]) 的桶。每个桶只能包含一个元素。

当我们尝试将一个新数字插入到一个已经满了的桶中时，就会发生 “冲突”。必须返回发生冲突的索引。如果没有冲突，则返回 -1。

算法 1

1. Import vectors, unordered sets, and IO libraries as needed.
2. Function findCollisionIndex (a, P):
            a. Create a blank set called buckets.
            b. For every item in the array P[k]:
                        i. Use the modulo operation to calculate the bucket for P[k]: bucket = P[k] % a.
                        ii. Return I as the collision index if the bucket is located within the set buckets.
                        iii. If not, place the bucket into the designated buckets.
c. Return -1 if, after processing every element, no collision is discovered.
3. Main function:
a. Declare the variables a and n; 
b. Read the input for a and n; 
c. Make an array P that is empty and has size n;
d. Read the input for the P elements. 
e. Make use of findCollisionIndex(a, P) and assign collisionIndex to the outcome.
f. If the collisionIndex is not equal to -1:
                       print- "Collision is found at index no: " + collisionIndex.
             g.otherwise,
 	           print- "No collision found".
4. End of Algorithm 

示例 1

让我们看一个 C++ 程序来查找哈希冲突的索引

#include<iostream>
#include<vector>
#include<unordered_set>
int findColl (int a, const std::vector<int>& P) {
    std::unordered_set<int> buckets; 
     for (int i = 0; i < P.size(); ++i)
      {
           int bucket = P[i] % a; 
           if (buckets.find(bucket) != buckets.end())
           {
            return i;
        }
        buckets.insert(bucket);
    }
    return -1; // No collision
}
int main() {
    int a;
    std::cout << "Enter the number of buckets (a): ";
    std::cin >> a;
    int n;
    std::cout << "Enter the number of elements in the array (n): ";
    std::cin >> n;
    // Input the elements of the array (P)
    std::vector<int> P(n); 
    std::cout << "Enter the elements of the array:" << std::endl; 
    for (int i = 0; i < n; ++i) {
        std::cin >> P[i];
    }
    int collisionIndex = findColl(a, P);
    if (collisionIndex != -1) {
        std::cout << "Collision found at index: " << collisionIndex << std::endl;
    } else {
        std::cout << "No collision found." << std::endl;
    }
    return 0;
}

输出

C++ code to find an index where this is a hash collision

算法 2

a:= size of P 
Create an array called Arr with the size n, then fill it with ?0? 
initialize: i = 0; when i < n, update (increase I value by 1), do: 
z = P[i] 
If Arr[z mod n] is not equal to zero,
then 
                return i
            increase  Arr[z mod n] by 1
return i 

示例 2

让我们看另一个 C++ 程序来查找 哈希冲突 的索引：

#include<iostream>
#include<vector>
#include<unordered_set>
int findCollisionIndex(int n, const std::vector<int>& P) 
{
       std::vector<int> arr(n, 0); 
       for (int i = 0; i < P.size(); ++i) 
       {
        int z = P[i];
        int bucket = z % n;
        if (arr[bucket] != 0) {
            return i;
        }
        arr[bucket]++;
    }
    return -1;
}
int main() {
    int n, x;   
    // Input the number of buckets (n)
    std::cout << "Enter the number of buckets (n): ";
    std::cin >> n;
    // Input the number of elements in the array (x) 
    std::cout << "Enter the number of elements in the array (x): ";
    std::cin >> x;
    // Input the elements of the array (P)
    std::vector<int> P(n); 
    std::cout << "Enter the elements of the array:" << std::endl; 
    for (int i = 0; i < x; ++i) {
        std::cin >> P[i];
    }
    // Find the collision index and print the result
    int collisionIndex = findCollisionIndex(n, P);
    if (collisionIndex != -1) {
        std::cout << "Collision found at index: " << collisionIndex << std::endl;
    } else {
        std::cout << "No collision found." << std::endl;
    }
    return 0;
}

输出

结论

总而言之，我们可以得出结论，通过使用上述技术来查找冲突，我们可以避免数据丢失或混淆。哈希表可以通过高效的冲突检测可靠有效地管理数据，这使其成为处理大型应用程序中数据的可靠资源。

下一主题格规约算法在 C++ 中的实现

C++ 代码查找哈希冲突的索引

问题陈述

算法 1

示例 1

算法 2

示例 2

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 代码查找哈希冲突的索引

问题陈述

算法 1

示例 1

算法 2

示例 2

结论

相关帖子

C++ 中计算启示录数序列

C++ 中的 ChaCha20 流密码

C++ 中的 HITS 算法

C++ 中的霍纳克素数

C++ STL 中 deque::assign 和 deque::at 之间的区别

C++ 中的二十一面体数

C++ 中查找第 n 个埃尔米特数

C++ 中检查主教是否可以吃掉兵

C++ 粉笔盒 XOR 游戏

C++ 中的莫茨金数

订阅 Tpoint Tech

联系信息

关注我们

教程