How does hash table work for dynamically lengthed array?

You are correct, a hash table where the keys are implemented as a linked list would not be O(1), because the key search is O(n). However, linked lists are not the only expandable structure.

You could, for example, use a resizable vector, such as one that doubles in size each time it needs to expand. That is directly addressable without an O(n) search so satisfies that O(1) condition.

Keep in mind that resizing the vector would almost certainly change the formula that allocates items into individual buckets of that vector, meaning there's a good chance you'd have to recalculate the buckets into which every existing item is stored.

That would still amortise to O(1), even with a single insert operation possibly having to do an O(n) reallocation, since the reallocations would be infrequent, and likely to become less frequent over time as the vector gets larger.

You can still map the elements of a linked list to a hash table. Yes, it's true we do not know the size of the list beforehand, so we cannot use a C-style or non-expandable array to represent our hash table. This is where vectors come into play (or ArrayList if you're from Java).

A crash course on vectors will be: if there is no more space in the current array, make a new array of double size, and copy the previous elements into it. More formally, if we want to insert n+1 elements into an array of size n, then it will make a new array of size 2n. For the next overflow, it will create an array of size 4n and so on.

The following code can map values of a linked list into a hash table.

void map(Node* root) {
    vector<int> hash;

    while(root){
        hash[root->val]++;
        root = root->next;
    }

    for(int i = 0; i<hash.size(); i++){
        cout<<hash[i]<<" ";
    }
}