There are gazillion things on which the performance of insert depends on. The calculation of hash function indeed is O(k) for a string of length k, but it is just uninteresting in general case.

If you consider string keys of only 8 bytes of length, there are 18446744073709551616 different combinations and 8 is a constant, calculation of hash for 8-byte key is O(8) is O(1).

But at 18446744073709551616 items, insertion to hash table could still take 1 ms, whereas insertion to a beginning of list of that many items could take 584942417 years.

OTOH, while it is conceivable that you might have a collection of 4294967296 or even 18446744073709551616 items, if you've got a key of 4294967296 or 18446744073709551616 bytes to your hash table you seriously need to rethink your architecture.

There are gazillion things on which the performance of insert depends on. The calculation of hash function indeed is O(k) for a string of length k, but it is just uninteresting in general case.

If you consider string keys of only 8 bytes of length, there are 18446744073709551616 different combinations and 8 is a constant, calculation of hash for 8-byte key is O(8) is O(1).

But at 18446744073709551616 items, insertion to hash table could still take 1 µs. And for list, where insertion to the beginning would be O(n), and the insertion/copying of one item took only one nanosecond at the end of the list, insertion to the beginning of a list of that many items could take 585 years.

OTOH, while it is conceivable that you might have a collection of 4294967296 or even 18446744073709551616 items, if you've got a key of 4294967296 or 18446744073709551616 bytes to your hash table you seriously need to rethink your architecture.

There are gazillion things on which the performance of insert depends on. The calculation of hash function indeed is O(k) for a string of length k, but it is just uninteresting in general case.

If you consider string keys of only 8 bytes of length, there are 18446744073709551616 different combinations and 8 is a constant, calculation of hash for 8-byte key is O(8) is O(1).

But at 18446744073709551616 items, insertion to hash table could still take 1 ms, whereas insertion to a beginning of list of that many items could take 584942417 years.

There are gazillion things on which the performance of insert depends on. The calculation of hash function indeed is O(k) for a string of length k, but it is just uninteresting in general case.

If you consider string keys of only 8 bytes of length, there are 18446744073709551616 different combinations and 8 is a constant, calculation of hash for 8-byte key is O(8) is O(1).

But at 18446744073709551616 items, insertion to hash table could still take 1 ms, whereas insertion to a beginning of list of that many items could take 584942417 years.

OTOH, while it is conceivable that you might have a collection of 4294967296 or even 18446744073709551616 items, if you've got a key of 4294967296 or 18446744073709551616 bytes to your hash table you seriously need to rethink your architecture.