Hash Table Exercise

[00:00:00]
>> Bianca Gandolfo: And then Hash Table. So the difference here is this Hash Table has array as the storage. You're gonna need to be able to insert. When you insert, you need to pass a key and a value. It needs to be constant time. Removal also constant time. Retrieval constant time on average, of course.

[00:00:29]
Some things that aren't included in here, but you should be thinking about when you think about a Hash Table is the problem of resizing, right? And then also the problem of collisions. You will need to think about the size. You guys are doing the Hash Table?
>> Speaker 2: Mm-hm.

[00:00:45]
>> Bianca Gandolfo: You're going to need to think about the size, because your hashing function requires a size. You're going to think about the size. If you have time, you can handle collisions however you feel like. You can just use an array, you don't need to use a link, a link might be be too complicated for the time that we have, but you can just use an array.

[00:01:05]
When you have a collision with an array or when you have a collision, you just put a two-pole, and array with two values with a key and the value in the index of that hash. So when you have two, so let's just say this is your empty Hash Table.

[00:01:27]
And say will you put A which to say you put the keys one and the value is one, and you have the keys two and the value is two, right?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: But they all hash to let's say zero.
>> Bianca Gandolfo: Okay, so they hash to zero. We're going to have to put both of these, in the zeroth position.

[00:01:58]
So how do we do that? Very easily, we could just simply put an array in here, and then put 'one', 1 and then 'two', 2, like that. So that's how you can handle collisions if you have time.
>> Bianca Gandolfo: Is this clear? The other thing is, this could be a linked list.

[00:02:28]
So where, like, this has a Next and it points to this one, this one has a Next and it points to the next, you know, to null, okay. And then the retrieval, if you're gonna handle collisions, which needs to handle retrieving from something that's nested. So that's some extra logic to think about.

[00:02:49]
And then here's just like my hash function.
>> Bianca Gandolfo: Okay, and note so a parameter needs to be defined here. I don't always define them, for you, so just be, be mindful of this.
>> Bianca Gandolfo: These comments that say what the parameters are, and what they should return.