Fundamentals of Programming III: Data Structures

These flashcards cover key concepts and terminology related to hash tables as discussed in the lecture.

Hash Table

A data structure that maps keys to values, also called associative arrays.

Bucket

An element location in the hash table.

Hashing

The process of converting a key to a valid index.

Load Factor

The number of items divided by the number of buckets in a hash table.

Collision

Occurs when two keys hash to the same bucket.

Chaining

A collision handling strategy where each bucket holds a linked list of entries.

Linear Probing

A collision resolution method where we step through buckets one by one.

Quadratic Probing

A probing method where the step size increases quadratically to reduce clustering.

Double Hashing

A probing sequence that uses a second hash function to determine the step size.

Perfect Hash Function

A hash function that maps each key uniquely without collisions.

ESS (Empty Since Start)

Indicates that no element has ever been stored at a particular location.

EAR (Empty After Removal)

Indicates that a location was once occupied but is now empty.

Collision Handling Strategy

Techniques used to resolve collisions in hash tables, such as chaining and open addressing.

Resize

The process of creating a new hash table when the current one is full.

Common Hash Function

Functions used in a hash table to determine the index for a given key, such as division and multiplication methods.

Runtime Complexity for Insertions (Chaining)

Expected time O(1 + α) where α is the load factor.

Clustering

Occurs when multiple keys in a hash table occupy adjacent buckets, hindering performance.

Threshold

A value that must be exceeded for an action to be triggered in hash tables.