Hash Table in Data Structure and Algorithm

Hash Tables




Chapter 13

,Outline
●
Introduction
– Dictionaries
●
Hash Table Structure
●
Hash Functions
– Building hash functions
●
Linear open addressing
– Operations on linear open addressed hash tables
– Performance analysis
– Other collision resolution techniques with open addressing
●
Chaining
– Operations on chained hash tables
– Performance analysis
●
Applications

, Introduction
● Dictionary is a collection of data elements
uniquely identified by a field called key.
● A dictionary supports the operations of search,
insert and delete. The ADT of a dictionary is
defined as a set of elements with distinct keys
supporting the operations of search, insert, delete
and create (which creates an empty dictionary).
● A dictionary supports both sequential and
random access
● Hash tables are ideal data structures for
dictionaries