Is using a hash table valid in counting sort (in place of an array)?
You can do that, and the construction would be O(n) with the obvious memory benefit.
With one little problem.
To output the sorted array, you'll still need to sort the hash table keys. And that problem is exactly what you were trying to solve in the first place.