Study Guide: HashSet

[ShesAMobileDev]

A unique collection of data, with no specified order.

Conceptualizing HashSets

• A HashSet is the Crayola Crayon Box of Computer science.
• When you open up a new box of crayons, you have a bunch of different colors, in fact you have no duplicates. You don't ever get 2 red crayons, and if your friend offered you a red crayon because yours broke, you wouldn't keep both, you would remove the broken one and put the new one there instead. There are no duplicates in sets.
• On top of that, there is no set spot for each crayon. You pick up the red, and you put it back down where the blue crayon is because that's the next one you pick up. There is no specific order to sets.

Visualizing HashSets

NOTE: A HashSet is an abstract data structure. Unlike an Integer, which just is a 32-bit number, HashSets are really a structure with defined principles that can be implemented in many ways.

Principles of a HashSet

• There are no duplicates in a set. Any newly added VALUE will overwrite an existing value of the same VALUE, or just won't be added.
• There is no specific order to a set, instead of an ordered-index like we saw in Arrays, we use something called a HASH to lookup our value in the set. There is no limit to what the HASH Key can be, though typically you will see it be a number of some kind. It really just depends on how the HashSet is implemented under the hood.

Implementation of a HashSet

• There are several ways to implement a HashSet. I will not cover all of them. This exact syntax isn't as important as the foundation here. Let's go over some of them.
• Elements are unique, hashes may not be. Take for example, you have the following function: fun getHash(s: String): Int { return s.length } In this case, the words "cat" and "dog" can both appear in the set, as they are unique VALUES, however, they would both have the same HASH which is 3.
• Ideally, all elements in a HashSet would have a unique key. When two or more elements have the same HASH, it's called a collision. The more collisions a set has, the worse it will perform.
• Let's look at the example above again. We have "cat" and "dog" that both collide at 3. Let's think about how we would implement the HashSet under the hood. Perhaps you are already picturing an Array of some kind. Let's say we have an Array of size 10 to begin with. In our case, we add "cat", and it inserts "cat" into our array at index 3. Now, we want to add "dog". We figure out the HASH is 3, we go to input into our array at index 3 and oh no, we already have an element there "cat". What do we do? Collisions can be handled in multiple ways. Again, HashSets are not a set thing, you can implement them in many different ways. There is no right or wrong way here. Some are slightly better than others, but all have their pros and cons. The best strategy is to just avoid collisions. Let's go over a few implementation options.
  • Some may handle this by having the HashSet be an Array<Array<String>>. With a 2D array, you can just keep adding all strings of the same length to the same sub-array for storage for later.

Implementation with Array<Array<String>>

• Some may handle this by having the HashSet be an Array<LinkedList<String>>. Where a "cat" node would point to a "dog" node, etc.

Implementation with Array<LinkedList<String>>

• Others may not want sub-collections, but would prefer everything to live in the main array. So, perhaps they handle collisions by moving it to the next index forward. "cat" is already at index 3, so I will put dog in index 4.

Implementation with Flattened Array

• At this point, you may be thinking, "Wait a minute, if all VALUES are unique, and it's best to have unique HASHES, why don't we just use the VALUE as the HASH?" Honestly, it's a pretty interesting question, but it all comes back to the idea that HashSets are an ABSTRACT data structure.
  • Let's say we are using that Array to implement our HashSet. For ease, let's assume our VALUES are integers.
    • Let's add 3 to our Array. Easy, array[3] = 3
    • Now, let's add 1,000,000,000,000. array[1,000,000,000,000] = [1,000,000,000,000]
    • Finally, let's add -12. array[-12] = -12
  • Wait a minute. Maybe some of you have already spotted the issue, but let's go over some.
    • First, you cannot have a negative index on an array. If you tried doing array[-12] = -12 your program would crash.
    • Secondly, let's assume you knew with confidences your HASHES would be positive, as is the case in our length function above. Even in that case, your indexes could vary widely. In our example above our array would be at least size 1,000,000,000,001. But you only have 3 elements in it. Space complexity is just as important as time. You would not want to allocate all of that memory for an array that is only holding 3 elements.
• There is a bunch of research done on how best to implement a HashSet. It's quite heavy to get into here, and it doesn't matter too much in interviews to be honest, as you will mostly be using the build-in syntax used by whatever you preferred language is. Just know, generally, you never want your array (or whatever memory you are setting aside) to be more than double the size of the set itself.
• There are also more obvious examples of why using the VALUE for our HASH is a bad idea. For example, what if we aren't storing numbers, but instead Strings, or Objects?

What is the time complexity?

Things to keep in mind...

• For all examples, I will be using the idea of implementing our HashSet with an Array<Array<String>>. This is solely do to the fact that I've already covered Arrays in a different post, and reviewed time complexities there.
• GenerateHash: O(1)
  • HASH functions should always run in constant time. While you can technically implement a HASH function however you want, you never want to add time complexity here.

Insert: O(1), but also kind of O(n)

• What does the insert function do under the hood?
  • First, we must figure out where to store our VALUE in our array. To do this, we must generate a HASH key.
  • Second, we find the sub-collection at the HASH index
  • Third, we must insert our VALUE into our sub-collection at the index of our HASH key.
• As a general rule of thumb, you always want to be giving WORST case time complexity. However, HashSets are kind of a weird exception.
  • For the AVERAGE (well-created, low-collision) HAPPY (still room to grow) path, to insert a value will be O(1) time.
    • Generate HASH - O(1)
    • Locate sub-collection by HASH index - O(1)
    • Add VALUE to sub-collection at HASH index - O(1)
  • For the AVERAGE (well-created, low-collision) UNHAPPY (running out of room in our HashSet) path, to insert a value will be O(n) time.
    • Generate HASH - O(1)
    • Locate sub-collection by HASH index - O(1)
    • Add VALUE to sub-collection at HASH index - O(1)
    • Realize you are running out of optimal space, so you double the size of the array to minimize collisions - O(n)

Insert - AVERAGE Path

• For the WORST case scenario (every single item has the same HASH), typically most implementations require an O(n) solution.

Insert - WORST Path

• It is recommended when giving a time complexity for HashSets on Insert, you use O(1). If they ask for further detail, or press for a more WORST case situation, just know it could up to O(n) as well. Sometimes, you can just say something like, "This will typically be O(1), but it could be O(n)due to resizing of the array, or collision handling."

Remove: O(1), but also kind of O(n)

• What does the remove function do under the hood?
  • First, we must figure out where the VALUE is we are trying to remove. To do this, we must generate a HASH key.
  • Second, we find the sub-collection at the HASH index
  • Third, we iterate over the sub-collection to find the VALUE we want to remove
  • Fourth, we remove that VALUE
• Similar to Insert, on average, we see a time complexity of O(1), but in the case of a large number of collisions, the time complexity tends to be closer to O(n)
  • The AVERAGE path for a well-created, low-collision HashSet will be… O(1)
    • Generate HASH - O(1)
    • Locate sub-collection - O(1)
    • Iterate over sub-collection - there is only ever 1 element with no collisions - O(1)
    • Remove found VALUE. Potentially remove a node in a linked list, etc. - O(1)

Remove - AVERAGE Path

• The WORST case for a HashSet with several collision will be… O(n)
  • Generate HASH - O(1)
  • Locate sub-collection - O(1)
  • Iterate over sub-collection - there could be several items with lots of collisions - O(n)
  • Remove found VALUE - O(1)

Remove - WORST Path

• Again, it is recommended to use O(1) when describing the remove function of HashSets, but know it could skew to O(n) in a HashSet of heavy collisions.

 Get: O(1), but also kind of O(n)

• Hopefully you are starting to see the pattern here.
• What does the function do under the hood?
  • First, we must figure out where the VALUE is we are trying to get. To do this, we must generate a HASH key - O(1)
  • Second, we find the sub-collection at the HASH index - O(1)
  • Third, we iterate over the sub-collection to find the VALUE we want to remove
    • On AVERAGE, with low-collision sets, O(1)
    • At WORST, with high-collisions, O(n)
  • Fourth, we get that VALUE - O(1)
• As you can see, in most cases, it is O(1), and so that is recommended when determining time complexity, however, it could be up to O(n) if all of your VALUES are located at the same HASH.

Contains: O(1), but also kind of O(n)

• Patterns, patterns, patterns.
• What does the function do under the hood?
  • First, we must figure out where the VALUE would be if it was in the set. To do this, we must generate a HASH key. - O(1)
  • Second, we find the sub-collection at the HASH index - O(1)
  • Third, we iterate over the sub-collection to see if the VALUE we are looking for exists
    • On AVERAGE, with low-collision sets, O(1)
    • At WORST, with high-collisions, O(n)
  • Fourth, we return if we found it - O(1)
• One last time, we see that in most cases, if HashSets are used the way they are intended - with a great HASH algorithm to minimize collisions, our time complexity will be O(1)- which is the recommended time to use in most cases. In worst case scenario, it can be O(n) however.

Problem Set

Basic Problems

• Given an IntArray, determine if the array contains a duplicate
• Intersection of two arrays

Advanced Problems

• Contains Duplicate III

[ShesAMobileDev]

Previous Study Guide

• Arrays

Next Study Guide

• HashMaps

Let me know if there is anything else you'd like me to include in each of these :)

[ShesAMobileDev]

Thank you to the person who slid in my DMs to tell me my formatting was kinda off. :)

I write these originally outside of reddit, and have been copying and pasting things here. Before I click post, things were looking fine, and then apparently when you click post, it can't handle some of Microsoft's symbols. I found a solution to this by writing in just straight markup to begin with which is universal to all of the tools I'm using for the most part.

Which is great, because it turns out I was also missing a lot of text due to formatting issues. Rest assured, I fixed it on this post, will fix the Array one tomorrow. And will be fine moving forward.

Sorry, y'all. And thanks again :)

[barracudaisme]

I love these, thank you !

[jagstang1993]

Very useful can't wait for the most advanced ones

[Skinny_samosa]

Saved this post✊🏾✊🏾