$orderedhash{$newkey} = $newvalue;
# is really doing

  $next_index = @KEYS;
  $KEYINDEX{$key} = $next_index;
  push @KEYS, $key;
  push @VALUES, $value;

$orderedhash{$oldkey} = $newvalue;
# is really doing

  $key_index = $KEYINDEX{$key};
  $VALUES[$key_index] = $value;