Introduction to Data Structures for Interviews Hash Tables Use Cases, Arrays & Strings
Transcript from the "Hash Tables Use Cases, Arrays & Strings" Lesson
>> Bianca: All right, so hash table in real life. It's a little simpler. We're used to using objects. Do you guys use ES6 maps and sets? So a set doesn't save a value. It just saves the property name. So this idea of the key value pair, it's only a key for a set but the key can be a string, can be a function, could be a number, could be anything.
[00:00:32] Where as a regular object it could only be a string if you pass a number to an object. That property name is just stringified so is just like a string of zero, for example. And then a map is like a combination of the set and the object because you still have a key value pair and you can save any data type in a map just like a set.
[00:00:57] So you can save other objects, you can save functions, strings, whatever you want. So it's like an extension of an object. The interface, how you interact with a map and a set is a little different. So, you don't use the dot notation like you would, or a bracket notation like you would with an object.
[00:01:21] You do things like .has or .get and .said, things like that. So, it's a little bit of a different way of interacting with it, but a lot of the qualities are the same. And the time complexity in terms of insertion and retrieval are all constant time and under the hood, they're implemented as a hash table.
>> Bianca: Questions? When you're thinking about optimizing a problem that requires a fast look up, your mind should always think Hash table. And then when you think hash table, and you're using ES6, which, you should try to do as much as you can, it shows that you're learning and growing as technology changes.
[00:02:09] When you consider, what is the appropriate data structure? Is it just a regular object? Is it a map, like do I have to save functions as values or as properties? Or is it a set, do I even need a key value, maybe I just need a key. So we're gonna talk about arrays and strings.
[00:02:34] When we think about strings like I mentioned, we should think about them as arrays of characters, as often better. Strings are not mutable, which means that if you change a string you're really copying a new string with that change. And so if you're doing any string operation that is changing the string, so if you're slicing a string, keep in mind that you're actually copying a new string.
[00:03:00] And this has space complexity implications. So if you're trying to do something in constant space, you can't really use a string. You need to use an array and then you would need to do swapping versus creating a new string every time. Through slicing or whatever it may be.
[00:03:25] If you loop, you can loop through a string. But, in an array, if you look through an array and you want to change array I to a different value. You could say array at I equals 2 and you would have an array of all twos. If you did a string at I, you could look it up, it would say like ABC, as you look through.
[00:03:50] However, if you tried to set it either it won't work or it will throw an error, I'm not sure. But you just can't do that, you can't swap out the values of a string. So strings are unmutable, something to keep in mind. When you're working with strings, often I will just split it into an array.
[00:04:09] And then you have a lot of handy array methods that you can work with. So what are arrays good at? They are good for looking up by key, by appending data in constant time. You can have a slow insert in the middle, so if you insert something in the middle, you're gonna have to shift everything over.
[00:04:32] Like I mentioned before when we were talking about the que you would have to shift everything over and then deleting things from the middle. Would have to shift everything over. What else do you need to know about this?
>> Bianca: Yeah, so again, when I say the same things over and over again because repetition is good.
[00:05:23] We don't do any of that, so we get a nice pass. But you might see that when you're reading about it.