Hashing,Sets,Maps

The process of converting a given key into another value using a hash function.

Hashing

A data structure that maps keys to values using a hash function for fast operations.

Hash Table

The mathematical function used to generate a hash value from a key.

Hash Function

The formula used to determine the index or position where data is stored.

h(k) = k mod m or index = hash(key) % array_size

The array position where a key-value pair is stored.

Bucket

The part of hashing where the index determines which bucket will hold the key-value pair.

Storage in Buckets

The key-value structure used to store data in hash tables.

Key-Value Pair

The process of adding a new key-value pair into the hash table.

Insertion

The process of finding or getting the value associated with a key.

Retrieval

The process of deleting a key-value pair from the hash table.

Deletion

The operation that checks if a given key exists in the table.

Checking

The Java class used to implement a hash table-based map.

HashMap

The Java method used to insert a key-value pair in a HashMap.

put(key, value)

The Java method used to retrieve a value using its key.

get(key)

The Java method used to remove a key-value pair.

remove(key)

The Java method that checks if a specific key exists.

containsKey(key)

A real-life analogy used for hashing that compares it to a library with numbered shelves.

Library Analogy

The process of determining how the hash table is structured, sized, and organized.

Table Design

The act of two different keys producing the same hash value.

Collision

The measure of how full a hash table is, calculated as entries divided by buckets.

Load Factor

The process of creating a larger table and recomputing indices when the load factor is too high.

Rehashing

The number of available slots or array positions in a hash table.

Table Size

A recommended kind of number to use for table size to reduce clustering.

Prime Number

The property of a good hash function that ensures the same key always yields the same hash.

Determinism

The property of a good hash function that distributes keys evenly across buckets.

Uniform Distribution

The property of a good hash function that allows quick computation.

Efficiency

The data-holding unit or slot in a hash table that can contain one or more key-value pairs.

Bucket

The method of handling collisions by storing multiple elements in the same bucket using a linked list.

Chaining

The collision handling method where each bucket holds only one entry and another slot is searched if full.

Open Addressing

The open addressing method that checks the next slot sequentially.

Linear Probing

The open addressing method that checks slots using quadratic steps to reduce clustering.

Quadratic Probing

The open addressing method that uses a second hash function to determine the step size.

Double Hashing

The process of adjusting or increasing the table size when the load factor exceeds a certain threshold.

Resizing / Rehashing

The situation when two or more keys are assigned to the same index or bucket.

Collision

The technique that handles collisions by using linked lists or trees in each bucket.

Chaining

The data structure often used in chaining to link multiple key-value pairs.

Linked List

The data structure sometimes used instead of a linked list when a bucket list gets too long.

Balanced Tree

The technique that handles collisions by finding the next open bucket through probing.

Open Addressing

The condition that triggers the creation of a larger hash table and redistribution of keys.

High Load Factor

The process of copying existing elements into a new, larger hash table with recomputed hash values.

Rehashing

A data structure that stores a collection of unique elements without duplicates.

Set

The set implementation that uses a hash table and does not maintain order.

Unordered Set / HashSet

The set implementation that uses a balanced binary search tree to keep elements sorted.

Ordered Set / TreeSet

The property of sets that ensures each element appears only once.

Uniqueness

The time complexity of basic set operations such as insertion or search on average.

Constant Time

The Java class that represents an unordered set.

HashSet

The Java class that represents an ordered set.

TreeSet

The Java method used to add an element to a set.

add(element)

The kind of output shown when printing a HashSet, where order is not guaranteed.

Unordered Output

The kind of output shown when printing a TreeSet, where order is always ascending.

Sorted Output

The internal data structure used by a TreeSet.

Binary Search Tree (BST)

A data structure that stores information as key-value pairs.

Map

The rule that each key in a map must be unique.

Uniqueness of Keys

The operation that associates a specific key with a value in a map.

Insertion (put)

The operation that retrieves a value using its corresponding key.

Retrieval (get)

The operation that removes a key and its value from a map.

Deletion (remove)

The property of a map that allows dynamic resizing when elements are added or removed.

Dynamic Size

The type of map implemented using a hash table.

HashMap

The type of map implemented using a binary search tree.

TreeMap

The type of map implemented using hashing and a linked list to maintain insertion order.

LinkedHashMap

The Java method used to insert key-value pairs in a map.

put(key, value

The Java method used to retrieve values from a map.

get(key)

The Java method used to check if a key exists in a map.

containsKey(key)

The Java method used to delete key-value pairs from a map.

remove(key)

The default print format when displaying map contents.

{key=value, key2=value2}

The map that provides constant-time lookups but no ordering.

HashMap

The map that stores keys in sorted order.

TreeMap

The map that preserves insertion order when iterating.

LinkedHashMap

The reason prime numbers are used as table sizes in hashing.

To reduce clustering

The metric that measures how full the hash table is.

Load Factor

The data structure used in chaining to store multiple values in one bucket.

Linked List

The situation when the hash function gives the same index for two different keys.

Collision

The process of creating a new table and re-computing all hash values when resizing.

Rehashing