23июн
Хэш-таблицы (Hash Tables ).
Oracle использует хэш-таблицы (hash tables)для эффективного размещения объектов в памяти. Например, хэш-таблица используется для размещения блоков данных в буферном кэше.
Что такое хэш-таблица? Это ассоциативный массив: набор пар «ключ-значение». По этому массиву можно по ключу быстро найти значение. Ключ (индекс) формируется с помощью некой хэш-функции. Важно подобрать такую функцию, которая дала бы равномерное распределение по ключам.
Для размещения объектов с помощью хэш-таблицы, оракл применяет определенный алгоритм ( хэш-функция) для преобразования названия объекта или идентификатора в число. Несколько объектов могут иметь один и тот же индекс в хэш-таблице (hash table entry). Это называется хэш-коллизией. Оракл разрешает эту проблему путем использования цепочек (chains) – все объекты, у которых получился один и тот же hash table entry связываются в цепочку указателей. То есть объекты попадают в один и тот же hash bucket. Коллизии в хеш таблицах всегда есть и будут, но распределение будет более равномерное, когда размер таблицы представляет собой простое число.
При выполнении хэш-организованного доступа к данным существенную роль играет длина цепочек (hash chains), потому что поиск по ним осуществляется линейно. Поэтому хэш – таблица должна быть достаточно большой, чтобы длина цепочки была приемлемой.
Использован материал:
http://www.dbanotes.net/Books/oracle8i_internal_services_for_waits,_latches,_locks.pdf
А здесь есть интересный материал
http://www.cs.sfu.ca/CC/354/zaiane/material/notes/Chapter11/node20.html