Mhash 'random' method is supposed to return a valid node id given
an arbitrary integer, likely generated randomly. But on some
values it was returning 'end' marker despite emptiness of the
container.

This was because of confusion in usage of mh_size() and mh_end().
Mh_size() means real number of objects, stored in the cache,
while mh_end() means hash capacity, or 'number of buckets' as it
is named. Generally capacity is bigger than size, and sometimes
it led to a situation like this:

    size = 1
    capacity = 4
    rnd = 3

    [0]  [1]  [2]  [3]
     -    -    x    -

When code iterates only 'size' times, looking for an element
starting from 'rnd' position, it will not find anything. It
should iterate 'capacity' times instead.