In the week 6, it was said for hash tables that - "We could even combine names and birthdays somehow to create a larger hash table that’s even more uniform and have smaller chains, and be even faster"
Here chain means that value and not the index. I am not sure if above is true, larger hash tables means that there would be more index locations in the hash table and each index location will be pointing to a chain which would be some linked list or array.
If there are more index locations and smaller chains then it in order to search the element, all index locations need to traversed, so this would approach O(n) because worst case let say element is in the last index location in the hash table.
Please correct me if I have misunderstood the statement I mentioned in the start.
Suppose I want to insert 'n' element and I computed 'x' hash'es from it which means there would be 'x' index locations. So, I think running time of a hash table will be O(n/x). Right? Where 'n' is the number of elements and 'x' is the number of hash'es or indexes.
Now, simple maths tells me that
- if there is only one hash/index (x=1) which means all elements will be inserted at same index in the hash table, so running time becomes O(n). Which looks true to me.
- if there are 'n' hash/index (x=n) which means all elements will be inserted at one index in the hash table, so running time becomes O(1). But this is not true. Right? Because if each element is inserted at one index in the hash table then it is as good as my linked list. Right?
So, what I think is that hash table will have best running time when for each index in the hash table will have same number of elements. Right?