- Forum
- General C++ Programming
- Hash tables vs arrays
Hash tables vs arrays
closed account (4ET0pfjN)
Hi, I am a little confused with direct addressing in arrays vs using hash tables with chaining.
eg: let's say 900 items stored in 900 indices in a direct addressing array so
item 1 in index 0, item 2 in index 1 VS hash tables where we having each array
act as pointers to a linked list that hold the actual 900 items, but isn't it the same space requirement either way b/c 900 items to store is stil going to need
900 indices or a mix of linked lists that add to 900. Is it b/c a chaining allows for pointers so we never actually store actual data and only reference it? What am I missing here?
eg: let's say 900 items stored in 900 indices in a direct addressing array so
item 1 in index 0, item 2 in index 1 VS hash tables where we having each array
act as pointers to a linked list that hold the actual 900 items, but isn't it the same space requirement either way b/c 900 items to store is stil going to need
900 indices or a mix of linked lists that add to 900. Is it b/c a chaining allows for pointers so we never actually store actual data and only reference it? What am I missing here?
Last edited on
If you're storing 900 elements, you will need to make room for 900 elements no matter what. I don't quite understand what your question is.
closed account (4ET0pfjN)
Sorry for confusion, I guess what I'm saying then is is hash table only good for lookups since we can find a value by using a simple calculation (eg: hash function). I'm not sure actually...
You are confused...
with array you can access elements by their indices... a[0] a[1] etc...
but lets say you want to store addresses of people. Is it not nice to access addresses like address[john], address[tom]... array does not provide this facility. Has table does.
Name 'john' will return a index, depending upon the hashing function (e. g. ASCII value of J), and that number will be used to dereference the array. Problem solved, and now you can access the element address[john]
But, second problem comes, what if you want to store address[Juan]?? again j, so again it will return same index. So it is better to have a linked list at that index. So 'john' gets to be the first guy at a linked list pointed by a[j], and juan gets to be the second, and so on...
with array you can access elements by their indices... a[0] a[1] etc...
but lets say you want to store addresses of people. Is it not nice to access addresses like address[john], address[tom]... array does not provide this facility. Has table does.
Name 'john' will return a index, depending upon the hashing function (e. g. ASCII value of J), and that number will be used to dereference the array. Problem solved, and now you can access the element address[john]
But, second problem comes, what if you want to store address[Juan]?? again j, so again it will return same index. So it is better to have a linked list at that index. So 'john' gets to be the first guy at a linked list pointed by a[j], and juan gets to be the second, and so on...
closed account (4ET0pfjN)
Thanks for that, I forgot that we can use strings and use a character's ASCII integer value to represent the key item we want to insert /search, but I was googling and found this:
Since most uses of hashing for lookup involve trying to take keys in a broad range and force them into indices for a smaller range, it stands to reason that no hash algorithm can perfectly hash a sequence of unknown keys into unique indices. at http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx, but I am not sure why we would want to have keys forced into a smaller range of indices, is this to do with chaining like you mentioned?
Since most uses of hashing for lookup involve trying to take keys in a broad range and force them into indices for a smaller range, it stands to reason that no hash algorithm can perfectly hash a sequence of unknown keys into unique indices. at http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx, but I am not sure why we would want to have keys forced into a smaller range of indices, is this to do with chaining like you mentioned?
Topic archived. No new replies allowed.