`_histogram` IS only applied to integers from 0 to n_labels - 1. Other than that, I really don't care anymore, except that your statement that my approach is 2x slower is simply not true:

```python
In [33]: from sklearn.preprocessing import resample_labels, resample_labels2
In [34]: import numpy as np
In [35]: n = 1000000
In [36]: for k in [2, 10, 1000, 10000]:
   ....:         print k
   ....:         probs = {}
   ....:         # ensure at least 1 instance of each label
   ....:         y = np.hstack((np.arange(k), np.random.randint(k, size=n - k))).astype('S4')
   ....:         prob = np.random.rand(k)
   ....:         prob = {str(i): v for i, v in enumerate(prob / prob.sum())}
   ....:         %timeit resample_labels(y, prob, n * 2)
   ....:         %timeit resample_labels2(y, prob, n * 2)
   ....:     
2
1 loops, best of 3: 4.53 s per loop
1 loops, best of 3: 3.64 s per loop
10
1 loops, best of 3: 4.84 s per loop
1 loops, best of 3: 3.51 s per loop
1000
1 loops, best of 3: 4.76 s per loop
1 loops, best of 3: 3.35 s per loop
10000
1 loops, best of 3: 5.42 s per loop
1 loops, best of 3: 4.25 s per loop
```