Review & Cheat Sheet
This is a review and cheat sheet for Hashing and Maps.
Key Takeaways
- Hashing is the technique of mapping a large data set to a smaller range of indices (buckets) using a Hash Function.
- Collisions occur when two different keys map to the same index. They are handled via Separate Chaining (Linked List) or Open Addressing (Probing).
- Hash Map (Key-Value) and Hash Set (Unique Keys) are the most versatile data structures.
- Time Complexity: Average Case O(1) for Insert, Delete, and Search. Worst Case O(N) (collisions).
- Common Patterns:
- Frequency Map: Counting occurrences (Anagrams).
- Difference Lookup:
target - current(Two Sum). - Prefix Sum + Hash Map: Subarray Sum Equals K.
Interactive Flashcards
Cheat Sheet
| Operation | Average Case | Worst Case |
|---|---|---|
| Insert | O(1) | O(N) |
| Delete | O(1) | O(N) |
| Search | O(1) | O(N) |
| Space | O(N) | O(N) |
Java & Go Reference
Java
Go
```java
// HashMap
Map<String, String> map = new HashMap<>();
map.put("key", "val"); // Put
String val = map.get("key"); // Get
if (map.containsKey("key")) { // ContainsKey
map.remove("key"); // Remove
}
// HashSet
Set set = new HashSet<>();
set.add(1); // Add
if (set.contains(1)) { // Contains
set.remove(1); // Remove
}
```
</div>
```go
// Map
m := make(map[string]string)
m["key"] = "val" // Put
val := m["key"] // Get
if _, exists := m["key"]; exists { // ContainsKey
delete(m, "key") // Remove
}
// Set (using map with empty struct)
s := make(map[int]struct{})
s[1] = struct{}{} // Add
if _, exists := s[1]; exists { // Contains
delete(s, 1) // Remove
}
```
</div>
## Next Steps
Now that you've mastered Hashing, it's time to dive into **Recursion**, where functions call themselves!