Page 234 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

A linked list or a binary search tree can be used. An array can be used which can be efficient than Notes
the previous two but storing 10,000 students information will need a lot of memory for an array.
The best technique to search in efficient time in this type of situation is hashing with minimum
wastage of memory.
We need to know about two important features that will be used during hashing:

Hash Table
Hash Function
The idea is simple in hashing is to use hash function to map keys (data to be searched) in the hash
table. Let’s first know what exactly a hash table & hash function is.

13.5.1 Hash Table

All the large collection of data are stored in a hash table. The size of the hash table is usually
fixed and it is always bigger than the number of elements we are going to store. The load factor
defines the ratio of the number of data to be stored to the size of the hash table. Hashing is the
procedure of inserting and searching a data from the hash table in optimal time.

For storing a element in the hash table, we assign a key to each element that is inserted. This key
is the important criteria in a hash table which allows searching to be performed much faster.
Hash tables are generally array of cells of fixed size containing data. This key is helpful in
mapping the element to be searched in the hash table.

Figure 13.4: Hash Table

Index Values

1 Apple
2 Orange
3 Mango
4 Grapes
5 Pineapple
6
7 Banana
8
9

Source: http://newtonapples.com/understanding-hashing-in-c-language/
The above figure shows a sample hash table whose size is 9 and there are 7 elements stored
currently. The first column ranging from 1 to 9 are the INDEX assigned to all the individual
elements and the second column are the specific values stored in a hash table.

13.5.2 Hash Function

The element that is to be retrieved from the hash table is known as a key. A hash function helps
in connecting a key to the index of the hash table. The key can be a number or string. A hash
function should be perfect in storing the elements in the exact index in the hash table and tell us
where to retrieve the searched data from the table. A hash function should be easy and quick to
compute.

LOVELY PROFESSIONAL UNIVERSITY 227