If your range of keys is kept reasonably sane (e.g. not jumping from 1 to 100 to 10000), consider using an array instead of a hash. This doesn't solve the problem of finding the next or previous item in the list (a jump leaves that element in the array undefined), but it could be considerably more efficient, depending upon your application. An array, in practice, is equivalent to a numerically-addressed hash. So long as you're not doing too much jumping, you're not likely to be wasting a significant amount of space by ignoring the gaps.