14.1 Введение
Во многих задачах программирования необходимо хранить и манипулировать множествами разнообразных объектов. Одной из важнейших задач является
поиск заданного объекта во множестве. Если не применять никаких специальных
механизмов хранения, то необходим полный перебор всех объектов. Однако если
построить механизм, при котором каждому объекту из множества можно поставить
однозначно некоторое уникальное число, то можно существенно сократить поиск
заданного объекта во множестве. Ассоциативная память это такая
организация хранения объектов, при которой местоположение объекта в памяти можно определить по его некоторым свойствам или атрибутам.
Механизмы организации ассоциативной
памяти различные.
- Можно отметить следующие:
-
Хеш-таблицы
-
Двоичные деревья
-
B-деревья
- Хеш-функции и хеш-таблицы
Рассмотрим основные идеи организации
ассоциативной памяти на примере.
Предположим, нам необходимо хранить некоторую таблицу, в которой хранятся
идентификаторы (правила записи идентификаторов смотри раздел "Трансляторы")
и некоторые их характеристики, такие как тип, начальное значение, адрес распределения и пр.
Описание структуры элемента таблицы.
Элемент содержит некоторый идентификатор name и две целых переменных
type и addr, интерпретация зависит от конкретной реализации.
-
typedef struct TablElem_ {
char
name[20];
int
type;
int
addr;
} TablElem;
Описание таблицы символов содержит
размер таблицы size, счетчик записанных идентификаторов count. Указатель на вектор элементов таблицы.
-
typedef struct HashTabl_ {
int
count;
int
size;
TablElem *elem;
} HashTable;
Функция создания таблицы символов.
Входным параметром является размер создаваемой таблицы. Первоначально распределяется память под структуру
таблицы, затем распределяется память под вектор элементов таблицы, если все
нормально, то обнуляются все элементы таблицы и устанавливаются значения count
и size для таблицы ht. Если в результате таблица создана, то возвращается адрес
таблицы, в противном случае NULL.
-
HashTable *CreateHashTable(int size)
{
HashTable *ht=(HashTable*)malloc(sizeof(HashTable));
if(ht==NULL)
return NULL;
ht->elem=(TablElem*)malloc(sizeof(TablElem)*size);
if(ht->elem==NULL)
{
free(ht); //освобождаем память выделенную под структуру ht
return NULL;
}
ht->count=0;
ht->size=size;
setmem(ht->elem,sizeof(TablElem)*size,0); //обнуляем вектор элементов
return ht;
}
Функция удаления таблицы
void DeleteHashTable(HashTable *tabl)
{
free(tabl->elem);
free(tabl);
}
Функция вычисленияиндекса элемента в
векторе elem таблицы ht. Вычисление производится следующим образом: определяется сумма байт строки name,
затем берется остаток от деления на размер таблицы, это и будет индексом элемента.
-
int HashFunc(HashTable *tabl, char *name)
{
int
sum=0;
while(*name)
sum+=*name++;
return
sum%tabl->size;
}
Обратите внимание функция HashFunc
произвольной строке, записанной в
name, ставит в соответствие номер элемента таблицы. Вот свойство ассоциативности, но атрибуту объекта name определяется его местонахождение в таблице.
Функция, вычисляющая по некоторому атрибуту объекта число, называется хешфункцией (от английского слова hash - мешанина, путаница). Исследования свойств
хеш-функций показывает, что имеется огромное количество разных объектов имеющих одно и тоже значение хеш-функции. Для нашего примера это строки "xyz",
"yxz", "zyx" будут иметь одно и тоже значение. В этом случае говорят о коллизии. Имеется много различных методов разрешения коллизий . Ниже предлагается
описание функции AddHashTable, которая вставляет в таблицу имя name, используя описанную выше хеш-функции HashFunc. На входе этой функции подается
актуальный указатель на структуру таблицы ht и указатель на строку name. Первоначально по строке name вычисляется индекс, используя функцию HashFunc.
Затем проверяется соответствующий элемент таблицы, если он пуст, то имя записывается в этот элемент, функция AddHashTable возвращает индекс элемента
таблицы. Если место уже занято, то проверяется на совпадение строк, если совпало, то такое имя уже записано в таблице и его не нужно записывать, при этом
функция возвращает индекс найденного элемента таблицы. Если имена не совпали,
то наступила коллизия и вызывается функция разрешения коллизий Collision (см.
описание следующей функции).
-
int AddHashTable(HashTable *ht, char *name)
{
int
index=HashFunc(ht,name); //вычислить индекс таблицы
if(ht->elem[index].name[0]==’\0’)
//элемент таблицы не занят
{
strcpy(ht->elem[index].name,name);
//вставить
ht->count++;
//количество элементов в таблице увеличить на 1
return index; //вернуть индекс
}
else
if(strcmp(ht->elem[index].name,name)==0) return index;
else
{
printf("Collise%d\n",ht->count);
// коллизия
srand(index);
return
Collision(ht,name);
}
}
Функция разрешения коллизий
Collision. Эта функция вызывается когда,
в таблице вычисленный элемент уже занят другим именем. Для разрешения коллизии предлагается использовать другую функцию преобразования индекса или
строки name, для перечисления некоторого множества индексов. Функция разрешения коллизий пытается найти другой индекс, чтобы элемент таблицы был не
занят. Ниже используется простой метод разрешения коллизий на основе датчика
случайных чисел (см. раздел Датчик случайных чисел). Перед вызовом функции
Collision устанавливается параметр параметра случайных чисел srand(index),
после
этой установки датчик выдает фиксированную последовательность чисел. Функция работает следующим образом: организуется цикл в зависимости от наполнения и размера таблицы. Вычисляется следующий индекс next_index, если элемент
таблицы не занят, то вставляем и возвращаем индекс, если строки совпали, то
возвращаем найденный индекс, если этот элемент занят другой строкой, то возвращаемся в начало цикла и ищем следующий индекс. Если по завершению цикла не
нашли места для вставки строки, то возвращаем -1, который показывает, что данным методом нельзя вставить эту строку в таблицу. Эта ситуация говорит о том,
что таблица скорее всего полностью заполнена. В таких случаях поступают следующим образом: устанавливают размер таблице большим или выполняют механизм
динамического расширения таблицы.
-
int Collision(HashTable *ht, char *name)
{
int
next_index;
for(int i=0; i<ht->size; i++) //цикл для разрешения коллизий
{
printf("coll
%d\n",i);
next_index=random(ht->size);
//получить следующий индекс
if(ht->elem[next_index].name[0]==’\0’)
//элемент таблицы свободен
{
strcpy(ht->elem[next_index].name,name);
ht->count++;
return
next_index;
}
else
if(strcmp(ht->elem[next_index].name,name)==0) //строка совпала
{
printf("find
%s\n",name);
return
next_index;
}
}
//цикл закончился
return
-1; //не смогли вставить
}
Функция печати таблицы
void PrintHashTable(HashTable *ht)
{
printf("size = %d count =
%d\n",ht->size,ht->count);
for(int i=0; i<ht->size; i++)
if(ht->elem[i].name[0]!=’\0’)
{
printf("%3d %20s\n",i,ht->elem[i].name);
}
}
Функция показывающая работу хеш-таблицы.
void
main()
{
int
j; char name[20];
HashTable *ht;
randomize();
ht=CreateHashTable(100); //создание хеш-таблицы
for(int i=0; i<80;
i++)
{
j=rand();
itoa(j,name,10);
if(AddHashTable(ht,name)==-1)
printf("don’t insert\n");
}
PrintHashTable(ht);
DeleteHashTable(ht);
getch();
}
Задание
- Реализовать функцию поиска в
хеш-таблице. Указание, функцию поиска
можно сделать из функции AddHashTable, убрав код связанный с добавлением
нового имени.
- Реализовать механизм хеш-таблицы
как контейнер.
- Реализовать другую хеш-функцию,
например, находить сумму не байтов,
а 16 битовых слов.
- Реализовать метод разрешения
коллизий на основе использования списков. Т.е. все строки с одним индексом хранятся в одном списке, указатель списка
записывается в элемент таблицы.
|