#coding #programming #python

Previous (Hash Table) Video:    • Why Is Finding an Item in a Hashtable...  

Some people mentioned that hash table look ups are only faster when compared to a list with many items in it. So I though we could all look at a hash table like lookup that most people could use in the commonly used language, python.

Quickbits Shorts:    • QuickBit Shorts  
Quickbits:    • QuickBits  

​Music:    • (FREE) Lo-fi Type Beat - Blue Moon  

Some of the comments that inspired this video:

1. Good video, but the title is actually wrong. Like always it depends. For short lists linear search can be faster than constant time search. Basically a hashing function can bring a large enough constant that is bigger than accessing N items, for some values of N.

2. Is it really SO MUCH FASTER for a list of like 5 items (or even like 100)? A sophisticated hash function is O(1) but is also not negligible. This video title is exactly why I see people converting a list of 100 items to a hash table, and do a single search on it. The conversion is already very costly since the hash function is called on every single item to build the hash table first. And then the hash O(1) search may still be slower than a linear search on that 100 items. The explanation of how hash table works in the video content is good though, I just think the title IS VERY MISLEADING.

3. Depending on the size of your list, checking a simple linear list might actually be faster. Why? Cache lines. There is always a difference between theory and practice. So the best advice I’d give on this one is: profile your code and measure what works faster. Never simply trust theory over practice :)

4. Depending on the hash function complexity and speed, the hash function is only better when your list is LONG.

5. But this is not actually true? If the list is small it will be always faster.
Hashtables have ~O(1) cost, but the constant cost is very large, as computing hashes is expensive.
Good video though, just nitpicking because I'm tired of seeing big O notation used as a metric, instead of actually benchmarking.

6. What you fail to account for the front end work done to create and compute the hash. For small scale list HASH is inefficient, for Giga-scale content, it is very efficient, crazy efficient.