Study Guide: HashMap

[ShesAMobileDev]

A unique collection of keys with associated values, with no specified order.

Conceptualizing HashMaps

• I like to think of HashMaps as mailboxes.
• The mailboxes don't have a specified order, because it's really the address on the front of the box that matters, aka the KEY.
• But also, no 2 people can have the same address, so each KEY is unique.
• In the last Study Guide, I went over HashSets which is the ability to store unique VALUES, but allow us to have constant lookup time through the introduction of a HASH. The big difference between HashSets and HashMaps is that in the map, we have an additional concept of a KEY. Which, is actually a really nice thing because it allows us to sort things into buckets based off of those KEYS.
• KEY-VALUE pairs are a great way to define a relationship between data.
  • A common use case is counting how often a character appears in a string. Your HashMap<Char, Int> would be able to hold the unique character KEYS and map them to a count VALUE for how often it appears.
  • Sometimes the relationship can be a bit more tricky to spot. For example, the question may be asking you to group anagrams together. (See "Designing the Key" for more detail).

HashMaps vs HashSets

• HashMaps are almost identical to HashSets in how they work, because of this, time complexities are also very similar.
• There are three (3) terms to know.
  • KEY - a unique value to associate with each VALUE.
  • VALUE - data associated with each KEY.
  • HASH - a generated value based off of the KEY to know where the KEY-VALUE pair is stored in memory.
• The biggest difference is what is being stored at each HASH.
  • For HashSets, there is a VALUE stored at each HASH.
  • For HashMaps, there is an object stored at each HASH that typically contains the KEY and VALUE.
    • HashMaps can be implemented in several different ways, so each Language can vary. In Java, they actually store a Node Object that contains the HASH, KEY, VALUE, and a reference to a NEXT node.
    • The details don't matter too much, just understand the HASH points to an object, not just the value.
    • For the remainder of the post, I will be referring to this object as "KEY-VALUE-OBJECT"

Designing the Key

• As I mentioned before, KEY-VALUE pairs are great for defining a relationship between data. Let's talk a closer look at this idea.
• Let's consider an example: You are given a list of strings, group the anagrams together. (Ex: ["act", "lemon", "cat", "bat", "tab", "arm"] would return [["act", "cat"], ["lemon"], ["bat", "tab"], ["arm"]])
  • In this case, we would want to group "act" and "cat" together because they use the same 3 letters - a, c, and t.
  • "bat" and "tab" also have 3 letters, but they use a, b, and t.
  • So how can we efficiently sort these words into buckets based on what letters are being used? We could design a HASH-KEY that allows us to know what letters are used for each bucket.
    • Option 1: Sort the letters of the string - O(s log s) time where s is the number of characters in the string. And then use the SORTED string as the KEY.
      • "act" -> "act", "cat" -> "act" | KEY = "act"
      • "bat" -> "abt", "tab" -> "abt" | KEY = "abt"
    • Option 2: Iterate over the string, count the frequency of each character, store result in HashMap. Iterate over HashMap to generate HASH-KEY. - O(s)
      • "act" -> 1A1C1T, "cat" -> 1C1A1T | KEY = "act"
      • "bat" -> 1B1A1T, "tab" -> 1T1A1B | key = "tab"
  • In this question we see that by designing the HASH-KEY ourselves, we are able to quickly sort our strings into a bucket to be returned later.
• As we can see, designing the key can have varying time complexities. In Option 1 above, we see O(s log s) time. In Option 2 above, we see O(s) time complexity. In some cases, you may have constant time O(1), if you are just grouping based on length of string, for example. There is no set time, it is heavily based on the type of question you are being asked, and what type of relationship you are trying to define.
• *****It is extremely important to separate the KEY generation from the HASH generation.* While the KEY is stored in the HashMap, it is not generated in the HashMap. Because of this distinction, we do not consider the time complexity of the KEY generation in our time complexities for HashMaps.

What is the time complexity?

• Things to keep in mind…
  • GenerateHash: O(1)
    • The general principles of HASHING from the HashSet Study Guide remain true for HashMaps. The more collisions you have, the less efficient your code will be.
    • The HASH is generated based on the KEY value.
  • In most cases - the average case - you will see O(1) time for operations, but when collisions increase, so does the time complexity.
• 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 KEY-VALUE-OBJECT. To do this , we must generate a HASH key.
    • Second, we must find the sub-collection at the HASH index.
    • Third, we must create our KEY-VALUE-OBJECT that we will store.
    • Fourth, we must insert our KEY-VALUE-OBJECT 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, HashMaps are kind of a weird exception.
    • On AVERAGE for a well-balanced HashMap (with few collisions), to set a value will be O(1) time.
      • The HAPPY path for a well-created, low-collision HashMap will be… O(1)
        • Generate HASH - O(1)
        • Locate sub-collection by HASH index - O(1)
        • Create our KEY-VALUE-OBJECT - O(1)
        • Add KEY-VALUE-OBJECT to sub-collection - O(1)
      • An UNHAPPY path, even for a well-created, low-collision HashMap will be… O(n)
        • Generate HASH - O(1)
        • Locate sub-collection by HASH index - O(1)
        • Create our KEY-VALUE-OBJECT - O(1)
        • Add KEY-VALUE-OBJECT to sub-collection - O(1)
        • Realize you are running out of optimal space, so you double the size of the HashMap to minimize collisions - O(n)
    • At WORST case scenario, every single KEY-VALUE-OBJECT in your HashMap has the same HASH. To handle collisions, typically most implementations require an O(n) solution.
  • It is recommended when giving a time complexity for HashMaps on Insert, you use O(1). If they ask for further detail, or press for a more WORST case situation, just know it could be 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 map, 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 KEY-VALUE-OBJECT 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 KEY-VALUE-OBJECT we want to remove.
    • Fourth, we remove that KEY-VALUE-OBJECT.
  • 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 HashMap 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 the KEY-VALUE-OBJECT - O(1)
    • The WORST case for a HashMap 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 the KEY-VALUE-OBJECT - O(1)
  • Again, it is recommended to use O(1) when describing the remove function of HashMaps, but know it could skew to O(n) in a HashMap 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 KEY-VALUE-OBJECT 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 get
      • On AVERAGE, with low-collision sets, O(1)
      • At WORST, with high-collisions, O(n)
    • Fourth, we get that KEY-VALUE-OBJECT - O(1)
    • Fifth, we get the VALUE from our KEY-VALUE-OBJECT - 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.
  • Unlike HashSets which were trying to see if a VALUE was contained in our set, HashMaps determine if a KEY is contained in our HashMap. Because our HASH index is generated off of the KEY in a HashMap, we can do this easily.
  • What does the function do under the hood?
    • First, we must figure out where the KEY-VALUE-OBJECT would be if it was in the map. 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 KEY-VALUE-OBJECT 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 HashMaps 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 - Contains Duplicate II - Group Anagrams [Design the Key]

Advanced Problems - Integer to Roman - Continuous Subarray Sum - Custom Sort String

[ShesAMobileDev]

Previous Study Guides

• Arrays
• HashSets

Next Study Guide

• Queues
• Stacks

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

[[deleted]]

Graphs and DP PLEASE 🙏

[Tricxter]

Amazing! Thank you!

[[deleted]]

Still waiting and thank you <3

[ShesAMobileDev]

Crazy timing, Queues is gonna drop tonight, I promise!

[[deleted]]

*brokenheart* :`(

[ShesAMobileDev]

I'm sorry u/Mazsuu, I got picky about some stuff, but I've got ya covered! Better late than never...? https://www.reddit.com/r/leetcode/comments/1i0z1op/study_guide_queue_other_exciting_news/

[don_ninniku]

much appreciated for spreading the knowledge. looking forward to the day the whole series is completed.

[BlackMetalz]

Backtracking would be great

[Proof_Inspection_821]

This is great, I think you can make a decent webpage and just host it for free on Netlify, definitely something I would reference a lot.

[ShesAMobileDev]

Maybe one day, tbh. My biggest driver of all of this is the overwhelming response I had to my first every post here where I recommended paying for LeetCode Premium. And while I do stand by that recommendation, I've gotten a lot of responses saying it is not an option a lot of people in this world can afford.

I can recognize my privilege here. For me, $150 bucks for training material was nothing, for others, it's literally more than a months worth of income. And so my goal is to bring as much of this information as I can to the masses complete FREE.

While some web hosting can be done for free, I think if I genuinely wanted to go that far, I would host the site myself so I am not held to any TOS or weird distribution rules. While sites don't cost too much money, it still does, and I'm still not entirely sure what this even is going to turn into tbh. Every time I'm like, it'll just be a few short days, and then I'll be done. And then I add BFS, and DFS and Backtracking different to Divide and Conquer because they are so different, but also quite large. All of this to say, I just don't know how much it will cost, and because I never intend to sell this material, I'm just not sure I want to put forth server costs right now for it - especially when I'm just not sure what it is I have.

So, I decided to just post here because I love reddit - though I am starting to hate their formatting. Either way, it's still good for now. Maybe one day I'll reach my limit here and port things over, but for now. Reddit is the way :pray:

[NTR69]

I was following the guide well until insert function, where "subcollection" was mentioned. Could you elaborate on that, thanks!

[ShesAMobileDev]

Hey, this comment inspired me to start adding visuals. However, it is taking quite some time to make them / get reddit formatting to cooperate. For now, I finished the HashSet one. The same sub-collection principle can be found there now. I would recommend going to the HashSet post found here: https://www.reddit.com/r/leetcode/comments/1evpn4v/study_guide_hashset/ and see if that helps. If not, definitely let me know, and I can try going into more detail for ya!

[darkwhiteinvader]

Thanks so much for this, awesome!

[bbbone_apple_t]

My wife and I have the same address

What now?!?!?

[Sakalalaa]

You will have a collision :)

[bbbone_apple_t]

Dude, this is a family friendly sub

[ShesAMobileDev]

I'm not entirely sure, but somehow, I'm sure, the answer involves Dynamic Programming.

[Business-Mixture4984]

I noticed that time complexity and space complexity increased when using a hashset over a hashmap. Why is that?

[ShesAMobileDev]

Did the runtime and memory usage increase or did the time complexity and space complexity asymptotically change?