То есть Вы предполагаете, что обьем хеша будет меньше обьема массива? Это, по-моему, в общем случае неверно. А если обьем хеша мал, то цена поиска в нем будет не меньше, чем цена сортировки изначального массива.