Open Addressing (Hash Collision)

When hash collision happens, we keep looking to the next available index until we find an available index.

When looking for the next available index, we will follow a Probing Sequence.

To use Open Addressing (Hash Collision), we have to make sure that the table has enough space for us to find the next index. Therefore we need to consider Load Factor and Resize

Inserting an element

defaultSize = 4
hashTable = [0] * defaultSize

def insertOpenAddressing(key: string, value: any):
	x = 1
	index = hash(key)

	while (hashTable[index] != None):
		index = (index + P(x)) % defaultSize
		x += 1

	hashTable[index] = (key, value)

Where P(x) is one of the function from Probing Sequence.

Getting an element

defaultSize = 4
hashTable = [0] * defaultSize

def getOpenAddressing(key: string, value: any):
	x = 1
	index = hash(key)

	while (hashTable[index] != None and hashTable[index].key != key):
		index = (index + P(x)) % defaultSize
		x += 1

	return hashTable[index] if hashTable[index] else None

Problem

Probing Sequence > Cycle Problem