Page 95 - Data Structures Handout_Neat

Chapter 9

9.1 Introduction to Hashing

Hashing is a fundamental technique in computer science used to achieve fast data

access and efficient storage. At its core, hashing involves applying a hash function to input

data (called a key) to produce a numerical value known as a hash code or hash value. This
value is then used as an index to store or retrieve the data in a hash table. The primary

motivation behind hashing is speed: while searching in arrays or linked lists can take linear

time, hashing allows constant-time average performance for insertion, deletion, and lookup

operations.

Hashing is widely used in real-world applications. For example, databases use hashing
to quickly locate records, compilers use hashing to manage symbol tables, and operating

systems use hashing for memory management and caching. In security, cryptographic hash

functions are used to store passwords securely and verify data integrity. The versatility of
hashing makes it one of the most important concepts in data structures and algorithms.

9.1.1 Definition and Motivation

A hash function is a mathematical function that maps input data of arbitrary size to a

fixed-size output. The output is typically an integer that serves as an index in a hash table. The
key idea is that instead of searching through all data, we can directly compute where the data

should be stored or found.

The motivation for hashing comes from the need for efficiency. Consider searching for

a student record in a university database. Without hashing, we might need to scan through

thousands of records. With hashing, the student’s ID can be passed through a hash function
to directly compute the location of the record, reducing search time dramatically.

9.1.2 Real-World Applications of Hashing

Hashing is everywhere in computing:

• Databases: Hashing is used in indexing to quickly locate records.
• Password Storage: Cryptographic hash functions store passwords securely by

95