ТОР 5 статей:
Методические подходы к анализу финансового состояния предприятия
Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века
Характеристика шлифовальных кругов и ее маркировка
Служебные части речи. Предлог. Союз. Частицы
КАТЕГОРИИ:
- Археология
- Архитектура
- Астрономия
- Аудит
- Биология
- Ботаника
- Бухгалтерский учёт
- Войное дело
- Генетика
- География
- Геология
- Дизайн
- Искусство
- История
- Кино
- Кулинария
- Культура
- Литература
- Математика
- Медицина
- Металлургия
- Мифология
- Музыка
- Психология
- Религия
- Спорт
- Строительство
- Техника
- Транспорт
- Туризм
- Усадьба
- Физика
- Фотография
- Химия
- Экология
- Электричество
- Электроника
- Энергетика
Спецификация класса HashTable
Открытая адресация с линейным перебором
Эта методика предполагает, что каждая ячейка таблицы помечена как незанятая. Поэтому при добавлении нового ключа всегда можно определить, занята ли данная ячейка таблицы или нет. Если да, алгоритм осуществляет перебор по кругу, пока не встретится «открытый адрес» (свободное место). Отсюда и название метода. Если размер таблицы велик относительно числа хранимых там ключей, метод работает хорошо, поскольку хеш-функция будет равномерно распределять ключи по всему диапазону и число коллизий будет минимальным. По мере того как коэффициент заполнения таблицы приближается к 1, эффективность процесса заметно падает.
Пример.
Проиллюстрируем линейный перебор на примере семи записей.
Предположим, что данные имеют тип DataRecord и хранятся в 11-элементной таблице.
struct DataRecord
{
int key;
int data;
};
В качестве хеш-функции HF используется остаток от деления на 11, принимающий значения в диапазоне 0-10.
HF(item) = item.key % 11
В таблице хранятся следующие данные. Каждый элемент помечен числом проб, необходимых для его размещения в таблице.
Список: {54,1}, {77,3}, {94,5}, {89,7}, {14,8}, {45,2}, {76,9}
Хеширование первых пяти ключей дает пять различных индексов, по которым эти ключи запоминаются в таблице. Например, HF({54,1}) = 10, и этот элемент попадает в Table[10]. Первая коллизия возникает между ключами 89 и 45, так как оба они отображаются в индекс 1.
Элемент данных {89,7} идет первым в списке и занимает позицию Table[1]. При попытке записать {45,2} оказывается, что место Table[1] уже занято. Тогда начинается последовательный перебор ячеек таблицы с целью нахождения свободного места. В данном случае это Table[2]. На ключе 76 эффективность алгоритма сильно падает. Этот ключ хешируется в индекс 10 – место, уже занятое. В процессе перебора осуществляется просмотр еще пяти ячеек, прежде чем будет найдено свободное место в Table[4]. Общее число проб для размещения в таблице всех элементов списка равно 13, т.е. в среднем 1,9 проб на элемент.
Метод цепочек
При другом подходе к хешированию таблица рассматривается как массив связанных списков или деревьев. Каждый такой список называется блоком (bucket) и содержит записи, отображаемые хеш-функцией в один и тот же табличный адрес. Эта стратегия разрешения коллизий называется методом цепочек (chaining with separate lists).
Если таблица является массивом связанных списков, то элемент данных просто вставляется в соответствующий список в качестве нового узла. Чтобы обнаружить элемент данных, нужно применить хеш-функцию для определения нужного связанного списка и выполнить там последовательный поиск.
Рис.5
Пример.
Проиллюстрируем метод цепочек на семи записях типа DataRecord и хеш-функции HF.
Список: {54,1}, {77,3}, {94,5}, {89,7}, {14,8}, {45,2}, {76,9}
HF(item) = item.key % 11
Каждый новый элемент данных вставляется в хвост соответствующего связанного списка. На рисунке 30 каждое значение данных сопровождается (в скобках) числом проб, требуемых для запоминания этого значения в таблице.
Рис.6
Заметьте, что если считать пробой вставку нового узла, то их общее число при вставке семи элементов равно 9, т.е. в среднем 1,3 пробы на элемент данных.
Преимущества метода цепочек перед открытой адресацией:
- в общем случае метод цепочек быстрее открытой адресации, так как просматривает только те ключи, которые попадают в один и тот же табличный адрес;
- открытая адресация предполагает наличие таблицы фиксированного размера, в то время как в методе цепочек элементы таблицы создаются динамически, а длина списка ограничена лишь количеством памяти.
Основной недостаток метода цепочек: являются дополнительные затраты памяти на поля указателей.
В общем случае динамическая структура метода цепочек более предпочтительна для хеширования, чем открытая адресация.
Класс HashTable
В этом разделе определяется общий класс HashTable, осуществляющий хеширование методом цепочек. Этот класс образуется от базового абстрактного класса List и обеспечивает механизм хранения с очень эффективными методами доступа. Допускаются данные любого типа с тем лишь ограничением, что для этого типа данных должен быть определен оператор «= =». Чтобы сравнить ключевые поля двух элементов данных, прикладная программа должна перегрузить оператор «= =».
Мы также рассмотрим класс HashTableIterator, облегчающий обработку данных в хеш-таблице. Объект типа HashTableIterator находит важное применение при сортировке и доступе к данным.
Но сначала приведем листинги классов Array и LinkedList, используемых в классе HashTable. Особо пояснять мы их не будем, поскольку их обсуждение не входит в задачи этой статьи.
Класс Array
Объявление
enum ErrorType {invalidArraySize, memoryAllocationError, indexOutOfRange}; char *errorMsg[] ={ "Неверный размер массива", "Ошибка при выделении памяти", "Неверный индекс: "}; template <class T> class Array{ private: // Динамически занимаемый массив. T* alist; // Размер массива. int size; // Обработчик ошибок. void Error(ErrorType error,int badIndex=0) const; public: // Конструкторы и деструктор. Array(int sz = 50); Array(const Array<T>& A); ~Array(void); // Оператор присвоения Array<T>& operator= (const Array<T>& rhs); // Оператор индексации T& operator[](int i); // Оператор приведения к void operator T* (void) const; int ListSize(void) const; // считать размер void Resize(int sz); // изменить размер};
Реализация
// печатает сообщение, соответствующее ошибкеtemplate <class T>void Array<T>::Error(ErrorType error, int badIndex) const{ cerr << errorMsg[error]; if (error == indexOutOfRange) cerr << badIndex; cerr << endl; exit(1);} // конструкторtemplate <class T>Array<T>::Array(int sz){ // проверка правильности заданного размера if (sz <= 0) Error(invalidArraySize); // запоминаем размер и выделяем память под массив size = sz; alist = new T[size]; // проверяем, что система выделила запрошенную память if (alist == NULL) Error(memoryAllocationError);} // деструкторtemplate <class T>Array<T>::~Array(void){ delete [] alist;} // конструктор копированияtemplate <class T>Array<T>::Array(const Array<T>& X){ // присвоить размер объекта X текущему объекту int n = X.size; size = n; // выделить память под массив и проверить, что она выделена alist = new T[n]; // allocate dynamic array if (alist == NULL) Error(memoryAllocationError); // скопировать элементы массива из Х T* srcptr = X.alist; // начальный адрес X.alist T* destptr = alist; // начальный адрес alist // копируем элементы массива while (n--) *destptr++ = *srcptr++;} // оператор присвоения. Присвоить rhs текущему объектуtemplate <class T>Array<T>& Array<T>::operator= (const Array<T>& rhs){ // запоминаем размер rhs int n = rhs.size; // если размеры не совпадают, перезанимаем память if (size!= n) { delete [] alist; // освобождаем ранее занятую память alist = new T[n]; // занимаем память под новый массив if (alist == NULL) Error(memoryAllocationError); size = n; } // Копируем элементы массива из rhs в текущий объект T* destptr = alist; T* srcptr = rhs.alist; while (n--) *destptr++ = *srcptr++; // возвращаем ссылку на текущий объект return *this;} // оператор индексированияtemplate <class T>T& Array<T>::operator[] (int n){ // проверяем границы массива if (n < 0 || n > size-1) Error(indexOutOfRange,n); // возвращаем ссылку на запрошенный элемент массива return alist[n];} // оператор приведения указателяtemplate <class T>Array<T>::operator T* (void) const{ // возвращаем значение скрытого поля alist return alist;} template <class T>int Array<T>::ListSize(void) const{ return size;} // оператор изменения размеров массиваtemplate <class T>void Array<T>::Resize(int sz){ // Проверяем заданный размер if (sz <= 0) Error(invalidArraySize); // ничего не делать, если размер не изменился if (sz == size) return; // занимаем память T* newlist = new T[sz]; if (newlist == NULL) Error(memoryAllocationError); // Рассчитываем количество элементов, // копируемых из старого массива в новый. // Запоминаем в n значение sz (обрезаем массив), если sz <= size // иначе запоминаем size int n = (sz <= size)? sz: size; // копируем n элементов из старого массива в новый T* srcptr = alist; // начальный адрес старого массива T* destptr = newlist; // начальный адрес нового массива // Копируем элементы массива. while (n--) *destptr++ = *srcptr++; // Уничтожаем старый массив. delete[] alist; // Изменяем значение alist так, чтобы оно указывало на новый массив alist = newlist; // Запоминаем новый размер массива. size = sz;}
Класс LinkedList
Класс LinkedList использует класс Node для хранения элементов списка.
template <class T>class Node{private: Node<T> *next; // указатель на следующий элемент public: T data; // конструктор Node (const T& item, Node<T>* ptrnext = NULL); // Методы модификации списка void InsertAfter(Node<T> *p); Node<T> *DeleteAfter(void); // возвращает адрес следующего элемента Node<T> *NextNode(void) const;}; // Конструктор. Инициализирует data и next.template <class T>Node<T>::Node(const T& item, Node<T>* ptrnext): data(item), next(ptrnext) {} // Возвращает значение nexttemplate <class T>Node<T> *Node<T>::NextNode(void) const{ return next;} // Вставит ветку после текущей// p – элемент, подключаемый к текущему элементуtemplate <class T>void Node<T>::InsertAfter(Node<T> *p){ p->next = next; next = p;} // Отсоединяет элемент, подключенный к текущему, и возвращает // адрес отключенного элемента.template <class T>Node<T> *Node<T>::DeleteAfter(void){ Node<T> *tempPtr = next; // запоминаем отключаемый элемент // Если подключенного элемента нет, возвращаем NULL. if (next == NULL) return NULL; // Восстанавливает целостность цепочки. next = tempPtr->next; // возвращаем указатель на отключенный элемент. return tempPtr;}
Объявление
// Предобъявление класса SeqListIteratortemplate <class T>class SeqListIterator; template <class T>class LinkedList{ private: // указатели для доступа к началу и концу списка Node<T> *front, *rear; // используются для получения, вставки и удаления данных Node<T> *prevPtr, *currPtr; // число элементов списка int size; // позиция в списке. Используется методом Reset int position; // скрытые методы создания и уничтожения элементов Node<T> *GetNode(const T& item,Node<T> *ptrNext=NULL); void FreeNode(Node<T> *p); // копирует список L в текущий список void CopyList(const LinkedList<T>& L); public: // конструкторы LinkedList(void); LinkedList(const LinkedList<T>& L); // деструктор ~LinkedList(void); // оператор присвоения LinkedList<T>& operator= (const LinkedList<T>& L); // методы проверки состояния списка int ListSize(void) const; int ListEmpty(void) const; // Методы прохождения void Reset(int pos = 0); void Next(void); int EndOfList(void) const; int CurrentPosition(void) const; // Методы вставки void InsertFront(const T& item); void InsertRear(const T& item); void InsertAt(const T& item); void InsertAfter(const T& item); // Методы удаления T DeleteFront(void); void DeleteAt(void); // Получение/изменение данных T& Data(void); // Метод очистки списка void ClearList(void); // Класс SeqListIterator нуждается в доступе к этому классу friend class SeqListIterator<T>;};
Реализация
template <class T>Node<T> *LinkedList<T>::GetNode(const T& item, Node<T>* ptrNext){ Node<T> *p; p = new Node<T>(item,ptrNext); if (p == NULL) { cout << "Ошибка при выделении памяти!\n"; exit(1); } return p;} template <class T>void LinkedList<T>::FreeNode(Node<T> *p){ delete p;} // копируем L в текущий список, который считаем пустымtemplate <class T>void LinkedList<T>::CopyList(const LinkedList<T>& L){ // Используем p для пробегания по списку L Node<T> *p = L.front; int pos; // Перебираем элементы в списке L и вставляем каждый элемент // в конец текущего списка. while (p!= NULL) { InsertRear(p->data); p = p->NextNode(); } // Если список пуст, заканчиваем работу. if (position == -1) return; // Перезагрузка prevPtr и currPtr в новом списке prevPtr = NULL; currPtr = front; for (pos = 0; pos!= position; pos++) { prevPtr = currPtr; currPtr = currPtr->NextNode(); }} // Создает новый список. Устанавливает указатели в NULL, размер в 0,// и позицию в списке -1template <class T>LinkedList<T>::LinkedList(void): front(NULL), rear(NULL), prevPtr(NULL),currPtr(NULL), size(0), position(-1){} template <class T>LinkedList<T>::LinkedList(const LinkedList<T>& L){ front = rear = NULL; prevPtr = currPtr = NULL; size = 0; position = -1; CopyList(L);} template <class T>void LinkedList<T>::ClearList(void){ Node<T> *currPosition, *nextPosition; currPosition = front; while(currPosition!= NULL) { // Получаем адрес следующего элемента и удаляем текущий. nextPosition = currPosition->NextNode(); FreeNode(currPosition); currPosition = nextPosition; // Переходим к следующему элементу. } front = rear = NULL; prevPtr = currPtr = NULL; size = 0; position = -1;} template <class T>LinkedList<T>::~LinkedList(void){ ClearList();} template <class T>LinkedList<T>& LinkedList<T>::operator= (const LinkedList<T>& L){ if (this == &L) // Нельзя копировать себя в себя же. return *this; ClearList(); CopyList(L); return *this;} template <class T>int LinkedList<T>::ListSize(void) const{ return size;} template <class T>int LinkedList<T>::ListEmpty(void) const{ return size == 0;} // Передвигает prevPtr и currPtr вперед на одну позициюtemplate <class T>void LinkedList<T>::Next(void){ // если перебирать нечего, заканчиваем if (currPtr!= NULL) { // Передвигаем указатели вперед на одну позицию. prevPtr = currPtr; currPtr = currPtr->NextNode(); position++; }} // Возвращает TRUE если достигнут конец списка.template <class T>int LinkedList<T>::EndOfList(void) const{ return currPtr == NULL;} // Возвращает позицию текущего элементаtemplate <class T>int LinkedList<T>::CurrentPosition(void) const{ return position;} // Сбросить текущую позицию в postemplate <class T>void LinkedList<T>::Reset(int pos){ int startPos; // Если список пуст, заканчиваем if (front == NULL) return; // В случае неверной позиции завершаем выполнение. if (pos < 0 || pos > size-1) { cerr << "Reset: Неверная позиция: " << pos << endl; return; } if(pos == 0) { // Сбрасываем механизм прохождения в начальное положение prevPtr = NULL; currPtr = front; position = 0; } else { // Устанавливаем механизм прохождения в pos. currPtr = front->NextNode(); prevPtr = front; startPos = 1; // Пробегаем по списку до достижения pos for(position=startPos; position!= pos; position++) { prevPtr = currPtr; currPtr = currPtr->NextNode(); } }} // Возвращаем ссылку на элемент данных.template <class T>T& LinkedList<T>::Data(void){ // Ошибка если список пуст или прохождение завершено. if (size == 0 || currPtr == NULL) { cerr << "Data: неверная ссылка!" << endl; exit(1); } return currPtr->data;} // Вставить элемент в начало списка.template <class T>void LinkedList<T>::InsertFront(const T& item){ // Вызвать Reset если список не пуст. if (front!= NULL) Reset(); InsertAt(item);} // Вставить элемент в конец списка.template <class T>void LinkedList<T>::InsertRear(const T& item){ Node<T> *newNode; prevPtr = rear; newNode = GetNode(item); // создать новый элемент if (rear == NULL) // Если список пуст, вставить в начало front = rear = newNode; else { rear->InsertAfter(newNode); rear = newNode; } currPtr = rear; position = size; size++;} // Вставить элемент в текущую позицию в списке.template <class T>void LinkedList<T>::InsertAt(const T& item){ Node<T> *newNode; // Два случая: вставка в начало или в середину списка. if (prevPtr == NULL) { // Вставка элемента в начало списка. Также позволяет // поместить элемент в пустой список. newNode = GetNode(item,front); front = newNode; } else { // Вставка элемента внутрь списка. Помещает элемент после prevPtr newNode = GetNode(item); prevPtr->InsertAfter(newNode); } // Если prevPtr == rear, мы вставляем в пустой список // или в конец непустого списка; обновить rear и position if (prevPtr == rear) { rear = newNode; position = size; } // Обновить currPtr currPtr = newNode; size++; // увеличиваем размер списка} // Вставляет элемент за текущей позицией.template <class T>void LinkedList<T>::InsertAfter(const T& item){ Node<T> *p; p = GetNode(item); if (front == NULL) // вставляем в пустой список { front = currPtr = rear = p; position = 0; } else { // Вставляем в конец списка. if (currPtr == NULL) currPtr = prevPtr; currPtr->InsertAfter(p); if (currPtr == rear) { rear = p; position = size; } else position++; prevPtr = currPtr; currPtr = p; } size++; // увеличиваем размер списка} // Удаляет первый элемент списка.template <class T>T LinkedList<T>::DeleteFront(void){ T item; Reset(); if (front == NULL) { cerr << "Ошибка – удаление в пустом списке!" << endl; exit(1); } item = currPtr->data; DeleteAt(); return item;} // Удаляет текущий элементtemplate <class T>void LinkedList<T>::DeleteAt(void){ Node<T> *p; // Ошибка если список пуст или прохождение завершено. if (currPtr == NULL) { cerr << "Ошибка удаления – отсутствует текущий элемент!" << endl; exit(1); } // Если удаление производится в начале или внутри списка if (prevPtr == NULL) { // Сохраняем указатель на первый элемент и отключаем его. Если это // последний элемент, front становится равным NULL p = front; front = front->NextNode(); } else p = prevPtr->DeleteAfter(); // если удален последний элемент, новым последним элементом становится // prevPtr и позиция уменьшается на 1; иначе, позиция остается той же. // Если p – последний элемент, rear = NULL и position = -1 if (p == rear) { rear = prevPtr; position--; } // Переключить currPtr на следующий за удаляемым элемент. Если p – последний // элемент в списке, currPtr принимает значение NULL. currPtr = p->NextNode(); // Освободить память, занимаемую элементом, и уменьшить размер списка. FreeNode(p); size--;}
Класс List
Объявление
template <class T>class List{ protected: // Число элементов списка. Изменяется производными классами. int size; public: // Конструктор List(void); // Делаем деструктор виртуальным, чтобы производные классы // могли использовать динамически занимаемую память. virtual ~List(void); // Методы доступа к списку virtual int ListSize(void) const; virtual int ListEmpty(void) const; virtual int Find (T& item) = 0; // Методы изменения списка virtual void Insert(const T& item) = 0; virtual void Delete(const T& item) = 0; virtual void ClearList(void) = 0; }; // Конструктор устанавливает размер в 0template <class T>List<T>::List(void): size(0){} // Виртуальный деструктор ничего не делаетtemplate <class T>List<T>::~List(void){} // Возвращает размер спискаtemplate <class T>int List<T>::ListSize(void) const{ return size;} // Проверка на отсутствие элементовtemplate <class T>int List<T>::ListEmpty(void) const{ return size == 0;}Спецификация класса HashTable
Объявление
#include "array.h"#include "list.h"#include "link.h"#include "iterator.h" template <class T>class HashTableIterator; template <class T>class HashTable: public List<T>{ protected: // число блоков; представляет размер таблицы int numBuckets; // хеш-таблица есть массив связанных списков Array< LinkedList<T> > buckets; // хеш-функция unsigned long (*hf)(T key); // адрес элемента данных, к которому обращались последний раз T *current; public: // конструктор с параметрами, включающими // размер таблицы и хеш-функцию HashTable(int nbuckets, unsigned long hashf(T key)); // методы обработки списков virtual void Insert(const T& key); virtual int Find(T& key); virtual void Delete(const T& key); virtual void ClearList(void); void Update(const T& key); // дружественный итератор, имеющий доступ к // данным-членам friend class HashTableIterator<T>}
Описание
Объект типа HashTable есть список элементов типа T. В нем реализованы все методы, которые требует абстрактный базовый класс List. Прикладная программа должна задать размер таблицы и хеш-функцию, преобразующую элемент типа T в длинное целое без знака. Описание параметра функции с помощью типа, заданного в шаблоне, позволяет использовать данный класс для хеширования данных любого типа.
Методы Insert, Find, Delete и ClearList являются базовыми методами обработки списков. Отдельный метод Update служит для обновления элемента, уже имеющегося в таблице.
Методы ListSize и ListEmpty реализованы в базовом классе. Элемент данных current всегда указывает на последнее доступное значение данных. Он используется методом Update и производными классами, которые должны возвращать ссылки.
Пример.
Предположим, что NameRecord есть запись, содержащая поле наименования и поле счетчика.
struct NameRecord{ String name; int count;}; // 101-элементная таблица, содержащая данные типа NameRecord// и имеющая хеш-функцию hashHashTable<NameRecord> HF(101,hash);// вставить запись {"Betsy",1} в таблицуNameRecord rec;rec.name = "Betsy";rec.count = 1;HF.Insert(rec);cout << HF.ListSize(); // распечатать размер таблицы // Найти значение данных, соответствующее ключу "Betsy",// увеличить поле счетчика на 1 и обновить запись.rec.name = "Betsy";if (HF.Find(rec) // найти "Betsy"{ rec.cout += 1; // обновить поле данных HF.Update(rec); // обновить запись в таблице}else cerr << "Ошибка: \"Ключ Betsy должен быть в таблице.\"\n;
Класс HashTableIterator образован из абстрактного класса Iterator и содержит методы для просмотра данных в таблице.
Не нашли, что искали? Воспользуйтесь поиском: