+
CS310 – Data Structure
Lecture – 12 – Hash Tables
+ 2
Maps
A map is an abstract data type designed to efficiently store and retrieve
values based upon a uniquely identifying search key for each. Specifically, a
map stores key-value pairs (k,v), which we call entries, where k is the key
and v is its corresponding value. Keys are required to be unique, so that the
association of keys to values defines a mapping.
Figure 10.1:
A conceptual illustration of the map ADT.
Keys (labels) are assigned to values
(folders) by a user. The resulting entries
(labeled folders) are inserted into the
map (file cabinet).
The keys can be used later to retrieve or
remove values.
February 2, 2025
+ 3
What is Hash table?
In CS, a hash table, or a hash map, is a data structure that associates
keys with values .
Example:
A small phone book as a hash table.
February 2, 2025
+ 4
Hash Table Data Structure
Hash Table is a data structure which stores data in an associative manner. In a
hash table, data is stored in an array format, where each data value has its
own unique index value.
Access of data becomes very fast if we know the index of the desired data.
Thus, a faster search technique.
Hash Table uses an array as a storage medium and uses hash algorithm to
generate an index where an element is to be inserted or is to be located from.
Hashing is a technique to convert a key value into an index of an array using
a specific hash function.
Video: https://www.youtube.com/watch?v=KyUTuwz_b7Q
February 2, 2025
+ 5
Hash Table using Array Example
The Hash table consist of array of records Record
Each record has a special field, called its key. ID(KEY)
Suppose the key is a person's identification Person’s Info
number, and the rest of the record has
information about the person.
This hash table has 701 records
506643548 233667136
.... Person’s Person’s
Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 6
Insert a new record
In order to insert a new record, the key must New Record
somehow be converted to an array index.
ID=5806256
The index is called the hash value of the key. 85
Person’s Info
Typical way create a hash value:
Hash value (index) = (ID number mod size)
(580625685 mod 701) = 3
506643548 580625685 233667136
.... Person’s Person’s Person’s
Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 7
Collisions
Here is another new record to insert, with a hash value of New Record
2.
(701466868 mod 701) = 2 ID=7014668
68
Person’s Info
This is called a collision, because there is already another
valid record at [2].
When a collision occurs, move forward until you find an
empty spot.
506643548 580625685 233667136
.... Person’s Person’s Person’s
Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 8
Collisions
Here is another new record to insert, with a hash value of New Record
2.
(701466868 mod 701) = 2 ID=7014668
68
Person’s Info
This is called a collision, because there is already another
valid record at [2].
When a collision occurs, move forward until you find an
empty spot.
701466868 506643548 580625685 233667136
.... Person’s Person’s Person’s Person’s
Info Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 9
Searching for a key
key:
Calculate the hash value.
506643548
(506643548 mod 701) = 4
Check that location of the array for the key.
The keys are
equal
701466868 506643548 580625685 233667136
.... Person’s Person’s Person’s Person’s
Info Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 10
Searching for another key
key:
Calculate the hash value.
701466868
(701466868 mod 701) = 2
Check that location of the array for the key.
The keys are 701466868 != 233667136
not equal
701466868 506643548 580625685 233667136
.... Person’s Person’s Person’s Person’s
Info Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 11
Searching for a key
key:
Move forward and check the next index
701466868
The keys are 701466868 != 580625685
not equal
701466868 506643548 580625685 233667136
.... Person’s Person’s Person’s Person’s
Info Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 12
Searching for a key
key:
Move forward and check the next index
701466868
The keys are 701466868 != 506643548
not equal
701466868 506643548 580625685 233667136
.... Person’s Person’s Person’s Person’s
Info Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 13
Searching for a key
key:
Move forward and check the next index
701466868
Here the key 701466868 == 701466868
found in index 5
701466868 506643548 580625685 233667136
.... Person’s Person’s Person’s Person’s
Info Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 14
Deleting a Record
Records may also be deleted from a hash table.
But the location must not be left as an ordinary "empty
spot" since that could interfere with searches.
(Remember that a search can stop when it reaches an empty
spot.)
Delete this
record
701466868 506643548 580625685 233667136
.... Person’s Person’s Person’s Person’s
Info Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 15
Deleting a Record
The location must be marked in some special way so
that a search can tell that the spot used to have
something in it.
In any case, a search can not stop when it reaches "a
location that used to have something here". A search can
only stop when it reaches a true empty spot.
701466868 580625685 233667136
.... Person’s Person’s Person’s
Info Info Info
[700] [5] [4] [3] [2] [1] [0]
February 2, 2025
+ 16
Hash Table implementation using Array
Causes Collision
February 2, 2025
Hash Table implementation using Separate
+ Chaining 17
(or a Linked List)
Closed Addressing
This method was developed to avoid collision in the previous method
February 2, 2025
+ 18
Example
February 2, 2025
+ 19
Summary
Hash tables store a collection of records with keys.
The location of a record depends on the hash value of the record's key.
When a collision occurs, the next available location is used.
Searching for a particular key is generally quick.
When an item is deleted, the location must be marked in a special way, so that
the searches know that the spot used to be used.
Implementing Hash Table using Separate Chaining (or a Linked List) to avoid
collision.
February 2, 2025
+ 20
References
https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.h
tm
https://docs.oracle.com/javase/8/docs/api/java/util/Hashtable.html
https://www.geeksforgeeks.org/implementing-our-own-hash-table-with-separate-
chaining-in-java/
https://www.geeksforgeeks.org/hashtable-in-java/
https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html
Chapter 10 of the course textbook
February 2, 2025
+ 21
End of Hash Tables
February 2, 2025
