data structures and algorithms

DATA STRUCTURE http://www.youtube.com/c/EDULINEFORCS
STUDENT




MODULE 5
SORTING & HASHING




Prepared By Mr. EBIN PM, AP, IESCE 1




HASHING
Hash Tables
• 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.
• Hashing function is used to implement hash table
• Hash function returns a location in hash table
• Hash table contains buckets

Prepared By Mr.EBIN PM, AP, IESCE EDULINE 2




Prepared By Mr. EBIN PM, AP, IESCE

, DATA STRUCTURE http://www.youtube.com/c/EDULINEFORCS
STUDENT




• Hash value is a bucket address of hash table
• One bucket can store more than one values
• N number of record can be stored in one bucket.
• One bucket has number of slots. In 2 slotted hash table, one bucket
contains 2 values.
n = number of key values
b = number of buckets
s = number of slots
∴ identifier density = n/T, where T is total number of possible
identifiers. And
Loading factor = n/sb
Prepared By Mr.EBIN PM, AP, IESCE EDULINE 3




Consider 2 identifiers I₁ and I₂.
I₁ and I₂ are applied on a same hashing function and produce same
bucket address. So I₁ and I₂ stored in same bucket. Then this
identifier is called “synonyms”
0 I₁ I₂ Synonyms
1
2
. 2 slotted hash table. Hash table with 26 buckets and
. two slots per bucket
.
25



Prepared By Mr.EBIN PM, AP, IESCE EDULINE 4




Prepared By Mr. EBIN PM, AP, IESCE