Hash Table: Retrieve

[00:00:00]
>> Bianca Gandolfo: Let's retrieve, so, we wanna pass the key. And it's gonna return the value associated with it. Okay. So, we want to get the index from the key. So we have the key, we wanna look up the index by passing it to the hashing function, okay? And then we need to delete it.

[00:00:27]
So, the thing here is if we have a collision and the scenario is that we have something like this.
>> Bianca Gandolfo: We need to loop. And so this is where, am I retrieving? Yeah. So this is where the question starts to be, okay, so if we have these collisions and we're adding all of these items into the same index and then if we need to find something, we just loop through that index, right?

[00:01:05]
The array of arrays, we just loop until we find it. Doesn't that make this linear time? Why would I say hash tables are always constant? Well, we think of hash tables as constant because on average, with things like resizing, in really good hashing algorithms, it's pretty much like a moot point.

[00:01:31]
Like it's so rare that you would have everything hashed to the same index. My hash function is stupid but the real has function that people are using are very complex and they manage like distribution and stuff like that, depending on the type of data, there's different ones. So this is called amortized time complexity.

[00:01:58]
So we kind of like spread it out and think of it in terms of adverse case when the worst case is so unlikely that it's not useful to think about, does that make sense? So yeah, if suddenly, we know we do c3, d4 and we keep going, going, going and it's all in this third index and then we wanna find one of these, yeah, we're gonna be looping through and that's a linear time operation that would happen in a very rare circumstance, so, something to know.

[00:02:37]
Something to note. Okay. So what we're gonna do, we retrieving keys, so we got the index, so, let's say we want to say if.
>> Bianca Gandolfo: So if this strong, got to be strong if this.storage. So if this.storage[index], so if it exists, then we want to return our value.

[00:03:23]
So we can loop through, we can reduce over it, we can just go create but we're gonna need to loop. So this.storage[index] is gonna be, should we for each? What kinda loop is the best? So we're just gonna loop through it, we're gonna find the value, we wanna return is, so if you wanna return, probably for each isn't the best.

[00:03:48]
It's not really good for returning things. Why don't we, we mapped it, then it wouldn't be an array. We don't really want it to be an array. We could reduce it but reduce is kind of overly complicated for what we need. Also, it's really hard to stop the loop.

[00:04:04]
So I think I'm just gonna be old school.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So now we're looping through all of, so let's just make this, what do we wanna call like this internal array here? Like maybe.
>> Bianca Gandolfo: Or I'm gonna put array in that word for sure. Let's see. All right, arrayAtIndex.

[00:04:53]
That's what we're doing, okay? Okay. If you guys come up with a better name, let me know. That's what I got right now in my head. So, for this arrayAtIndex, we're gonna loop trough it and if (arrayAtIndex[i]), so the very first time we loop through this array, we're gonna get this value, this array.

[00:05:33]
The second time we loop through, we're gonna get this one. So, this is gonna be, if I said type of arrayAtIndex, it's also going to be an array.
>> Bianca Gandolfo: So, let's see. So we could say, if you could just see my natural typing, I always just type var, I'm too used to it.

[00:05:56]
What do we want to do? I'm gonna say keyValueArray.
>> Bianca Gandolfo: So we have our key value.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So if our keyValueArray, so our very first value is the key. So we want to say if our keyValueArray, this value equals the key, right, not the value because we can't look up an object for a value.

[00:06:38]
We can only look up an object for the particular key. In any case, we only know the key.
>> Bianca Gandolfo: So, === are key, then you wanna return keyValueArray[1], which is our value.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: And hopefully, you only have to loop through this once or twice. And that your collisions aren't so deep that this is going on forever.

[00:07:25]
>> Bianca Gandolfo: All right, do I have any edge cases?
>> Speaker 2: Are there such a thing as like collisions within a collision kind of thing?
>> Bianca Gandolfo: So, you mean like if you try to add to the same keys?
>> Speaker 2: Maybe that's what I mean.
>> Bianca Gandolfo: So, we have a collision for this index three.

[00:07:49]
And then we need to push, right? What if, I just found a bug actually, now that we're talking about it, what if we do this?
>> Bianca Gandolfo: That wouldn't work because we can't have a duplicate. So, when we are pushing, we also need to make sure that we don't have another value here.

[00:08:23]
>> Bianca Gandolfo: So, let's see. So, if storage index and then, so we can do TODO, TODO loop through, all right and find if key was already inserted. Does that make sense? So if we insert B twice, we don't wanna have two arrays for B, we need to update the value of B of the first B.

[00:08:58]
>> Bianca Gandolfo: We're not gonna have time to implement it. But that's what needs to be done.