Well, let's say we have an array of 50,000 elements. Now, let's say the first # is 12...so now we scan the rest of the 49,999 elements and add up all the 12's.
Now you move on to the next element of the array, let's say element 2 is 520. So now we scan through the rest of the 49,998 elements and add 1 for each 520 we encounter. Etc etc, all the way through the array. Needless to say, that's a lot of array scanning.
You could say, well, first scan the array to see which unique #'s it has and create a new array with only those #'s, that way you won't have to scan 50,000 elements each time if there are only say, 500 unique #'s. Only problem is, to build up this list of unique #'s you have to scan your new "index" array for each element of the original array to see if it exists. So you'll still have TONS of array scanning. Also, you're index array will originally have to be as large as your original array since your original array *might* be composed of all unique #'s. In other words, you are using double the amount of space as your original array (which might be alot if you were doing this with a large .bmp)
The hash table does it different. It goes through the 50,000 elements ONCE and ONCE only. Each time it gets to the next element it converts it to a string and then hashes that and checks if a value (the count value) already exists. If it does, it increases that value by 1. If it does not, it sets that value to 1. Then it moves on to the next element in the array and does the same.
So basically, instead of scanning through a full array, it instead creates a hash value and uses that as an index into it's internal array. It's *not* scanning the array when it adds an entry. It simply tacks that entry onto the back of the list at the index that the hash algorithm returns.
The only time it does any scanning is when you are retrieving values - and even then it only scans if there have been hash collisions. So as long as you make your hash table big enough, you'll have very few collisions (1000 objects in a hashtable size 1000 usually results in an average of maybe 2 objects per index, with a max of maybe 6-8 objects in a single index with standard semi-random data). So in other words, on average it'll have to scan through 2 entries and at most 6-8 (and oftentimes there is only one entry and so no scanning is needed.)
Simplified, you can think of it this way, a hash-table is an array that uses a string as it's index, not a number. The only difference is that internally it changes that string into a #. The only reason it does any scanning is when more than one string index generated the same # index, and that scanning is only done on retrieval.*
*-well, that's not 100% always true. I do have insertion functions that scan - these are useful when you want to overwrite the object stored for a particular key. The standard insertion simply tacks the object to the end of the list at that index.
Now you move on to the next element of the array, let's say element 2 is 520. So now we scan through the rest of the 49,998 elements and add 1 for each 520 we encounter. Etc etc, all the way through the array. Needless to say, that's a lot of array scanning.
You could say, well, first scan the array to see which unique #'s it has and create a new array with only those #'s, that way you won't have to scan 50,000 elements each time if there are only say, 500 unique #'s. Only problem is, to build up this list of unique #'s you have to scan your new "index" array for each element of the original array to see if it exists. So you'll still have TONS of array scanning. Also, you're index array will originally have to be as large as your original array since your original array *might* be composed of all unique #'s. In other words, you are using double the amount of space as your original array (which might be alot if you were doing this with a large .bmp)
The hash table does it different. It goes through the 50,000 elements ONCE and ONCE only. Each time it gets to the next element it converts it to a string and then hashes that and checks if a value (the count value) already exists. If it does, it increases that value by 1. If it does not, it sets that value to 1. Then it moves on to the next element in the array and does the same.
So basically, instead of scanning through a full array, it instead creates a hash value and uses that as an index into it's internal array. It's *not* scanning the array when it adds an entry. It simply tacks that entry onto the back of the list at the index that the hash algorithm returns.
The only time it does any scanning is when you are retrieving values - and even then it only scans if there have been hash collisions. So as long as you make your hash table big enough, you'll have very few collisions (1000 objects in a hashtable size 1000 usually results in an average of maybe 2 objects per index, with a max of maybe 6-8 objects in a single index with standard semi-random data). So in other words, on average it'll have to scan through 2 entries and at most 6-8 (and oftentimes there is only one entry and so no scanning is needed.)
Simplified, you can think of it this way, a hash-table is an array that uses a string as it's index, not a number. The only difference is that internally it changes that string into a #. The only reason it does any scanning is when more than one string index generated the same # index, and that scanning is only done on retrieval.*
*-well, that's not 100% always true. I do have insertion functions that scan - these are useful when you want to overwrite the object stored for a particular key. The standard insertion simply tacks the object to the end of the list at that index.