Separate Chaining

In separate chaining we allow multiple keys to occupy one bucket.

We accomplish this by giving each bucket its own container to store keys. A linked list (a "chain") is most common, but we can certainly imagine other options. For our purposes, we will imagine a linked list.

We will assume that insert pushes the new key to the front of the list.

Here is our table using separate chaining after adding some additional keys:

bucket			key(s)
0		→	eggs
1		→	croissant	→	toast
2		→	bacon
3		→	cereal	→	avocado
4		→	juice	→	pancakes
5
6		→	coffee	→	milk	→	cheese
7		→	sausage
8		→	steak
9		→	waffles

Now, let's think about how bad things could possibly get…

Similarly, when we want to insert a key, we first have to check whether the key is already in the table—we don't want to add it twice to the same chain!

Since every INSERT starts with a LOOKUP, the worst-case time for INSERT is also \( \Theta(n) \).

Thus,

• The worst-case time for LOOKUP is \( \Theta(n) \).
• The worst-case time for INSERT is \( \Theta(n) \).

(When logged in, completion status appears here.)

Previous Page Go to Parent Page