Hash table program in python - python coding

Hash table program in python - python coding


Published at - Sep 08, 2021

In this lesson on python coding, we will talk about one of the most famous, and fundamental algorithms in computer science Hash table. The hash table algorithm is a very common question for python coding interviews. This article will help if you are preparing for a python coding interview, so let's try to write a simple python program to implement the hashing in python.
 
These are some highlighted points about binary search algorithm
  • A Hash table is a collection of items and each position of the hash table, often called a slot.
  • The mapping between an item and the slot where that item belongs in the hash table is called the hash function.
  • Hash function formation methods include a folding method, mid-square method, linear probing, quadratic probing etc
  • The worst-case time complexity of the hash table is O(n)

Hash Search Example in Python

class HashTable:
	
	def __init__(self):
		# Size holds the hash table size, slots will hold the key items and data will hold the data values 
		# Size should a prime number so that the collision resolution algorithm can be as efficient as possible.
		self.size = 11
		self.slots = [None] * self.size
		self.data = [None] * self.size
	
	def hash_function(self,key,size):
		# Return remainder 
		return key%size
	
	def rehash(self,old_hash,size):
		# Linear probing with a +1
		return (old_hash+1)%size
	
	def put(self,key,data):
		# Find hash value
		hash_value = self.hash_function(key,len(self.slots))	
		if self.slots[hash_value] == None:
			self.slots[hash_value] = key
			self.data[hash_value] = data
		else:
			if self.slots[hash_value] == key:
				# replace
				self.data[hash_value] = data  
			else:
				next_slot = self.rehash(hash_value,len(self.slots))
				# Iterates the rehash function until an empty slot occurs
				while self.slots[next_slot] != None and self.slots[next_slot] != key:
					next_slot = self.rehash(next_slot,len(self.slots))	
				if self.slots[next_slot] == None:
					self.slots[next_slot]=key
					self.data[next_slot]=data
				else:
					self.data[next_slot] = data 
			
	def get(self,key):
		start_slot = self.hash_function(key,len(self.slots))
		data = None
		stop = False
		found = False
		position = start_slot
		while self.slots[position] != None and not found and not stop:
			if self.slots[position] == key:
				found = True
				data = self.data[position]
			else:
				# Read rehash function to get next slot
				position=self.rehash(position,len(self.slots))
				if position == start_slot:
					stop = True
		return data
	

# Testing    
H = HashTable()
H.put(11,"a")
H.put(22,"b")
H.put(24,"c")
H.put(32,"d")
H.put(52,"e")
H.put(43,"f")
print H.get(22)
print H.data
print H.slots

The above python program will put elements in the hash table and search for your given input in the sorted array and provides the boolean value if the given input is found in the given list or not.

Thank you for reading.



About author

Harendra
Harendra Kanojiya

Hi I'm Harendra Kumar Kanojiya. Currently I am FSD (Full-stack developer) and I have expertise with Angular ,PHP, Node JS, Laravel, Codeigniter and front end. Done few live projects and portfolio work in above.



Related Posts -

Follow Us

Follow us on facebook Click Here

Facebook QR
Scan from mobile
Join our telegram channel Click Here
Telegram QR
Scan from mobile