Тут вдруг стало интересно: а какие хеш функции используются САПом при работе с хеш таблицами? И по каким параметрам они выбираются?
Вообще доступ по хешу считается довольно спорным из-за того, что все зависит от удачности выбора хеш функции для конкретного случая. И вроде как бинарный поиск - разумная альтернатива в общем случае.
Но в САПе я как-то все сталкивался с тем, что хеш таблицы быстрее сортированных. Это они так удачно функции выбирают или мне так просто везло?

Может быть вам стоит лучше изучить вопрос о самих алгоритмах, ассимптотических выражениях и оценки времени выполнения для различных алгоритмов? Вот, например, фундаментальный труд на эту тему, который обычно способствует просветлению: "Алгоритмы: построение и анализ " , авторы Томас Кормен, Чарльз Лейзерсон, Рональд Ривест и Клиффорд Штайн. Ну или всеми любимый Дональд Кнут и его "Искусство программирования".
Что значит "быстрее\медленнее"? На какой именно операции(вставка-удаление-изменение)? При каком размере?
Например: поиск в отсортированной таблице по binary serach оценивается как O( log2( n ) , а поиск в хэш-таблице O (1)

Да, вроде бы изучал, правда, возможно не очень детально. Спасибо за книжку, постараюсь почитать.
Но не очень понимаю как это мне поможет в данном вопросе?
Разумеется на чтение - всё таки в подавляющем большинстве случаев таблица заполняется один раз, а потом много раз считываются данные. Как пример - лоакальный кеш. Быстрее/медленнее - время, которое требуется на считывание одной записи по ключу таблицы (а какие еще есть варианты?). Размеры разные =) В общем случае как я понимаю на объемах до 100 записей разница не существенна.

Да, я разумеется знаю про O-нотацию. Но на практике интересны не теоретические ассимптоты, а абсолютные значения. Нами любимый хеш-индекс по сути - двухмерный массив. Индекс первого измерения - результат применения хеш функции к ключу. Второй - список адресов совпавших записей. Если наша хеш функция - остаток от деления на 5 (т.е. все записи будут распределяться по 5 массивам), а всего записей 1000000, то понятно, что O(1) вроде как и не совсем от 1, скорее от n. Всё зависит от хеш функции. А вот как ее САП выбирает и есть вопрос Количество записей все-таки заранее не известно.

На практике разницей во времени поиска в сортированных и хеш-таблицах для реальных задач можно пренебречь. Главное - не использовать поиск по несортированным таблицам.

Позвольте не согласиться. Пример из se30(Single Read: Sorted vs. hashed tables ) в моей системе показывает разницу в 20%(т.е. чтение из хэш-таблицы на 20% быстрее). При том, что там речь идет о чтении 250 раз из таблицы длинной 1000. В продуктивной задаче данных может быть и побольше, выигрыш будет аналогично - больше.
Другое дело, что всегда стоит подумать в зависимости от задачи в целом. Правильно построенный механизм перебора записей между собой (да ну хотя бы на примере из того же se30 в части Joining internal tables - использование параллельных курсоров - не смотря на всю свою банальность) может давать лучшую производительность даже на обычных таблицах, чем "наивный" алгоритм с использованием sorted\hashed таблиц



O(f(n)) - это не значит, что прям вот скорость\сложность алгоритма f(n) и все. а то, что скорость не превышает некоторой f(n) да еще и умноженной на некоторую константу. Т.е. есть некий порог, он точно не превышается, но до него может быть достаточно произвольное поведение.

Я имел в виду, что даже если разница будет 20%, то в абсолютном времени выполнения программы это будут секунды и единицы процентов в лучшем случае.
Как пример - в отчете MM по остаткам (с определением времени последнего прихода для остатка) идет куча чтений внутренних таблиц (45 секунд) - 2,4% от общего времени выполнения программы

Вот здесь народ много и долго спорил о "сферическом коне в вакууме"...
http://sapland.ru/blogs/obermann/?post=13135