Hashing

Flashcards about Hashing

Hashing Function

A method of storing data that converts keys (often strings) into integers for indexing a storage array.

Hash Table

Elements are stored in buckets; each element has a unique key; hash function generates a hash code to determine the bucket.

Hash Function

A function that maps keys to array indices (buckets).

Hashing Function

Compute indices to determine where entries will be stored and found.

Better Hashing Function

Using first four letters: index = L1 + L2×26 + L3×26^2 + L4×26^3.

Large Indices

index = rawIndex % size.

Hash Retrieval Stages

Two stages: compute index using hashing function and Search chain in array element for a match.

Key-Value Pair

Stores data where each element (the value) is associated with a unique identifier (the key).

Hash Table ADT

Stores key-value

Hash Table ADT Operations

put(t,

What happens if chains grow too long?

Becomes less efficient.

Summary of Hashing

To minimise collisions, use an array larger than the set of keys and ensure hashing minimize Collisions with a wide range of index values and uniform distribution.

FastHub

Open every weekday afternoon in B77 Infolab.

Hash function

Takes the key of an element to generate a hash code.

Chains

Are lists.