Hash table separate chaining

[@shivamjalotra7919]

These videos are lovely and the way you explain a rather complex topic is just remarkable.

[@bartolomejkozorog3387]

Hvala.

[@brunoserras]

Excellent video! I just have one question, at 2:44 you add the element at the tail of the linked list but I have been reading a book about this data structure where they add the new elements at the head of the linked list. Is there any difference on that? Keep up the good work.

[@WilliamFiset-videos]

You can add the element to the head of the list, somewhere in the middle or at the tail it really doesn't matter. However, you still need to check all the elements in the bucket the hash falls into to make sure you don't add duplicate elements. Since you need to traverse the entire linked list anyways I find it easier to add to the tail of the list, but whatever floats your boat :P

[@brunoserras]

Right! Thanks for the answer!

[@Henry14arsenal2007]

@@WilliamFiset-videos and what if you need to keep duplicate values, like people with the same name and age?

[@georgetsiklauri]

Good video, William (if that's your name :)). I just have a innate habit, that whenever I learn something, I go very slowly, analyze each bit and try to document the content in a consecutively structural way. So, during defining what type of is the backing array of the Hash Table, it's actually a bit tricky for me to write precise definition. First I understood that backing array is of a type of specific Entry, and in each slot, corresponding entries are stored, which makes sense, as after hashing the key, we'll get the specific index of the backing array, where both - key and value pair (a.k.a. Entry) are stored.. but during listening to the Separate Chaining, picture changed a bit.. and I'm now saying, that in some implementation (Hash Table implementation with Separate Chaining), backing array is of the type of Linked List, and each of the elements of that array (Linked Lists) are called buckets, which in turn, are the lists of Entry elements. Could we come up with some uniform, ubiquitous and consistent definition of what kind of array is the backing array in the Hash Table? :)

[@Mydad-et1el]

"backing array", which is the underlying core backbone data structure for the hash table, is always and always an array. That is the reason why hash table has O(1) time complexity, because accessing element in array is always O(1) Now with the bucket. In this video he uses Linked List to demonstrate separate chaining. So the structure of the hash table looks like this: index 0 [] -O-O-O-O-O index 1 [] -O index 2 [] -O-O-O-O index 3 []-O-O index 4 []-O-O-O-O The vertical square brackets represent the contiguous array- the backbone of the hash table. The O-O-O- is the linked list chain that get appended if a collision occur. And that is a bucket. Each linked list is a bucket- a bottomless bucket that can accommodate infinite collision. That linked list can be replaced by other data structures, like a binary, or even an array, depends on what you want. Each array index stores a reference to a node in linked list. The node, in turns, store the key-value pair and link to the next node, which stores the data of another collision (a key hashed to the same array index) in turns. And so on. Did I answer your question?

[@milindaseneviratne5917]

@@Mydad-et1el Thank you for this explanation. It was very helpful :)

[@Mydad-et1el]

@@milindaseneviratne5917 you're welcome. I didn't remember I wrote that. I'd actually just forgotten all that stuff when your comment brought me back here.

[@ButerWarrior44]

2:43 is it fine to append 'Lara' to front of linked list? does this affect time complexity?

[@decordsuccessful1823]

Thanks brother, I really appreciate it

[@bernardopankaarchegas8007]

Great series

[@radelfalcao9327]

Awesome video.

[@duchungtran9831]

How can we calculate hash function if there is not key type int like the video?

[@pokerface550]

1) There MUST be a hashable key, not necessary an int, it can be a string, for example. The main condition to comply with in order to be considered a good choice for keys - is to be immutable. So, things like chars, strings, numbers are good, but not lists, sets, arrays because you constantly add/remove/change their content. 2) Hash algorithms can work not only with numeric keys. I mean eventually keys will be mapped to numbers by some means to perform futher calculations, but initially keys may be of any type being immutable.

[@shivamjalotra7919]

What if we have a Balanced Binary Tree or(set) instead for every hashed value something like vector. The we can do insertion in O(log(n)), deletion in O(log(n)) and search in O(log(n)).So why don't we use it or say that O(n) is the worst case time complexity ?

[@wolfie6512]

You can use it. Separate chaining means you use an additional structure to store collided items. Linked lists are used for demonstration purposes only as it's easy to draw.

[@shivamjalotra7919]

@@wolfie6512 Got you.

[@subee128]

thanks

[@ernestofavio6735]

How old are you now Will?

[@cjromb]

Old enough to make amazingly useful videos, eh?

[@jazmine722]

3 years older than he was when he first made this video :p

[@ernestofavio6735]

@@jazmine722 I see... xD

[@lbars]

Now, 3 year and 10 months

[@ayubaalim2201]

my DREAMS from Somalia