Is there a difference between an array of Linked Lists and a Hash table?

My question is pretty much what's up above. According to the diagrams I see of a hashtable, it seems like for example: Hashtable temp1 = new Hashtable(20); SList[] temp2 = new SList[20]; Assuming SList is a singly linked list, isn't temp1 almost the same as temp2? I'm just trying to understand hash tables a little better. Thanks!

asked Jan 9, 2015 at 21:00 145 2 2 silver badges 8 8 bronze badges

These two are distinct. A hashtable is indexed by some sort of an object called key of a type with a well-defined operation called hash defined on it. Depending on the value of the hash, the pair (Key, Value) is stored in the appropriate place in hash table. In general hash functions should have vastly different values for almost identical objects. Hashtables use lists to take care of collisions - distinct keys can yield the same hash - if so, they are stored at the same spot (in the corresponding list) in this model of collision resolution. Hashtables can use arrays of lists internally.

Commented Jan 9, 2015 at 21:07

I see what you mean, but let's say you defined a separate class HashTableImplementation with the constructor being an array of Single linked lists. Because you're using single linked lists, collision is already taken care of and you can sort values of the same key in anyway you like. If you added a hash method to the HashTableImplementation as well as a compression function method to it, couldn't you have the exact same thing as a hash table?

Commented Jan 9, 2015 at 21:14

Yes. But you could have also used another method of collision resolution and it'd be still a hash table. What's used inside - be it an array of linked lists or just a simple array, is just an implementation detail.