Page 193 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms Anil Sharma, Lovely Professional University

Notes Unit 9: Hashing

CONTENTS

Objectives
Introduction
9.1 Hashing
9.1.1 Linear Probing or Linear Open Addressing
9.1.2 Rehashing

9.1.3 Overfl ow Chaining
9.2 Hash Functions
9.3 Open Hashing
9.4 Closed Hashing

9.5 Rehashing
9.6 Summary
9.7 Keywords
9.8 Self Assessment
9.9 Review Questions

9.10 Further Readings

Objectives

After studying this unit, you will be able to:
Explain the concept of hashing
Know of hash functions

Realise open hashing and closed hashing
Describe rehashing

Introduction

The search time of each algorithm depend on the number n of elements of the collection S of the
data. A searching technique called Hashing or Hash addressing which is essentially independent
of the number n.
Hashing is the transformation of a string of characters into a usually shorter fixed-length value or

key that represents the original string. Hashing is used to index and retrieve items in a database

because it is faster to find the item using the shorter hashed key than to find it using the original
value. It is also used in many encryption algorithms.
A Hash Function is a Unary Function that is used by Hashed Associative Containers: it maps its
argument to a result of type size_t. A Hash Function must be deterministic and stateless. That
is, the return value must depend only on the argument, and equal arguments must yield equal
results.

188 LOVELY PROFESSIONAL UNIVERSITY