1. Efficient data structures: Sets & Maps
Welcome back! Now, we are going to go through Sets & Maps.
2. Applying space/time complexity
Now that we understand time and space complexity, let's answer the most important question: "how do we apply this understanding to write more efficient code?"
The answer lies in choosing the right data structure for the task at hand.
3. A user management system
Now, to see this in action, imagine we're building a user management system. We need to check if a username already exists - should we use a list? Searching through an `ArrayList`, as we have covered, gives us `O(n)` time complexity, which is okay, but not ideal. This is where `Sets` come in very handy.
4. Sets
Sets are perfect for this scenario. A Set is a collection of unique elements with very fast lookup times. The `HashSet` implementation in Java provides an average time complexity of `O(1)` for key operations like adding, removing, and checking if an element exists.
Here's how we could improve our user management system using a `HashSet`. Instead of iterating through an entire list, we simply call the `contains()` method. This makes our code much more efficient, especially as the number of users grows.
5. Maps
Similar to `Sets` are `Maps`. Think of a `Map` as a dictionary - each word (the key) has its definition (the value). `HashMap`, a Map implementation, works with similar mechanisms as the `HashSet`, providing `O(1)` average time complexity for key operations like get, put, and remove.
6. Hashcode method
What is it that makes those data structures so fast? The key difference is that they use the `hashcode()` method to convert keys into array indices.
In the user management problem we had before, the reason we had to iterate through the whole list to find the username was because we did not know its index. But what if we had a way to find that index?
Using the `hashcode()` method, we can convert an object into an index we can look for.
Ignoring how this could be implemented for now, imagine a method that could, for example, take a username, and turn it into a number.
7. Indexing elements
Essentially, when we create a `HashSet` or a `HashMap`, Java creates an array of a certain size - let's say 16 buckets initially. When we add an element, two important things happen.
First, Java calls `hashCode()` on our element to get an integer. Then, it uses this `hashCode` modulo, the number of buckets, to determine which bucket the element belongs in. In this example, Java calculates the `hashcode()` of our string, `optimizingCodeInJava`, to be some long number. We have 16 buckets, this number mod 16 is 14, so it goes in bucket 14.
8. Collisions
But what happens if two different elements end up having hashcodes that map to the same bucket? This is called a collision, and Java handles it by creating a linked list at that bucket position. Each bucket can contain multiple elements in this linked list, and that's why we say operations are O(1) on average, but could be O(n) in the worst case if too many elements hash to the same bucket.
9. A note to remember
Always remember; data structure selection is like choosing the right tool for a job - a hammer (an `ArrayList` in this example) is great for nails but terrible for screws (where a `Set` might work better)!
10. Let's practice!
Now, let's practice!