I'm trying to implement a dynamic hash table using chain hashing (each element in the array is a linked list). I want to know, complexity wise, which of the following possibilities is better: 1. I should double the array size when the array is full, meaning each linked list has at least one element. 2. I should double the array size when I have N elements in total (in all of the linked lists) - where N is the array size.
Plenty of hash table implementations in the wild including several in the C++ standard (unordered_set, unordered_map).
To answer your question, it's better to double up the bin count (internal array) when the element count reaches N. The other way around would be harder and time consuming (finding out if all bins are full).
You need to keep a member that holds the element count.
You don't need to worry yourself about users using a bad hash function like { return 0;}.