#include <functional> // std::hash
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
/*
Computes a hash value for a string.
std::hash is the standard hashing facility used by
containers such as std::unordered_map and std::unordered_set.
Important:
- Hashes are useful for fast lookups.
- Different strings can theoretically produce the same hash.
- Therefore, hashes alone should not be used to determine
whether two strings are identical.
*/
std::size_t hashString(const std::string& text)
{
return std::hash<std::string>{}(text);
}
/*
Checks whether a hash collision has occurred.
A collision occurs when:
hash(A) == hash(B)
but:
A != B
We store the original string for each hash value and
compare strings when a matching hash is found.
*/
void insertAndCheckCollision(
const std::string& text,
std::unordered_map<std::size_t, std::string>& hashTable)
{
const std::size_t hashValue = hashString(text);
std::cout << "String: \"" << text << "\"\n";
std::cout << "Hash : " << hashValue << '\n';
auto it = hashTable.find(hashValue);
if (it == hashTable.end())
{
// First time this hash has been seen.
hashTable[hashValue] = text;
std::cout << "Status: Stored successfully.\n\n";
return;
}
/*
A matching hash already exists.
Now compare the actual strings. A matching hash
does not necessarily mean the strings are identical.
*/
if (it->second == text)
{
std::cout << "Status: Same string already exists.\n\n";
}
else
{
std::cout << "Status: HASH COLLISION DETECTED!\n";
std::cout << "Existing string: \"" << it->second << "\"\n";
std::cout << "New string : \"" << text << "\"\n\n";
}
}
int main()
{
/*
Example data.
In real applications, collisions with std::hash
are relatively uncommon, so this sample focuses on
demonstrating the correct detection logic rather
than guaranteeing a collision.
*/
std::vector<std::string> strings =
{
"apple",
"banana",
"orange",
"apple" // Duplicate string
};
/*
Maps:
hash value -> original string
Keeping the original string allows us to verify
equality and detect collisions correctly.
*/
std::unordered_map<std::size_t, std::string> hashTable;
for (const auto& text : strings) {
insertAndCheckCollision(text, hashTable);
}
}
/*
run:
String: "apple"
Hash : 13776597747624572848
Status: Stored successfully.
String: "banana"
Hash : 4209850087293805843
Status: Stored successfully.
String: "orange"
Hash : 12623290586017486571
Status: Stored successfully.
String: "apple"
Hash : 13776597747624572848
Status: Same string already exists.
*/
