Hashing, Hash Tables and Map (ADT)

This flashcard set covers key concepts related to hashing, hash tables, and the Map abstract data type as discussed in the lecture.

Map (ADT)

An abstract data type that stores key-value (k,v) pairs without duplicate keys.

Hashing

The process of mapping a set of items of any size to a fixed-size set of values using a hash function.

Hash Function

A function that converts an input (or 'key') into a numerical value that represents a location in a hash table.

Collision

Occurs when two keys hash to the same index in a hash table, leading to potential data loss unless handled correctly.

Closed Addressing (Chaining)

A collision resolution method where each bucket contains a linked list of elements that hash to the same index.

Open Addressing

A collision resolution method where all elements are stored directly in the hash table with probing to find empty slots.

Linear Probing

A method in open addressing for resolving collisions by checking subsequent slots in the array until an empty slot is found.

Resizing

The process of increasing the size of the hash table to accommodate more entries, typically triggered when a certain load factor is reached.

Load Factor

A measure of how full the hash table is, defined as the number of occupied buckets divided by the total number of buckets.

Good Hash Function

A hash function that distributes keys uniformly across the hash table, minimizing collisions.