Quick question: What would be the most efficient way (apart from a simple search) of testing if a sortable key exist in a hash AND (here's the real question ) if it doesn't to get the next highest one.

This isn't a quick question at all. Essentially its not an operation that hashes are suitable for. Depending on how often you fetch and how often you store will determine the best way to do it. If the data is relatively static and you are looking at optimising look up times then I would consider a pair of arrays, one with the keys, they other with the values. Binary range searching isn't difficult and makes look up times fast. OTOH, if you have a good ratio of stores to fetches then a tree structure will be more suitable. Some hybrid may also be preferable.

PS: Did you really mean defined there? Did you actually mean exists?