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

0

Стандартный пакет java.util содержит и интерфейс АТД «словарь», называемый java.util.Map. Кроме того, этот пакет включает абстрактный класс java.util.Dictionary, который тоже соответствует описанному выше АТД «словарь». Но этот абстрактный класс считается устаревшим. И java.util.Map, и java.util.Dictionary сформулированы таким образом, что реализация класса требует уникальности ключей. Так, например, в интерфейсе java.util.Map отсутствует метод, соответствующий методу findAllElements(A;). За исключением требования уникальности ключей, интерфейс java.util.Map почти полностью соответствует вышеописанному АТД «словарь». И все же имеются два почти неуловимых отличия между описанным АТД и интерфейсом java.util.Map, о чем ниже.

Проверка на равенство в java.util.Map

Первое отличие заключается в том, что интерфейс java.util.Map предполагает использование метода equals, поддерживаемого любым Java-объек- том и проверяющего равенство двух ключей. Таким образом, применяя java.util.Map, следует включить метод equals в код ключевого класса. Однако в таком подходе отсутствует гибкость, поскольку существуют приложения, в которых ключи «не знают» о своем равенстве. Например, геометрический алгоритм может рассматривать точки как равные, если они имеют одинаковые координаты х, а другой алгоритм может рассматривать их как равные при одинаковых координатах у (см. п. 7.1.4). Вместо этого предлагается использовать определитель равенства (или компаратор) для проверки равенства двух ключей в словаре. Такой подход обеспечивает универсальный, многократный и легко адаптируемый способ сравнения объектов. Отметим, что определитель равенства всегда может использовать метод equals ключевого класса, если таковое имеет смысл.

Использование null в качестве элемента и сигнального сообщения

Второе отличие java.util.Map от АТД «словарь» заключается в использовании нулевого (null) объекта в качестве специального элемента, возвращаемого в случае отсутствия элемента с заданным для поиска ключом, одновременно позволяя применить null в качестве элемента пары «ключ-элемент», хранимой в словаре. Нулевой объект в качестве элемента может потребоваться, когда необходимо сохранять ключ, не имеющий отношения ни к одному из элементов. К несчастью, вышедший из употребления класс java.util.Dictionary также использует нулевой объект как значение NO_SUCH_KEY. Но при этом нулевой объект не может содержать элементов. Таким образом, с одной стороны, нулевой объект — это обычный элемент, а с другой стороны — специальный элемент сродни объекту NO_SUChLKEY в АТД «словарь». Использование нулевого объекта в качестве значения NO_SUCH_KEY позволяет выполнять простые сравнения, но может привести и к некоторой путанице. В частности, если null является легитимным элементом, то чем же является результат поиска null — значением элемента или признаком отсутствия ключа, невозможно определить. Чтобы избежать подобного, java.util.Map содержит булев метод containsKey(/;), возвращающий true только в случае наличия ключа к в словаре.

Соответствующие методы

Остальные отличительные особенности АТД «словарь» и интерфейса java.util.Map отражены в табл. 8.1.

Таблица 8.1. Соответствие между методами АТД «словарь» и интерфейса java.util.Map, поддерживающего и другие методы

Дав определение абстрактному типу данных «словарь» и его Java-Ba- риантам, обсудим теперь способы реализации этого АТД, рассмотрев как сильные, так и слабые стороны каждого из подходов.

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

По теме:

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