Hash tables

Arrays:

  1. Random access.
  2. Fixed size.

Linked list:

  1. Not Random access.
  2. Not fixed size.

What we need is something that has random access and not fixed size.

Solution: Hash table

Hash

Uses a hash function to determine where to store a given key value.

Same hash function is used later to search for where a given key value is stored.

Collision:

If the hash output of two keys point to the same location.

Solution: each location has a linked list of values.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s