For the sake of discussion let's exclude hash collisions and the resulting "scanning" that takes place, since it is theoretically possible that you won't have a hash collision with a certain subset of data, and then it behaves essentially just like an array.
So what's the difference? Well, the difference is this - in your proposed solution you have the original array, and then you create two arrays - let's call them the "already-exists" and "count". You insert each number you see in the original array into the "already-exists" array at element X, and then increase the count at element X on the count array.
So if your original array is like so
1 2 4 2 5 1
The first scan would put 1 into already-exists[0], and then add 1 to the same index of the count array -- count[0] = count[0] + 1.
So now you move on to the second element of the original array. Now - to see if this value exists - you have to scan the "already-exists" array. Each time you move to the next element in the original array, you have to scan the length of the already-exists array.
So if you had 50,000 elements in your original array, you'd have to scan your 50,000 element "already-exists" array to see if the number was seen before. Granted, you might not have to scan the full length of the array if the # is found earlier, but you still have to do some scanning.
The reason this will take forever is because at element 49,000 you may have 49,000 lookups in the "already-exists" array (if the number isn't found and the whole array is scanned), and then when you move to the next element, 49,001 - you may have 49,001 lookups and then 49,002 and so on and so forth.
The hash table doesn't need to scan itself to see if the number exists - instead it uses the number itself to generate a hash-value that corresponds to an element within itself. If something is already stored there, then obviously the number already exists. In fact, we can store the "count" value there.
The whole point of a hash table is that it doesn't need to scan it's entire length to find an element - it uses the key (whatever key you provide it - in this case it uses the number you provided and converts it to a string and hashes it) and that key value IS the index where that value is stored.
So if you have the following hash lookup
hash.getEntry( 53352 )
the hash table doesn't scan it's entire length to see if 53352 exists anywhere. It converts 53352 to it's string equivalent "53352", and then converts that string to a # (using a hashing algorithm like the one described in an earlier post). This number is then used as an index to the hash tables internal array.
So no scanning is done. Instead, it generates the index based on the key provided, and then looks in that index.* If something is there, we know the # already exists (because something was stored with the same key - in this case the same number). If nothing is there, we know the # doesn't exist.
I don't know how to break it down any more - I'm sure it could be said clearer but probably not by me :P. The difference between a hash table and an array - in the way we are using them here - is like the difference between indexing an array with a known index versus scanning a list for an element.
What is faster:
someArray[200]
or
someList.FindValue( someValue )
Obviously the array is, because it can nearly instantly jump right to index 200 and retrieve the value there (if any). The list however, has to scan through each element and see if that particular element = someValue. Worst case scenario, the list reaches the end (X number of scans where X is the length of the list) and didn't find the value. The array is always constant time - either there is a value at 200 or there isn't.
Basically, the hashtable behaves like the array in the example above. It uses the provided key as an index into it's array and there's either a value there or there isn't. It doesn't really need to scan at all**. The array method proposed here by you & others requires you to scan through some index array to see if the # already exists, for *every* single # in the original array. While this is faster than a hash lookup on a small array, the hash table will end up being much faster on a large array.
*Actually, the hash algorithm generates a number based on an input string. THIS number will ALWAYS be the same for a given key. Just like an encryption algorithm always produces the same results on the same input with the same key. However, the hash table is only an X element array, so we need to turn the number generated (which can be very large) into a value between 0-X so that we can use it to index the hash table. That's what the mod operation is for (described in the post a few up) - it takes the number generated and reduces it to between 0-X.
**omitting hash collisions. I probably shouldn't have mentioned them in the above posts because they don't have that much bearing on how a hash table works on the conceptual level, and by mentioning them I only made the whole concept harder to understand.
So what's the difference? Well, the difference is this - in your proposed solution you have the original array, and then you create two arrays - let's call them the "already-exists" and "count". You insert each number you see in the original array into the "already-exists" array at element X, and then increase the count at element X on the count array.
So if your original array is like so
1 2 4 2 5 1
The first scan would put 1 into already-exists[0], and then add 1 to the same index of the count array -- count[0] = count[0] + 1.
So now you move on to the second element of the original array. Now - to see if this value exists - you have to scan the "already-exists" array. Each time you move to the next element in the original array, you have to scan the length of the already-exists array.
So if you had 50,000 elements in your original array, you'd have to scan your 50,000 element "already-exists" array to see if the number was seen before. Granted, you might not have to scan the full length of the array if the # is found earlier, but you still have to do some scanning.
The reason this will take forever is because at element 49,000 you may have 49,000 lookups in the "already-exists" array (if the number isn't found and the whole array is scanned), and then when you move to the next element, 49,001 - you may have 49,001 lookups and then 49,002 and so on and so forth.
The hash table doesn't need to scan itself to see if the number exists - instead it uses the number itself to generate a hash-value that corresponds to an element within itself. If something is already stored there, then obviously the number already exists. In fact, we can store the "count" value there.
The whole point of a hash table is that it doesn't need to scan it's entire length to find an element - it uses the key (whatever key you provide it - in this case it uses the number you provided and converts it to a string and hashes it) and that key value IS the index where that value is stored.
So if you have the following hash lookup
hash.getEntry( 53352 )
the hash table doesn't scan it's entire length to see if 53352 exists anywhere. It converts 53352 to it's string equivalent "53352", and then converts that string to a # (using a hashing algorithm like the one described in an earlier post). This number is then used as an index to the hash tables internal array.
So no scanning is done. Instead, it generates the index based on the key provided, and then looks in that index.* If something is there, we know the # already exists (because something was stored with the same key - in this case the same number). If nothing is there, we know the # doesn't exist.
I don't know how to break it down any more - I'm sure it could be said clearer but probably not by me :P. The difference between a hash table and an array - in the way we are using them here - is like the difference between indexing an array with a known index versus scanning a list for an element.
What is faster:
someArray[200]
or
someList.FindValue( someValue )
Obviously the array is, because it can nearly instantly jump right to index 200 and retrieve the value there (if any). The list however, has to scan through each element and see if that particular element = someValue. Worst case scenario, the list reaches the end (X number of scans where X is the length of the list) and didn't find the value. The array is always constant time - either there is a value at 200 or there isn't.
Basically, the hashtable behaves like the array in the example above. It uses the provided key as an index into it's array and there's either a value there or there isn't. It doesn't really need to scan at all**. The array method proposed here by you & others requires you to scan through some index array to see if the # already exists, for *every* single # in the original array. While this is faster than a hash lookup on a small array, the hash table will end up being much faster on a large array.
*Actually, the hash algorithm generates a number based on an input string. THIS number will ALWAYS be the same for a given key. Just like an encryption algorithm always produces the same results on the same input with the same key. However, the hash table is only an X element array, so we need to turn the number generated (which can be very large) into a value between 0-X so that we can use it to index the hash table. That's what the mod operation is for (described in the post a few up) - it takes the number generated and reduces it to between 0-X.
**omitting hash collisions. I probably shouldn't have mentioned them in the above posts because they don't have that much bearing on how a hash table works on the conceptual level, and by mentioning them I only made the whole concept harder to understand.