And also remember the context here: you're removing duplicate value's from an array. So you're inserting N items into a set. If the set insertion or enumeration involves even a O(log(n)) operation, you're at nlogn.
type HashSet<K> = HashMap<K, ()>;
In which case it has all the properties of a hashmap except it doesn't use values. That's what we need for this problem.
I'm only aware of partial solutions to that problem, of which top down Radix sort is in fact one. But once you do that you don't need the table to solve the problem anyways, you've already got your discrimination function and you'd just pass that over the data.
I cannot see why the tabular part of the hash table proposed solution is anything more than cargo culting.
How do you do that over all inputs? If there is a generalized non-probabilistic perfect hash function I am unaware of it and I'd like to be aware of it.
Then you're not at O(1). You cannot say "O(1) except in the worst case". That is like saying, "It is blue except when you look at it."
But you don't need these mitigations (most of which are O(log n)) because you never had the hash table. You should look at American Flag sort, because morally it's actually doing something that closely approximates what you're thinking about. That's why I brought it up elsewhere in the thread.
It was a bad design to rely on hashing algorithms to never collide. But it's worth noting that even SHA1 is much more robust than most hash table algorithms, which are meant to run even faster.