Gah, I see the confusion, in one sentence I was talking about single element access, and in the next about full copy, and I was just assuming the jump was clear

Gah, I see the confusion, in one sentence I was talking about single element access, and in the next about full copy, and I was just assuming the jump was clear to the reader but clearly it wasn't. So just to be fully explicit: Single element access in a hash table is only ~O(1) when it's amortized over many accesses of a table that assumes few collisions (due to size and a good hash function). But the real worst-case performance, in case of incessent collisions, is going to be the performance of whatever data structure hides behind each bucket: O(n) if it's a naive list, O(log_x n) if it's a simple tree, etc. So copying a full list into a hash table is not O(n), it's O(n^2) if the buckets are backed by naive lists, O(n log_x n) if the buckets are backed by simple trees, or another superlinear bound for another backing data structure. How about it? And personally I would still prefer to de-dupe an array by dumping into a hashtable and back, but the OP is right, you have to be careful about implementation details of both the hashtable and the hashing function. The simple hashtable-and-back can produce much worse perf than sort-and-dedupe if stars don't align.