Computing a histogram with the number of extant values not known in advance (This may be more fitting for CSTheory, I'm not sure.)

I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for the following problem:

Unknown-Number-of-Bins Histogram

Inputs:


An array of integers $a$, of length $n$.


Outputs: 


An array of integers $\text{bins}$ of length $m &lt;= n$.
An array of unsigned integers $\text{counts}$, also of length $m$.


Output Requirements: 


For every $i \in \{0...m-1\}$ it must be the case that 

$\bigl|\bigl\{ j \in \{0...n-1\} \mid a_j = \text{bins}_i \bigr\}\bigr|$
$ = \text{counts}_i$

In other words, $\text{bins}$ and $\text{counts}$ constitute a histogram of $a$, with one bin for every unique value in $a$.
It is not required for $\text{bins}$ or $\text{counts}$ to be sorted.


Other Notes:


Complexity is considered as a function of both $n$ and $m$. 
Low time complexity is required both asymptotically and for relatively low values of $m$ - but it is not required for low values of $n$.
No hiding monstrosities in the $\mathop{O}(\cdot)$ constants please! This should be usable in practice.
A parallel(izable) approach? You are most welcome :-)
Low space complexity is a plus.
Deterministic algorithms preferred, and barring that, go easy on those coin flips.


Clearly, there are many way to go about this, some very straightforward, e.g. "sort the input, then build a sorted histogram in a single pass", in $\mathop{O}(n \log{n})$ time. Of course I'm interested in something better....
Often, in order to improve a sorting-based algorithm from $O(n\log n)$ to $O(n)$, one can use hash tables. In this case, you would use a hash table of size $O(n)$. Each entry of the hash table would store an integer and its count. The entire algorithm would now run in expected time $O(n)$.