CODEWITHSUNDEEP
data-structuresvectorhashtablelinked-list
Jason Baker
Jason Baker

Reputation: 198517

Why are linked lists almost always used with separate chaining?

It seems as though every time I see a mention of separate chaining in a hash table, a linked list is used as the data structure to store items with collisions. Why is this? For instance, why couldn't you use a vector/array data structure?

Upvotes: 3

Views: 3157

Answers (2)

Mark Byers
Mark Byers

Reputation: 837906

You could use an vector / ArrayList but:

  • You don't need any of the features an ArrayList provides that a linked list doesn't have, such as indexing into the list in O(1) time.
  • ArrayLists tend to have a capacity greater than their current length, which wastes memory.
  • ArrayLists need to increase their capacity occasionally which is slow.

Upvotes: 5

anon
anon

Reputation:

If you have a vector of objects, then copying the objects can be expensive so most general purpose hash tables use linked lists, which don't require a copy on deletion or insertion. However, deletion from a hash table is actually rather a rare operation in most code, and insertion should be rare (you don't want to grow long chains) so whenever I've implemented hashes myself I've always used vectors for the chains, with absolutely no problems.

The alternative explanation is that the linked list is the container that people reach for blindly - see my blog comments here for more opinion on this.

Upvotes: 2

Related Questions