Хэш-таблицы (Hash Tables )

dbstalker, 23 июня

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

Тэги: SGA, общее

ОднаКнопка

 

Новый комментарий

Я не спамер: введите суму 3+7



 

От авторов блога

О Блоге - прочитай перед началом.

Задать вопрос и получить ответ - уже решено 94 вопросов

Глоссарий - список терминов и сокращений


 
 

Бизнес форум

Последние темы:

Шины бу
26 апреля, 2 ответа
Потрібна порада
25 апреля, 2 ответа
Посоветуйте адвоката
25 апреля, 1 ответа