Hash Table

Hash Table
Published on 10 March, 2014
A hash table is a data structure that stores two components in each element, the key, and the
value. They can also be referred to as hash maps, dictionaries, or associative arrays. The
primary benefit of a hash table is the lookup speed. This is done by computing a key for each
element which is used for its index position; this process involves a hashing algorithm.
Definitions:
 Key – The index to a value in the hash table.
 Value – The value stored at a certain location in the hash table.
 Hash Algorithm – The process which takes a value, then performs an operation on it
to be used as an index location.
 Collision – When two different elements have the same key when being put through
the hash algorithm.
 Chaining – When elements with the same key are put into a list together; to solve
collision issues.
Operations:
 Create – Create a hash table.
 Delete – Deletes a value in the hash table.
 Insert – Inserts a value into the hash table.
 Get – Gets a value from the hash table.
Complexity:
Average Worst case
Space O(n) O(n)
Search O(1) O(n)
Insert O(1) O(n)
Delete O(1) O(n)
Diagram:
The above diagram shows how a hash table might be visualised. It also takes into
consideration of a hash collisions with Alice and Bob. When `Alice’ and `Bob’ is put through
the hashing algorithm, they both have the output key `3′, so they are then put into a list data
structure chaining them together. Then searching for their values later just means finding the
index, then searching through the linked list in a linear way. As collisions rarely occur, the
speed is still very fast for lookup using a hash table.
Filed in Computer Science Revision | No replies