HASH TABLE IN DATA

STRUCTURE

INTORUCTION

BY:OFONDO SMITH 11/22/2024

 What is Hash Table?
2

 A Hash table is defined as a data structure used

to insert, look up, and remove key-value pairs

quickly.
 It operates on the hashing concept, where each

key is translated by a hash function into a distinct

index in an array.
 The index functions as a storage location for the

matching value. In simple words, it maps the keys

with the value.
BY:OFONDO SMITH 11/22/2024
 The Concept Of Hashing
3

 Hashing refers to the process of generating a

fixed-size output from an input of variable size

using the mathematical formulas known as hash
functions. This technique determines an index or
location for the storage of an item in a data
structure.

BY:OFONDO SMITH 11/22/2024

 COMPONENTS OF HASING
4

BY:OFONDO SMITH 11/22/2024

 COMPONENTS………………CON’D
5

 Key: A Key can be anything string or integer which

is fed as input in the hash function the technique

that determines an index or location for storage of
an item in a data structure.
For Example:
20,30,29,70,54,89,56 (integer)
Or: Guma, Wa ,Duke, Smith
(strings)
BY:OFONDO SMITH 11/22/2024
 COMPONENTS………………CON’D
6

 Hash Table: Hash table is a data structure that

maps keys to values using a special function called

a hash function. Hash stores the data in an
associative manner in an array where each data
value has its own unique index.

BY:OFONDO SMITH 11/22/2024

 Hash Function
7

 Hash Function: The hash function receives the

input key and returns the index of an element in an

array called a hash table. The index is known as
the hash index.
 When selecting hash function to use , consider the

criteria below;
1) Function should be easy and quick to

compare
2) Minimum
BY:OFONDO SMITH number of collision it may cause
11/22/2024
 Types of hash function
8

 There are three commonly used hash functions as

stated below;
Division methods
 It’s given by ; h(k)=k mod m
 For alphanumeric :
 h(k) = sum of ASCII code mod size of the array
 (American Standard Code for Information Interchange)

 Where; k =given keys, and m = size of the hash table

 Work example: Given 10, 11 ,12 , 13 ,and 14 , insert

them into a hash table of 5 indexes.

BY:OFONDO SMITH 11/22/2024

More example on division method……..
9

11/22/2024
 Types of hash function
10

Folding methods
 Here keys are partitioned in to parts and the each
part are added together

 It’s given by ; h(k) = k1 + k2 +k3+……………….

+kn

 Where: k = the part of the key partitioned

Work example: Given 10, 21 ,and 11 , insert them

into a hash table of 5 indexes.
BY:OFONDO SMITH 11/22/2024
 Types of hash function
11

Mid square method

 It’s given by ; h(k) = l

 Here, key is squared (k^2 ) and

 l is obtained by deleting digit from both end of k^2

 Work example: Given 10, 21 ,and 11 , insert them

into a hash table of 5 indexes.

BY:OFONDO SMITH 11/22/2024

 COLLISION IN HASH TABLES
12

 The hashing process generates a small number for

a big key, so there is a possibility that two keys

could produce the same value.
 Collision: The situation where the newly inserted

key maps to an already occupied index in the hash

table.
 It must be handled using some collision handling

technology.
BY:OFONDO SMITH 11/22/2024
 Collision In Hash Table…………con’d
13

BY:OFONDO SMITH 11/22/2024

 COLLISION RESOLUTION TECHNIQUES
14

Collisions happen when two or more keys

point to the same array index. It has some

resolution technique such as:
Separate chaining

open addressing

BY:OFONDO SMITH 11/22/2024

 Open Addressing
15

 collisions are handled by looking for the following

empty space in the table. If the first slot is already

taken, the hash function is applied to the subsequent
slots until one is left empty.
 There are various ways to use this approach, including

 Double Hashing,

 Linear Probing, And

 Quadratic Probing.

BY:OFONDO SMITH 11/22/2024

 Open Addressing

16

Double Hashing:
 Double hashing is a collision resolution technique used

in hash tables. It works by using two hash functions to

compute two different hash values for a given key.
 The first hash function is used to compute the initial

hash value, and the second hash function is used to

compute the step size for the probing sequence.

BY:OFONDO SMITH 11/22/2024

 Work example on double hashing
17

1. Use division method to and double hashing

method to insert the following given keys

k=3 ,2 ,9 ,6 ,11 ,13 ,7 ,12 using h1(k)=2k+3
and h2(k)=3k +1 and mode (m)=10
Solution:
Insert k at the first free place from (u +v * i)%m
Where : v = h2(k)%m and i=0,…….(m-1)

BY:OFONDO SMITH 11/22/2024

 Open Addressing
18

 Linear Probing:
 This involves doing a linear probe for the following slot

when a collision occurs and continuing to do so until an

empty slot is discovered.
 Strategy:

It uses hash function to find index for a key

If that spot contain a value , use the next available spot

(higher index). If you reach the end of the array, go back to
the front
BY:OFONDO SMITH 11/22/2024
 Work example on Linear Probing

19

 Insert the following number into a hash table

of size 5 using the hash function h(k) = key

%5. show the result when collusion are
resolved
Number:10 ,11 ,12 ,15
Step:
Let us do it together

BY:OFONDO SMITH 11/22/2024

 Open Addressing

20

 Quadratic Probing:
 Quadratic probing is an open addressing scheme where we look for the i2‘th slot in the i’th iteration if

the given hash value k collides in the hash table.

 Steps:

1. Set i to 0 that is to say, i=0

2. Get the hash value h(k) = (k +j^2 ) % table size

3. If hash table [h(k)] is empty, insert the key and stop else the space is occupied ,we must

find next available space.

i. Increase i by 1

ii. Compute the new has value, h(k) = (k + i^2) % size of the table

iii. Repeat step 3 until i is equal to table size

4. The hash table is full

5. stop

11/22/2024
 Work example on Quadratic Probing
21

 Insert the following number into a hash table

of size 7 using the hash function h(k) =key %

7. show result when collision are resolved.
Numbers: 76, 40, 48, 5, 20
 Solution:

 Let us do it together please

BY:OFONDO SMITH 11/22/2024

 Separate chaining
22

 In separate chaining, a linked list of objects that hash to

each slot in the hash table is present. Two keys are

included in the linked list if they hash to the same slot. This
method is rather simple to use and can manage several
collisions.
 The linked list data structure is used to implement this

technique. So what happens is, when multiple elements are

hashed into the same slot index, then these elements are
inserted into a singly-linked list which is known as a chain.

BY:OFONDO SMITH 11/22/2024

 Separate chaining
23

For example: Let us consider a simple hash

function as “key mod 5” and a sequence of keys as

12, 22, 15, 25
 Solution:

BY:OFONDO SMITH 11/22/2024

BY:OFONDO SMITH 24 11/22/2024
BY:OFONDO SMITH 25 11/22/2024
BY:OFONDO SMITH 26 11/22/2024
BY:OFONDO SMITH 27 11/22/2024
 Example 2:
28

BY:OFONDO SMITH 11/22/2024

 Applications of Hash Table:

29

 Hash tables are frequently used for indexing and

searching massive volumes of data. A search
engine might use a hash table to store the web
pages that it has indexed.

 Data is usually cached in memory via hash tables,

enabling rapid access to frequently used
information.

 Hash functions are frequently used in cryptography

to create digital signatures, validate data, and
guarantee data integrity.
11/22/2024
 Applications of Hash Table:

30

 Used in some programming languages like Python,

JavaScript hash is used to implement objects.

 Distributed systems: Hashes are used in distributed

systems to assign work to different nodes or servers. For
example, a load balancer might use a hash to distribute
incoming requests to different servers based on the request
URL or other criteria.

 File systems: Hashes are used in file systems to quickly

locate files or data blocks. For example, a file system might
use a hash to store the locations of files on a disk, with the
keys being the file names and the values being the disk
locations.
BY:OFONDO SMITH 11/22/2024
 Advantages of hash data structure
31

 Fast lookup: Hashes provide fast lookup times for elements,

often in constant time O(1), because they use a hash function to
map keys to array indices. This makes them ideal for
applications that require quick access to data.

 Efficient insertion and deletion: Hashes are efficient at

inserting and deleting elements because they only need to
update one array index for each operation. In contrast, linked
lists or arrays require shifting elements around when inserting
or deleting elements.

 Space efficiency: Hashes use space efficiently because they

only store the key-value pairs and the array to hold them. This
can be more efficient than other data structures such as trees,
which require additional memory to store pointers.
BY:OFONDO SMITH 11/22/2024
 Advantages……………
32

Flexibility: Hashes can be used to store any

type of data, including strings, numbers, and
objects. They can also be used for a wide variety
of applications, from simple lookups to complex
data structures such as databases and caches.

Collision resolution: Hashes have built-in

collision resolution mechanisms to handle cases
where two or more keys map to the same array
index. This ensures that all elements are stored
and retrieved correctly.

BY:OFONDO SMITH 11/22/2024

 Disadvantages of hash data structure
33

 Hash is inefficient when there are many collisions.

 Hash collisions are practically not be avoided for large

set of possible keys.

 Hash does not allow null values.

 Hash tables have a limited capacity and will eventually

fill up.

 Hash tables can be complex to implement.

 Hash tables do not maintain the order of elements,

which makes it difficult to retrieve elements in a

BY:OFONDO SMITH 11/22/2024
BY:OFONDO SMITH 34 11/22/2024