Explore

Data Structures and Algorithms

Hash Tables

Introduction to Hashing

Functions and Hashing

Functions:

Connect inputs to specific outputs.

Types:

One-to-One: Unique output per input.

Many-to-One: Multiple inputs map to the same output.

Hashing:

Transforms data into fixed-size output.

Produces consistent outputs for the same input.

Handles collisions when different inputs yield the same output.

Key Terms:

Hash Function: Converts input to fixed-size output.

Collision: Different inputs with the same output.

Cryptographic Hashing

Irreversibility: Hard to reverse-engineer input.

Pseudo-random Appearance: Consistent but appears random.

Collision Resistance: Difficult to find matching inputs.

Speed: Efficient hash generation is essential.

Applications

Passwords: Hashes with salt for security.

Git: Tracks file changes using hashes.

Blockchain: Secures transaction records.

Digital Signatures: Verifies document integrity.

Encrypted Communication: Ensures message confidentiality.

Hash Tables

Fast Retrieval Structures

Basic Data Structures:

List: Fast insertion, slow lookup.

Binary Search: Fast lookup with sorted data.

Hash Tables:

Uses hashing for efficient data storage/retrieval.

Handles collisions with chaining or open addressing.

Implementation

Structure:

Array of linked lists for key-value pairs.

Hash function determines bucket index.

Operations:

Put: Adds entries.

Get: Retrieves values.

Remove: Deletes entries.

Rehashing: Adjusts table size for load balancing.

Hash Functions and Collisions

Hash Functions

Purpose: Converts keys to practical integer values.

Methods:

Division Method: k mod m

Mid Square Method: Extracts middle digits from squared key.

Folding Method: Adds divided key parts, ignoring the last carry.

Collision Resolution

Techniques:

Separate Chaining: Uses linked lists.

Open Addressing: Finds next available slot.

For more detailed information, refer to the Notion link:

Hash Tables⁠

⁠

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.