Search by Hashing

The Core Idea of Hashing

Hashing is a search technique designed to answer one question in a single step: Is this key present in the list? The logic is simple: if you already know exactly which index position every value should occupy, you can go straight to that spot and check. No scanning, no comparing with every element — just one direct look-up.

This makes hashing extremely efficient. The time it takes to search does not grow with the size of the list. Whether the list has 10 items or 10,000, a hash-based search takes the same constant amount of time.

The Hash Function and the Hash Table

The magic happens through a hash function — a formula that takes an element from the list and computes an index (a position) for it. The result of this computation is called the hash value.

All these computed positions together form a new structure called a hash table. Think of it as a fresh list (usually implemented as a Python list) where each index can hold only one item. The positions are numbered starting from 0. Importantly, the hash table can be larger than the original list — it has empty slots.

The Remainder Method (A Simple Hash Function)

For numeric data, a simple hash function is the remainder method. It divides an element by the size of the hash table, and the remainder becomes the hash value:

h(element) = element % size(hash table)

For example, if the hash table has 10 positions, the hash value for 34 is 34 % 10 = 4. So 34 goes into index 4.

Step-by-Step: Building a Hash Table

Let's walk through a worked example. We start with an empty hash table of size 10 — all positions hold None.

Now take the list [34, 16, 2, 93, 80, 77, 51]. Apply the hash function element % 10 to each:

• 34 % 10 = 4 → index 4
• 16 % 10 = 6 → index 6
• 2 % 10 = 2 → index 2
• 93 % 10 = 3 → index 3
• 80 % 10 = 0 → index 0
• 77 % 10 = 7 → index 7
• 51 % 10 = 1 → index 1

Insert each element at its computed index. The resulting hash table looks like this:

Notice indices 5, 8, and 9 remain empty — that's fine.

Searching with Hashing

To search for a key, you do not scan the hash table. Instead:

1. Compute the key's hash value using the same hash function.
2. Go directly to that index in the hash table.
3. Compare the value stored there with the key.

If they match, the key is present. If the slot is None or holds a different value, the key is absent. This is a single comparison — hence constant time, no matter how large the original list is.

The Python Program (Program 6-3)

#Function to check if a key is present or not
def hashFind(key,hashTable):
    if (hashTable[key % 10] == key): #key is present
        return ((key % 10)+1)   #return the position
    else:
        return None              #key is not present
#end of function

#create hashTable with 10 empty positions
hashTable=[None, None, None, None, None, None, None, None, None, None]
print("We have created a hashTable of 10 positions:")
print(hashTable)

L = [34, 16, 2, 93, 80, 77, 51]
print("The given list is", L[::] )

# Apply hash function
for i in range(0,len(L)):
    hashTable[L[i]%10] = L[i]

print("The hash table contents are: " )
for i in range(0,len(hashTable)):
    print("hashindex=", i," , value =", hashTable[i])

key = int(input("Enter the number to be searched:"))

position = hashFind(key,hashTable)
if position is None:
    print("Number",key,"is not present in the hash table")
else:
    print("Number ",key," present at ",position, " position")

Output:

We have created a hashTable of 10 positions:
[None, None, None, None, None, None, None, None, None, None]
The given list is [34, 16, 2, 93, 80, 77, 51]
The hash table contents are:
hashindex= 0  , value = 80
hashindex= 1  , value = 51
hashindex= 2  , value = 2
hashindex= 3  , value = 93
hashindex= 4  , value = 34
hashindex= 5  , value = None
hashindex= 6  , value = 16
hashindex= 7  , value = 77
hashindex= 8  , value = None
hashindex= 9  , value = None
Enter the number to be searched:16
Number  16  present at  7  position

The textbook provides a complete program that:

• Creates an empty hash table of 10 positions (all None).
• Takes a list L = [34, 16, 2, 93, 80, 77, 51].
• Inserts each element into the hash table using L[i] % 10 as the index. …