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?
+1
A:
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.
anon
2010-01-16 13:48:36
Could you point me towards which blog post you're talking about specifically? I'd be interested to hear more on this.
Jason Baker
2010-01-16 13:56:06
http://punchlet.wordpress.com/2009/12/27/letter-the-fourth/
anon
2010-01-16 14:01:13
+4
A:
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.
Mark Byers
2010-01-16 13:49:16
Playing the devils advocate: a) You don't need the ability to insert into the list. b) Pointers need to be updated on inserting elements, which is slow. c) Due to overhead from pointers, Linked Lists are always larger than an array list of the same size, which wastes memory.
meriton
2010-01-16 14:09:31
b) You only have to update one or two pointers when updating a linked list. When updating an arraylist you have to update a pointer and a count, so there's no real saving here. c) This is only true if there is no extra capacity in the array list, and even then it still isn't true for lists with one element.
Mark Byers
2010-01-16 14:18:45