Непейвода Н.Н. Программирование. Раздел 4

Непейвода Н.Н. Программирование. Страница 423

Индексы представляются как последовательность регистров со ссыл­ками на ключи, которая соответствует упорядоченности ключей — пря­молинейная реализация.

По значениям ключей вместо массива Индексы строится Вдерево, обеспечивающее хорошую стратегию оперирования.

Значение ключа вершины, к которой ведет левая дуга, всегда боль­ше значения ключа родительской вершины, которое, в свою очередь, больше значения ключа правой вершины. Дерево должно быть сба­лансированным (длины всех путей от корня к листьям различаются не более чем на 1). Только в таком случае достигается эффективность доступа.

3. Используется расстановка (хеширование), суть которой сводится к следующему. Определяется расстановочное поле (хештаблица) — массив фиксированного размера т, который будет заполняться ссылка­ми на группы компонентов исходного разреженного массива (записей нового представления). Эти группы далее называются гроздями. На множестве всех возможных значений ключей определяется функция расстановки (хешфункция) со значениями во множестве номеров гроздей от 0 до т — 1 так, чтобы выполнялись условия перемешива­ния:

для каждого значения ключа существует значение функции рас­становки;

множества всех возможных значений ключей разбивается на клас­сы эквивалентных значений, у которых равны значения функции расстановки, тем самым каждый класс задает свою гроздь;

мощности гроздей должны оказаться примерно одинаковыми для статистически ожидаемого множества возможных значений клю­чей — равномерность расстановки.

Устройство грозди может быть любым (массив, список). Их взаим­ное размещение — также непринципиально (например, можно иметь перемешанные в памяти грозди).

Наряду с Вдеревьями, хеширование сейчас наиболее применимый об­щий метод работы с ключевыми массивами. Поэтому возникают раз­личные варианты и вырожденные случаи расстановки:

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие "Крокодилы"

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама