Your hash method returns 1 for every character in the alphabet. This makes it hard to solve the 3 challenges you proposed. I had to modify it you " * ord(c)" instead of " ** ord(c)". For full strings works fine. Besides that, great implementation! Thank you!
Dude, thanks for the video. What would make this better, is putting it into action on some data and having a look at the outputs. Then I can really understand what each part of the Class is doing and apply/tweak to my issue.
Great content, One thing I wanted to share that we can decrease the insert time to the bucket in O(1) - Constant time by inserting an element to the head(Front) of the LinkedList.Thanks
Hey ! I was wondering if you could review 2 quick hashtable classes I've made. They're using the djb2, crc32 and K&R algorithm for the hash function and your video helped me a lot so feedback would really mean a lot to me :) Thanks for your superb videos !
Hey, thanks a lot! If you post it on GitHub or Gist or something I'll definitely review, but I haven't looked into any of those hashing algorithms. Sounds like you're ahead of me :)
There is an issue with the remove function. Its not working properly. Suppose if the node is first node, then it is not handling the case properly and secondly the error is coming because the prev is not initialised.
I agree fully. Thanks for pointing this out! Someone noticed the same thing and made an issue on GitHub. Check out this link to see the fix and explanation: github.com/stephengrice/youtube/issues/2
Can the actual hash function you are using be replaced by any of more popular ones like SHA- or MD-? I assume for the scope of the example problems it shouldnt matter?
Muntasir, thanks for the question - great point. The hashsum is definitely the part of the hashtable where you have the most freedom in how you implement it. The simplest possible way of converting your "key" to an index in the internal array is to always return 0. If we did this, we would just have a linked list, because everything would be under the first position, or "bucket" in the array. When two keys are stored under the same "bucket", it's called a collision. In the above example, inserting an element into the hash table would cause a collision 100% of the time. A goal of the hashsum is avoid these collisions, keeping the hash table's performance as close to O(1) as possible. With everything under a LinkedList, you're getting O(n) performance instead (at least for the find() operation). To avoid collisions, you have to come up with a clever way of making sure that all the keys you're supplied with are evenly distributed throughout the internal array. If I remember, in this video, we simply added up the values of the character codes for the string. This was the example I've always seen used, but I know that there are other, more complex solutions out there that probably do a much better job. I just don't know what they are :) Another way could be just generating a pseudo-random number to store the item under, using a built-in Math.random() function or something like that. It would be simpler to code, and it would probably be a good enough quick-and-dirty solution, at least as a learning tool. Please let me know if this answers your question, and don't be afraid to ask if you have more. I'm no expert, but I can try my best to answer :)
@Duke Wellington again, I'm no expert, but I'm willing to bet this would work just fine for most applications. There could be a way to optimize it for high-performance scenarios when the code would be used en masse, but just running as a test on your laptop, I don't think you'd ever even notice the difference. I'd expect the rate of collisions to be really low. Thanks for your thoughts on this!