Another approach could be to use prefixes. A 0 could separate the prefix (fixed hash part) from the suffix (random part).

  0<suffix>
  10<suffix>
  20<suffix>
  ...

Combined with auto-completion, you preserve the main advantage (ordering) and you are able to quickly compute the hash.