// Класс, представляющий хеш-таблицу пар (ключ, значение), причем
// ключом является строка, а значением может быть произвольный объект.
//В таблице хранятся не сами эти объекты, а ссылки на них.
template <classObject>
classHashTable {
private :
static const int P= 557;
static const int Q= 811;
static const int LENGTH = 1000;
// Элемент списка, содержащий ключ и связанный с ним объект
structListElem {
string key; // ключ
Object *obj; // связанный объект
ListElem *next; // ссылка на следующий элемент
// Простой конструктор для создания элементов списка
ListElem(conststring & k, Object *o, ListElem *n) {
key = k; obj = o; next =n; }
};
// Массив списков, содержащих слова словаря
ListElem * diсt[LENGTH];
public :
// Конструктор
HashTable() { memset (dict, 0, sizeof (dict)); }
// Функция расстановки, основанная на сложении кодов символов
static inthash{const char* str);
// Функция добавления нового объекта по ключу. Если объект,
// связанный с этим ключом, уже содержится в словаре,
//то новый объект замещает собою старый, а старое значение
// возвращается в качестве результата работы функции.
Object * add(const char* key, Object * obj);
// Функция поиска объекта по ключу. Если ключ не найден,
//то функция возвращает пустую ссылку
Object * find(const char * key) const;
// Функция удаления объекта по заданному ключу.
// Результат функции - указатель на удаляемый объект.
// Если ключ не найден, то функция возвращает пустую ссылку
Object * remove(const char * key) ;
};
template <class Object>
int HashTable<Object>::hash(const char * str) {
int sum = 0;
for (int i = 0; str[i]; i++) {
sum += str[i] + i;
}
return ((P * sum + Q) & 0x7FFF) % LENGTH;
}
template <class Object>
Object * HashTable<Object>::add(const char * key, Object * obj) {
if (key == NULL || key[0] == 0 || obj == NULL) {
throw NullValueException();
}
int index - hash(key); // Значение hash-функции
ListElem *current =dict[index]; // Текущий элемент списка
// Поиск ключа в словаре:
while (current && key != current->key) {
current = current->next; }
Object * result = NULL;
if (current) { // Ключ уже есть в словаре
result = current->obj;
current->obj = obj;
} else {
// Создаем новый элемент списка и добавляем в начало списка
ListElem * newElem = newListElem(key, obj, dict[index]);
dict[index] = newElem;
}returnresult;}
template <classObject>
Object * HashTable<Object>::find(const char *key) const{
if{key == NULL || key[0] == 0) {
throwNullValueException();
}
intindex = hash(key); // Значение hash-функции
ListElem *current * dict[index]; // Текущий элемент списка
// Поиск ключа в словаре:
while(current && key !- current->key) {
current = current->next;
}
if (current == NULL) returnNULL; // Ключ не найден
returncurrent->obj;
}
template <classObject>
Object * HashTable<Object>::remove(const char* key) {
if (key == NULL || key[0] == 0) {
throwNullValueException();
}
intindex = hash(key); // Значение hash-функции
ListElem *current = diсt[index]; // Текущий элемент списка
ListElem *pred = NULL; // Предыдущий элемент списка
// Поиск ключа в словаре:
while(current && key != current->key) {
pred = current;
current = current->next;
}
if (current = NULL) returnNULL; // Ключ не найден
// Исключение элемента из списка:
if (pred == NULL) {
diсt[index] = current->next;
} else{
pred->next = current->next;
}
// Возврат результата:
Object * result = current->obj;
deletecurrent;
returnresult;
}
С помощью такого определения словаря можно решать самые разнообразные задачи по обработке текстов. Для большинства задач необходимо, по крайней мере, еще несколько функций, которые выдавали бы информацию обо всем словаре в целом. Можно определить следующие функции:
intsize(); // Количество слов в словаре
Iterator<string> keys (); // Итератор всех ключей словаря
Iterator<Object> objects (); // Итератор всех связанных объектов
Тем не менее у приведенной реализации имеется ряд недостатков. Наиболее серьезный из них — то, что размер таблицы выбран произвольно, и он никак не зависит от количества хранящихся в таблице объектов. При небольшом количестве объектов это приводит к напрасному расходу памяти. Наоборот, если количество хранимых объектов велико, то списки элементов с одним и тем же значением функции расстановки для ключей становятся длинными, а это приводит к сильному замедлению всех основных операций с таблицей.
Лучше всего в таких случаях связывать алгоритм работы функции расстановки и общую организацию таблицы с количеством объектов, хранящихся в ней. Например, если общее количество объектов более, чем в два раза превышает размер массива списков объектов diet, то можно провести так называемое перехеширование. При этом массив расширяется (например, в два раза), функция расстановки изменяется в соответствии с новым размером таблицы, а все слова вместе со связанными с ними объектами перемещаются в новые списки в соответствии с новыми значениями функции расстановки. Конечно, перехеширование— это серьезная и длительная операция, но зато после ее выполнения все операции со словарем начинают работать быстрее.
На самом деле совершенно неважно, являются ли ключами для поиска в хеш-таблице именно слова. Фактически ключами могут служить любые объекты, лишь бы для них можно было определить подходящую функцию расстановки.