What does it mean?

[Asif_NSU]

This is probably a stupid question, but i dont get the answer. Plz help me understand.

Question:
How could a linked list and a hash table be combined to allow someone to run through the list from item to item while still maintaining the ability to access an individual element in O(1) time?

Solution:
Create a hash table where the elements of the array are pointers to linked list objects. You have your linked list as normal, but when you add an element to the linked list, "you also add a pointer to that element from the correct place in the hash table specified by the hash value of the data in the new linked list element".

I dont understand what you also add a pointer to that element from the correct place in the hash table specified by the hash value of the data in the new linked list element. means.

[jwenting]

OK, I assume you know what a linked list is else it gets cumbersome :)

A hashtable is a special type of map where the items are indexed on the hashcode of the key.
The hashcode is an integer calculated over the item being stored, in this case your data.
The hashtable contract specifies that items with identical value have identical hashcodes as well.
In other words if you have 2 objects a and b where a == b, then a.hashCode() == b.hashCode().
This facilitates fast lookup. Internally the items are indexed on hashcode, when you try to find an object by the key the hashcode of that key is calculated. That provides an index into the datastorage where a group of items stored with that hashcode are kept.
If the hashing algorithm is perfect there will always be only 1 item there. If not you will at least have a far smaller number of items to compare with your key than the entire collection.

What you're said to do is store a key into your stored data into a hashtable.
As the data you store a pointer to that data, the same pointer which also indexes that same data in your linked list.

So you get both a List (fast sequential lookup) and a Map (fast random lookup) of the same data for practically the price of one.
List Data Hashtable
1 *O1 O1.hashCode()
2 *O2 O2.hashCode()
3 *O3 O2.hashCode()
4 *O4 O2.hashCode()
5 *O5 O2.hashCode()

Now if you want to look up an item and you know the key (from which you can calculate the hashcode) you can do it through the hashtable.
If on the other hand you want to look up elements by index or iteration you can use the list.

[Asif_NSU]

Suppose i have a linked list of say integers. So whenever i add a new integer to that linkedlist i also:
1. calculate the hash code for that integer
2. add a pointer to that integer into the hashtable(the position of the pointer is determined by the hash code)
Is that what it means?

[jwenting]

correct.
In the case of an integer it's rather trivial as the hashcode will be the integer itself but the concept is sound.

[diogeneb]

I still do not understand. Could you please elucidate what you mean by:-

"What you're said to do is store a key into your stored data into a hashtable. As the data you store a pointer to that data, the same pointer which also indexes that same data in your linked list"

Assuming the hashtable is represented by the array Arr. If data items X, Y & Z hash to the same value (say I), then Arr would contain a pointer to the linked list containing X,Y,Z. Now, suppose someone wants to search for Z in the hashtable. Z hashes to I. Then a sequential lookup of the linked list contained in Arr is done, and Z is found. It takes O(3). How can we make it O(1)?

Thanks
Dio

[Narue]

>Then a sequential lookup of the linked list contained in Arr is done, and Z is found. It takes O(3).
That's still O(1) because it's a constant time. But if the hash function is good, the extra cost of a sequential search is negligible since the lists will all be very short. The only way to get guaranteed and exact O(1) performance as you're thinking of it is to use a perfect hash, which isn't always possible.