title: Is using a hash table valid in counting sort (in place of an array)?
body: <p>The classic counting sort example requires you to build an array of size equal to the greatest integer of your input array.</p>
  
  <p>For example, if your array is [1, 6, 3, 10000, 8] you would need an array 10000 long for the counting sort.</p>
  
  <p>Could this not be done in the same linear time using a hash table on the integers?  Just a simple map?</p>
  
  <p>In python, it'd be something like:</p>
  
  <pre><code>counting_map = {n: 0 for n in input_array}  # start by mapping all to 0
  for num in input_array:
      counting_map[n] += 1
  </code></pre>
  
  <p>I know this really only works well for integers, but in that case is the mapping solution not superior?</p>
  
  <p>Time-complexity wise, you initialize the map in O(n) time, then iterate through the array in O(n) time, then perform hashing functions on input in O(1) time.  (Obviously big-O notation isn't the final determining factor of whether an algorithm is good, I just want to make sure I have the theory correct here).</p>
  
  <p>Is this a good solution, or does the "original" counting sort still do something superior that I don't see?  I'm also curious why a "hashmap-based counting sort" hardly returns any Google search results, making it seem like it's hardly ever used.  Is the overhead of the hashing enough to outweigh its smaller memory footprint?</p>