Why are linked lists almost always used with a separate chain?

Question

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

Answer 1

If you have an object vector, copying objects can be expensive, so most general-purpose hash tables use linked lists that don't need a copy when deleting or pasting. However, deleting from a hash table is actually quite a rare operation in most codes, and insertion should be rare (you don't want to grow long chains), so whenever I implemented hashes myself, I always used vectors for chains, no problem .

An alternative explanation is that a linked list is a container that people blindly reach - see the comments on my blog here to learn more about this.

Answer 2

You can use the vector / ArrayList, but:

• , ArrayList , , , O (1) .
• ArrayLists , , .
• ArrayLists , .