chsalvia
asked on
Hashtable structure
I'm slightly confused as to one aspect of how hashtables work. I understand that a hashtable is really just an array of key values, which can be turned into numbers using a hash function, which then allows you to map those values to data values.
But, I'm not sure if a hashtable is supposed to be created using one or two arrays. I would think you'd need two arrays to create a hashtable - one for key values and one for data values.
Is this correct? Some websites seem to imply there is only one array, which holds the data values, which are simply located at the hash index of a list of predetermined key values.
I'd think though, that when you perform a lookup, it would need to hash the lookup keyword, then check the keyword array for that index value, and see if the key matches. THEN, it would look up the same hash index in the data array, and return that value.
Right?
But, I'm not sure if a hashtable is supposed to be created using one or two arrays. I would think you'd need two arrays to create a hashtable - one for key values and one for data values.
Is this correct? Some websites seem to imply there is only one array, which holds the data values, which are simply located at the hash index of a list of predetermined key values.
I'd think though, that when you perform a lookup, it would need to hash the lookup keyword, then check the keyword array for that index value, and see if the key matches. THEN, it would look up the same hash index in the data array, and return that value.
Right?
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
A skiplist works with sorted linked lists what has the advantage that you can get a sorted list of all items or iterate through all items in order (regarding to the key). Furthermore, a skiplist automatically is balancing all entries which makes it nearly as fast as a balanced binary tree but has no costs for balancing (cause that is done atomatically).
A skiplist adds all entries to a sorted linked list. The node of any fourth entry (randomly calculated) was added to a second linked list, any 16th to a third list and so on:
3 L
2 D L S
1 B D F L Q S X Z
0 A B D F G H L M N Q R S U X Y Z
Here level 0 holds all entries and level 3 only one. For lookup you start at the top level and go down and right if the key to search is greater than key in the list. E. g. looking up for 'O' would start at 'L', go down to level 0, right to 'M', right to 'N'. Then, either the key was found or the new insert position. For each new entry it will be determined randomly to which lists it belongs. The maximum level is random as well.
Regards, Alex