Hashing

In Python, the built-in hash() function can be used to generate hash codes for various data types. However, for the purpose of this explanation, we will focus on implementing a basic hash function from scratch.

Here's an example of a simple hash function in Python:

def custom_hash(key, size):
    hash_code = 0
    for char in key:
        hash_code += ord(char)
    return hash_code % size

In this example, the custom_hash() function takes a key and the size of the hash table as parameters. It calculates the hash code by summing the ASCII values of the characters in the key and then taking the modulo of the size to ensure it fits within the hash table's range.

Now let's solve a problem using hashing. The problem we'll solve is "Two Sum".

Problem Statement: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

nums = [2, 7, 11, 15]
target = 9

Output:

[0, 1]

Explanation: The numbers at indices 0 and 1 (2 and 7) add up to 9.

Solution: We can solve this problem efficiently using hashing. We'll iterate over the array and for each number, check if the complement (target - number) exists in our hash table. If it does, we've found the pair that adds up to the target. If not, we'll store the current number in the hash table for future lookups.

def two_sum(nums, target):
    hash_table = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_table:
            return [hash_table[complement], i]
        hash_table[num] = i
    return []

nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

In this solution, we initialize an empty hash_table to store the numbers and their indices as we iterate over the array. For each number, we calculate the complement and check if it exists in the hash table. If it does, we return the indices of the current number and its complement. Otherwise, we store the current number and its index in the hash table.

The time complexity of this solution is O(n) since we iterate over the array once. The space complexity is also O(n) since, in the worst case, we may need to store all the numbers in the hash table.