If you want persistence (in the functional sense) and ordering I'd rather implement a skip list personally. You can use your existing hash code as a randomiser

If you want persistence (in the functional sense) and ordering I'd rather implement a skip list personally. You can use your existing hash code as a randomiser to determine level promotion. If you're going to keep it around you may as well make use of it. Skip Lists also have the nice property that you can stick a immutable linked list facade on them (since the base layer is fully linked)