Ассоциативные списки Поиск данных происходит не по индексу или положению объекта, а по его ассоциативной связи: public interface Map { // Доступ к объектам. - презентация

1 Ассоциативные списки Поиск данных происходит не по индексу или положению объекта, а по его ассоциативной связи: public interface Map { // Доступ к объектам по ключу Object get(Object key); Object put(Object key, Object value); Object remove(Object key); // Размер ассоциативного списка int size(); boolean isEmpty(); // Проверка наличия ключей и значений boolean containsKey(Object key); boolean containsValue(Object value); // Очистка списка void clear(); } Другие классы и интерфейсы: Dictionary, HashMap, Hashtable

2 Способы реализации ассоциативных списков class MapContainer implements Map { // Структура, содержащая ассоциативную связь private static class Pair { Object key, value; Pair(Object key, Object value) { this.key = key; this.value = value; } // Структура для поиска по ключу: // список, упорядоченный массив, дерево,... private SearchStruct container = new SearchStruct(); // Реализация операций: Object get(Object key) { // Поиск по ключу и возврат найденного значения } Object put(Object key, Object value) { Pair newPair = new Pair(key, value); // Вставка нового элемента с заданным ключом }

3 Преимущества и недостатки различных структур данных для реализации ассоциативных списков ПреимуществаНедостатки Упорядоченный массив Логарифмическая скорость поиска Простота слияния Легкость итерации Низкая скорость вставки и удаления элементов Список Удобство вставки и удаления элементов Простота слияния Легкость итерации Низкая скорость поиска Двоичное дерево Логарифмическая скорость поиска Сравнительно быстрая вставка и удаление элементов Сложность итерации Слияние только поэлементное

4 Хеширование Идея: разделить все элементы на легко вычисляемые классы, и для каждого класса хранить свой собственный структурный объект. class MapContainer implements Map { // Параметры хеширования: final private static int HASH_MODULE = 128; private static int hash(Object obj) { return obj.hashCode() % HASH_MODULE; } // Структура, содержащая ассоциативную связь private static class Pair { Object key, value;... } // массив структур: списков, упорядоченных массивов, деревьев,... private SearchStruct containers[] = new SearchStruct[HASH_MODULE]; // Реализация операций: Object get(Object key) { // Поиск по ключу и возврат найденного значения SearchStruct container = containers[hash(key)];... } Object put(Object key, Object value) { Pair newPair = new Pair(key, value); // Вставка нового элемента с заданным ключом в containers[hash(key)] }

5 Преимущества и недостатки хеш-таблиц ПреимуществаНедостатки Возможность использования простых структур хранения Быстрый поиск при величине модуля, сравнимого с общим числом элементов Сравнительно быстрая вставка и удаление элементов Возможность работы с неупорядоченными ключами Итерация не в порядке возрастания ключей Слияние только поэлементное Необходимость «перехеширования» при увеличении числа хранимых объектов java.util.HashMap, java.util.Hashtable – варианты реализации этой идеи.

6 Один из вариантов реализации public class HashDictionary { private int HASH_MODULE = 13; // Начальное значение хеш-модуля // Хеш-функция – скорректированная сумма кодов символов строки private int hash(String key) { int s = 0; for (int i = 0; i < key.length(); i++) { s += key.charAt(i) + i + 1; s %= HASH_MODULE; } return s; } // Узел списка – элемент контейнера private static class ListNode { String key; // ключ поиска Object obj; // ассоциированный объект ListNode next; // указатель на следующий элемент // Два варианта конструктора ListNode(String key, Object obj, ListNode next) { this.key = key; this.obj = obj; this.next = next; } ListNode(String key, Object obj) { this(key, obj, null); } // Счетчик количества элементов private int count = 0; // Массив контейнеров-списков private ListNode[] container = new ListNode[HASH_MODULE];

7 Один из вариантов реализации (продолжение) public Object get(String key) { int hash = hash(key); // значение хеш-функции ListNode current = container[hash]; // для поиска элемента в контейнере for (current != null && !current.key.equals(key); current = current.next) ; return current == null ? null : current.obj; } public Object put(String key, Object value) { if (value == null) throw new NullPointerException("HashDictionary.put"); // value != null int hash = hash(key); // значение хеш-функции ListNode current = container[hash]; // для поиска элемента в контейнере for (current != null && !current.key.equals(key); current = current.next) ; if (current == null) { // ключ не найден – вставляем новый элемент списка container[hash] = new ListNode(key, value, container[hash]); if (++count > 2*HASH_MODULE) rehash(); // перехеширование, если необходимо! return null; } else { // ключ найден – заменяем ассоциированный объект Object tmp = current.obj; current.obj = value; return tmp; } public Object remove(String key) { int hash = hash(key); // значение хеш-функции ListNode current = container[hash]; // для поиска элемента в контейнере ListNode prev = null; // предыдущий элемент списка (если есть) for (current = container[hash]; current != null && !current.key.equals(key); current = current.next) prev = current; if (current == null) { // ключ не найден – удалять нечего return null; } else { // ключ найден – удаляем элемент списка и возвращаем старое значение if (prev == null) container[hash] = current.next; else prev.next = current.next; count--; return current.obj; } 2*HASH_MODULE) rehash(); // перехеширование, если необходимо! return null; } else { // ключ найден – заменяем ассоциированный объект Object tmp = current.obj; current.obj = value; return tmp; } public Object remove(String key) { int hash = hash(key); // значение хеш-функции ListNode current = container[hash]; // для поиска элемента в контейнере ListNode prev = null; // предыдущий элемент списка (если есть) for (current = container[hash]; current != null && !current.key.equals(key); current = current.next) prev = current; if (current == null) { // ключ не найден – удалять нечего return null; } else { // ключ найден – удаляем элемент списка и возвращаем старое значение if (prev == null) container[hash] = current.next; else prev.next = current.next; count--; return current.obj; }">