Computer scienceAlgorithms and Data StructuresAlgorithmsPrinciples and techniquesHashing

Hash table

Theory

Time to find an element

Report a typo

Say we have the following hash table, with hash function h(x)=x % 13h(x) = x\ \%\ 13:

0

1

2

3

4

{0, 13, 5}

{6, 14}

{2}

{8, 16}

{22}

Searching for an element within a bucket goes from left to right, in the order they are written. What is the maximum number of steps needed to check if a number is in this hash table?

By step we mean:

  1. computing the hash value of a number,

  2. or, checking for equality between two numbers.

Hint: Maximum number of steps needed would be when either an element is the last element in the maximum element bucket, or it's not present in that bucket.

Enter a number
___

Create a free account to access the full topic