0

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.

My understanding:
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.

BUT

  • 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?

Improve this question

2 Answers 2

Reset to default
1

Your conclusion of "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?" is incorrect. If you have what is called a perfect hash (every element hashes to a different number), and each element is inserted into a different index, then it does indeed run at O(1). The key thing to remember is that you have direct access to each index in the table so you don't have to go through the rest of the elements to get there.

Maybe an example would clear it up.

Let's say you had 10 elements that are placed in an array called foo[]. Also, foo[] has at least 10 cells. If it had more than 10, the same logic would apply, so let's say it has 20 elements. In a perfect hash, each element would be placed in a different cell in foo[] and no two elements would be placed in the same element. (IF they were, it would be in the form of a linked list.) This means that in foo[], there are 10 empty cells and 10 full cells with one element in each.

NOw, you want to find whether an element is in your array. You would apply the hash function to the element to figure out where it should be in the array. Here's the key: the hash function tells you precisely where the element must be. You check that element in the array directly and you see that it is either there or it isn't. Since this is a perfect hash, it will never take more than to search 1 cell in array FOO[] to find an element, or O(1).

In contrast, if you had a single linked list, the worst case is that you are searching for the last element in the linked list, so it would be O(n).

The more efficient the hashing, the smaller the practical O(x) gets, even though it still calculates as O(n). In other words, if the hash produced an average of 2 elements per cell, then the average case is searching 2 elements to get to a target, even though the worst case could be a single linked list in one cell, while all the other elements are full. So, this is all about flattening out the linked lists. Having more cells and shorter lists make the search more efficient in the real world, even though they would have the same theoretical O(n). Also, making a perfect hash also can be inefficient, since perfection means exactly one cell for every element with no extras. In the real world, that's nearly impossible except for the simplest of sets.

Finally, to compare to your linked list, consider this. With a linked list, the worst case is to ALWAYS traverse the full list. An average access is going to be 1/2 * the length of the list. In a tree where elements are hashed to a linked list, the worst case is going to be to traverse the longest linked list in the tree, not the total number of elements in the tree. An average search will be something like 1/2 * the average length of the linked lists, assuming a reasonable even distribution. (In other words, with 100 elements evenly distributed in 5 lists of 20 each, the average search would be about 10 elements.) If those 100 elements were in a single linked list, the average search would be 50 elements, assuming even distribution of searches through the list.

Hopefully, this doesn't confuse the matter too much for you.

If this answers your question, please accept this answer to remove the question from the unanswered question pool. Let's keep up on forum housekeeping. ;-)

Improve this answer
12
  • I got your point but but whole point is about the direct access to the element in the array. Lets say you don't know the index position of the element in the array then you need to traverse the whole array, or let me say you have traverse through all hashes of your hash table, so you will have running time of O(n). No? . P.S.: You answer was useful but not answering my question completely, yet. so, just +1'ed.
    – hagrawal7777
    Aug 1, 2015 at 18:19
  • I don't think it is very practical that hash will be continuous number like in the case of hash based on birth dates. Hash will mostly be some random number, so in order to search a particular hash, you need to traverse the whole hash table.
    – hagrawal7777
    Aug 1, 2015 at 18:22
  • 1
    No. The point of a hash function is that when you apply it to a given value, it always produces the same result. That means that when you hash a value, the result is the index, so you do indeed know the index. Without the hash function that gives you the index, the whole exercise is pointless and you might as well have a single linked list.
    – Cliff B
    Aug 1, 2015 at 18:24
  • In response to your second comment, a hash function does not produce a random result. It must be deterministic. In other words, given an input, it will ALWAYS produce the same output. Examples: Given word inputs, the output would be the ASCII value of the first letter. Or, given an input of a series of 3 numbers, the hash could be the sum of those numbers. Given a number. the hash is that number % 5 (which would be a number between 0 and 4, no matter what the number.) The point is that it is NOT a random result, but a clearly calculated and consistent result.
    – Cliff B
    Aug 1, 2015 at 18:30
  • 1
    I don't know if it works exactly as you want for Rob and Alison but if you take the numeric representation of each letter in ASCII, and you do a % 5 at the sum, you can create a hash function that has as output a number from 0 to 4 for every possible name. Rob is 82 + 79 + 66 == 227 % 5 == 2. Alison is 65 + 75 + 73 + 83 + 79 + 78 == 453 % 5 == 3 (Examples are in uppercase)
    – ChrisG
    Aug 1, 2015 at 19:59
1

Let's assume at first that we want to store all the users in a database. In the first case we use the first letter of their name as the index value, and we link the user behind the previous one, if there is already a user with a name that starts with the same letter. For example we have the array

['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

and each letter becomes the head of linked list. Now we only have 26 indexes, something that will make our linked lists pretty long and we will have to traverse them in O(n), which is linear and will take a lot of time since the lists are long.

Now let's put the birthdates of the users in the equation. Now the index could be the number of the day they were born, so we could have an array with 31 indexes like that:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]

If we use the month too we could have 12*31 == 372 indexes, that will make our array even larger, and so our linked lists will get smaller by each step. Since we can have random access to our array (we can say array[15] for example) we decrease the time needed to find each user. Hope that helps a little.

Improve this answer
4
  • Ok, I got that explanation. In first case as well when hashing based on first letter you have got the O(n/26). But my confusion is that how shorter chain can improve the running because it will become more a linked list like search. Right? For your point on random access, yes I would agree it is continuous number like 1,2,3.... But how about if your hashes are not continuous number but some random number. In that case you cannot do random access of array like array[15] because you don't know which index of the array element is sitting.
    – hagrawal7777
    Aug 1, 2015 at 18:16
  • So, you have traverse the whole array and your running time becomes O(n)
    – hagrawal7777
    Aug 1, 2015 at 18:16
  • See my comments above.
    – Cliff B
    Aug 1, 2015 at 18:32
  • The whole logic behind a hash function is that you take as input something you know, like a name, or a date, or both, and the hash function gives you a deterministic output for every input you give it.
    – ChrisG
    Aug 1, 2015 at 20:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .