Data Structures: Sets and Hash Tables

Study Notes

Sets

Sets are collections of unique elements, designed for efficiency.
Duplicate elements are not allowed.
Removing an element that isn't present doesn't trigger an exception.
Elements cannot be added at specific positions within a set.

Hash Tables

Hash tables map keys to values via a hash function.
Elements are grouped by shared characteristics.
The hash code determines an element's position in the table.
Elements cannot be added at specific positions.

Hash Codes

Hash codes are numerical values, calculated for efficient indexing.
They must be consistent and uniform.
They cannot be directly used as array indexes (values might be too large).

Collisions

Collisions happen when multiple elements hash to the same index.
They are managed via chaining (linked lists) or probing.

Code Snippets

Compressing a hash code to an array index:

int h = x.hashCode();
if (h < 0) { h = -h; }
position = h % arrayLength;

Adding an element using chaining:

Node newNode = new Node();
newNode.data = x;
newNode.next = buckets[h];
buckets[h] = newNode;

Operations and Complexity

Add: Average: O(1), Worst: O(n)
Remove: Average: O(1), Worst: O(n)
Search: Average: O(1), Worst: O(n)

Collision Handling

Chaining: Uses linked lists (or other structures) at each index to handle multiple elements.
Probing: Searches for the next available slot in the array:
- Linear Probing: Checks the next slot sequentially.
- Quadratic Probing: Checks further slots to reduce clustering.
- Double Hashing: Uses a second hash function for probe intervals.

Linear Probing Issues

Clustering: Leads to long contiguous groups, increasing search times.

Hash Function Requirements

Uniform Distribution: Evenly distributes keys across the table.
Consistency: Returns the same hash for the same input.
Deterministic Behavior: Output depends only on the input.

Key Definitions

Bucket: A structure (like a linked list) used in chaining.
Load Factor: The ratio of elements to table size.
- Formula: Load Factor = Number of Entries / Table Size.
- Example: 650/1500 = 0.433 (or 43.3%).

Special Techniques and Terms

Re-hashing: Resizing the hash table and reassigning hash codes.
Perfect Hash Function: Maps each key to a unique slot (possible only with all known keys).
Key-Value Pair: The fundamental unit of a dictionary/map.

True/False Key Facts

Statement 1: A perfect hash function maps each search key to a unique location. TRUE
Statement 2: Double hashing significantly reduces clustering. TRUE
Statement 3: Linear probing results in clustering. TRUE
Statement 4: Quadratic probing completely eliminates clustering. FALSE
Statement 5: Set difference is commutative. FALSE
Statement 6: With separate chaining, a dictionary's size can exceed the hash table's size. TRUE
Statement 7: The getValue(searchKey) method retrieves the search key for a given value. FALSE

Miscellaneous

Other names for ADT Dictionary: Map, Associative Array.
Map Ordering: Typically ordered by key.
Set Operations:
- Union: Combines elements.
- Intersection: Finds common elements.
- Difference: Finds elements in one set but not the other.

Frequently Asked Questions

Search Key Exists: Update the value associated, or reject the new entry.
Primary Clustering: Causes groups of elements, increasing collisions.
Collision: When two keys hash to the same index.
Linear Probing: Searches sequentially for the next free slot.

Description

This quiz covers fundamental concepts of data structures, focusing on sets and hash tables. You'll explore how unique elements in sets are managed and the mechanics of hash codes and collision resolutions. Test your understanding of these essential topics in computer science.