What is a collision in the context of programming and databases?

• In programming: a situation where two or more different elements are assigned the same identifier or key.
• In databases: occurs when using hash indexes, where the hash function generates the same hash value for different data keys. This requires additional mechanisms to resolve the conflict (e.g., chaining or open addressing) to ensure unique data access.

Examples:

• Hash table: Two different keys have the same hash.

# Example of collision in a hash table (simplified)
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size # Hash function

    def insert(self, key, value):
        index = self._hash(key)
        # Collision if the list at this index already contains elements
        self.table[index].append((key, value))

ht = HashTable(10)
ht.insert("apple", 1)
ht.insert("banana", 2)
# Assume hash("apple") % 10 == hash("orange") % 10
ht.insert("orange", 3) # Possible collision

• Hash index in a DB:

-- Example of creating a hash index in PostgreSQL
CREATE INDEX idx_hashed_column ON my_table USING hash (hashed_column);
-- If two values in hashed_column have the same hash, a collision occurs

Collision resolution methods:

• Chaining method: Each record in the hash table or index stores a list (linked list or array) of elements with the same hash.
• Open addressing method: When a collision occurs, the next free space in the table is searched (linear, quadratic probing, or double hashing).

Collision resolution method	Advantages	Disadvantages
Chaining	Simple to implement, works well under high load	Requires additional memory for lists
Open addressing	Uses less memory under low load	Sensitive to load factor, can lead to clustering