Data Structures: Sets and Hash Tables

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

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