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
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
