Главная » Java, Структуры данных и алгоритмы » Словари

0

Знакомую фразу «Иди и посмотри» часто можно услышать в ответ на просьбу ленивого студента подсказать определение какого-либо слова от не менее ленивого преподавателя. Именно эта фраза — принцип построения абстрактного типа данных «словарь», который будет обсуждаться в этой главе.

Судя по названию, первоочередное назначение словаря заключается в хранении элементов таким образом, чтобы их можно было легко и быстро обнаружить с помощью ключей. Мотивом для поиска является еще и то, что обычно каждый элемент в словаре помимо поискового ключа хранит полезную дополнительную информацию, но единственным способом ее достичь является ключ. Например, словарь может хранить банковские счета. Каждый счет является объектом, идентифицируемым номером счета и хранящим множество дополнительных сведений, включающих текущий баланс, имя и адрес владельца, историю вкладов и расходов. Приложение, которое будет работать со счетом, должно предоставлять его номер в качестве поискового ключа для получения объекта, соответствующего счету из словаря.

Другим примером может быть словарь, хранящий некоторое количество открытых в графическом интерфейсе окон. Объекты окон хранятся в словаре в соответствии с указателями (такими как номер процесса ID), определяющими уникальное значение ключа. Но с каждым объектом хранится и дополнительная информация, включающая размеры окна, описания всплывающих меню, шрифты и цвета. Процесс, предполагающий послать сообщение определенному объекту окна, может запросить ссылку на этот объект, за которой он обращается в словарь с помощью ID окна в качестве ключа.

Как и очередь с приоритетами, словарь — это контейнер пар «ключ-элемент». Тем не менее, хотя отношения полной упорядоченности для очереди с приоритетами являются правилом, для словаря это не обязательно. Действительно, простейшая форма словаря предполагает только возможность определять равенство между собой двух ключей. Если же требуются отношения полной упорядоченности, то следует говорить об упорядоченном словаре, и можно вывести дополнительные методы АТД, касающиеся упорядочения ключей в данном конкретном случае.

Компьютерный словарь подобен своему бумажному собрату в том смысле, что оба используются для поиска информации. Хотя сравнение с традиционным словарем не совсем приемлемо, поскольку компьютерный словарь более динамичен, так как поддерживает операции ввода и удаления элементов. Таким образом, абстрактный тип данных «словарь» имеет методы ввода, удаления и поиска элементов по ключам.

В этой главе приводятся несколько различных методик реализации словарей. Покажем, например, как реализовать словарь с помощью неупорядоченной последовательности. Это довольно простая реализация, хотя и не самая лучшая. Поэтому будут представлены хеш-таблицы (hash table) и skip-списки, показывающие применение этих структур для реализации словарей с небольшим временем выполнения запроса и обновления. В заключение главы будет показана возможность использования ло- каторной модели проектирования, описанной в предыдущей главе, для увеличения количества методов, входящих в АТД «словарь». И далее в главе 9 рассмотрим структуры данных для увеличения скорости выполнения операций словаря, воспользовавшись разными видами сбалансированных бинарных деревьев.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии