Хэш-карта с закрытой адресацией
Ассоциативный массив. Введение
Для начала рассмотрим несколько задач, которые часто встречаются в программировании, затем попытаемся найти в них общие черты, а потом предложим общее решение.
1. Пусть нам необходим массив, который состоит из большого числа элементов. Массив имеет размер порядка 2128 элементов, но хранятся в нём всего около 210 – 220 штук. Проблема в том, что нужные элементы в массиве располагаются не обособленно, а размазаны по всему массиву, так что выделить подмассив достаточно малого размера и работать с ним не получится. Создать массив размера 2128 мы тоже не можем.
Самое простое решение – использовать список. Но у списков скорость поиска, вставки нового элемента и удаления элемента имеют сложность порядка n, а у массива это константа. Иными словами, нам бы хотелось такую структуру данных, в которой бы поиск, вставка и удаление были как и у массива, но при этом не было необходимости держать незанятыми много элементов.
Решение задачи
Пусть нужно хранить 3 значения, с индексами 1001883726, 4524352321524 и 77656433109. Для этого создадим массив A размером в N раз больше, чем элементов. Как находить это число N не известно пока. Возьмём массив размером 10 элементов.
После этого, вместо индекса будем брать остаток от деления на размер массива (в нашем случае 10). Тогда, первый элемент будет иметь индекс 6, и мы поместим его в массив A[6]. Второй элемент в массив под номером 4, третий под номером 9.
Очевидно, что могут появиться элементы с одинаковым индексом. Пусть теперь мы добавляем элемент с индексом 3776. Элемент A[6] же занят, поэтому мы создаём на месте элемента 6 односвязный список и привязываем новое значение к старому.
Когда элементов станет очень много, мы получим маленький массив длинных односвязных списков. Время доступа снизится до O(n). Чтобы этого избежать, когда массив будет заполнен на X процентов, нужно будет пересобрать массив, увеличив его размер в M раз. Тогда, при хорошем распределении, среднее время доступа будет порядка 1, а длинна каждого односвязного списка будет примерно единицей.
Вы успели заметить, что в таком описании очень много условностей. Начнём разбираться с неизвестными X, M и N.
Начальный размер массива, в принципе, может быть любым, хоть единицей. Нам больше важен коэффициент заполнения X, при котором будет происходить пересборка. Это значение называют load factor. В языке C# это значение равно 0.72, а в Java 0.75. Эти значения получены после анализ большого количества кода и считаются для данных языков оптимальными. Анализ мы проводить не будем, а просто возьмём на веру значение 0.72.
Значение 0.72 значит, что после заполнения исходного массива более чем на 72 процента его нужно будет увеличить в M раз. M обычно берут равным 2. То есть, если в нашем массиве изначально 100 элементов , то после добавления 72 пар <индекс, значение>, массив будет увеличен в 2 раза, то есть, станет равным 200.
Пересборку будем осуществлять следующим образом: создадим новую карту нового размера, поместим в неё элементы из старого массива, удалим старую карту.
Поиск элемента осуществляется подобно вставке. Сначала находим его индекс I в массиве. Если в массиве по номеру I нет элемента, то смотрим, есть ли хвост за I-м элементом. Если есть, то проходим по всему списку и ищем в нём нужный нам элемент. При удалении элемента находим его позицию, удаляем пару, удаляем узел списка.
Мы надеемся, что при хорошем распределении, когда элементы размазаны по всему массиву, каждый элемент массива хранит не более одной пары <индекс, значение>. Это оптимистичное предположение. В плохом случае мы получим мало длинных односвязных списков. Тогда сложность всех операция опустится до O(n).
В качестве структуры для хранения элементов (её ещё называют корзиной) может быть использован не только односвязный список, но, например, красно-чёрное дерево, или список с пропусками. Тогда в плохом случае сложность опустится всего до log(n).
Описанная нами структура называется ассоциативным массивом с закрытой адресацией. Также существует ассоциативный массив с открытой адресацией. В нём вместо создания односвязного списка, по определённому алгоритму мы ищем пустую ячейку в текущем массиве. Рассмотрим его позднее.
Вторая задача
Мы хотим реализовать структуру, подобную массиву, но в качестве индекса хотим использовать строку. То есть, обращаться к массиву как a[“Pupkin”], а не a[1772634]. Очевидно, что если бы мы могли каждой строке поставить в соответствие число, то тогда можно было бы свести вторую задачу к первой.
Третья задача
Мы хотим хранить пары <ключ, значение>, где в качестве ключа выступает не только число или строка, но в принципе любой объект, например, структура или кусок бинарного файла. Соответственно, если мы сможем поставить этому объекту в соответствие уникальный идентификатор, то задача сведётся ко второй.
Для решения второй и третьей задачи воспользуемся хэшированием.
Как говорит Википедия, Хеширование (иногда "хэшировани", англ. hashing) — преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или сводкой сообщения (англ. message digest).
Хэш-функции используются для решения многих задач. В нашем случае они помогут нам тем, что каждой строке или объекту поставят в соответствие число.
Вообще, нахождение и анализ хэш-функций – очень сложная и объёмная задача. Мы не будем о ней говорить, просто возьмём готовые решения. В качестве хранимых объектов в нашем примере будем использовать строки. Хэш-функция для строк выглядит в нашем случае, следующим образом.
//Нахождение хэш-кода строки
__inline unsigned long long hashcode(unsigned char *str) {
unsigned long long hash = 5381;
int c;
while (c = *str++) {
hash = ((hash << 5) + hash) ^ c;
}
return hash;
}
Фактически мы производим отображение из почти бесконечного пространства строк (оно ограничено размерами оперативной памяти) в пространство длинных чисел (оно обычно ограничено 64 или 128 битами). Так как мощность множества строк гораздо больше, то отображение будет суръективное, то есть для многих строк хэш-код будет один и тот же. Эта ситуация называется коллизией. Именно поэтому в карте мы будем хранить не хэш-код, а всё значение ключа.
Из этого следует, что ключ должен поддерживать операцию равенства. К счастью, почти все объекты поддерживают эту операцию (исключение, например, это значение NaN, для которого не поддерживается свойство рефлексии a == a).
Хэш-карта. Реализация.
Хэш-карты (хэш-таблицы, хэшмапы, хэштейблы, hashmap, hashtables) одни из самых востребованных структур данных. Они присутствуют практически во всех библиотеках (по иронии, исключение составляет STL, где map - это красно-чёрное дерево). Во многих языках это один их базовых типов данных. В некоторых языках программирования вообще вместо массивов использутся хэш-карты. Поэтому важно знать как они примерно устроены, их слабые и сильные стороны.
Хэш-карта - это реализация интерфейса ассоциативного массива. Ассоциативный массив должен поддерживать операции
- PUT(ключ, значение) для вставки новой пары
- GET(ключ) для получения значения по ключу
- REMOVE(ключ) для удаления пары по ключу
Объявим набор констант. Это значения по умолчанию для нашей хэш-карты.
static const float LOAD_FACTOR = 0.72f; static const size_t INITIAL_SIZE = 100; static const float MULTIPLIER = 2.0f;
Структура Entry – пара <ключ, значение>
//Тип для ключа и для значения
typedef char* K;
typedef char* V;
//Пара <ключ, значение>
typedef struct Entry {
K key;
V value;
} Entry;
Далее, структура для реализации односвязного списка
typedef struct Node {
Entry *value;
struct Node *next;
} Node;
Нужно также ввести функцию освобождения памяти из-под пары. В принципе, можно было бы оставить освобождение на совести пользователя, но это не этично.
__inline void freeEntry(Entry **e) {
free((*e)->key);
free((*e)->value);
free(*e);
//*e = NULL;
}
//Сравнение ключей
#define CMP_EQ(a, b) (strcmp((a), (b)) == 0)
//Нахождение хэшкода
#define HASHCODE(a) (hashcode(a))
//Удаление пары
#define FREE_ENTRY(a) (freeEntry(a))
Теперь, собственно, сама структура "хэш-карта".
typedef struct Hashmap {
Node **data; //массив корзин
size_t size; //количество элементов в карте
size_t arr_size; //размер массива корзин
size_t limit; //целочисленное значение количества элементов карты
//при превышении которого происходит пересборка
float loadFactor; //процентное заполнение карты, при котором
//происходит пересборка карты
float multiplier; //во столько раз увеличится размер карты при пересборке
} Hashmap;
Для упрощение работы введено ещё одно значение limit. Это целочисленное значение количества элементов, при превышении которого произойдёт пересборка.
Функция создания карты
Hashmap* createHashmap(size_t limit, float loadFactor, float multiplier) {
Hashmap *tmp = (Hashmap*)malloc(sizeof(Hashmap));
tmp->arr_size = (limit >= INITIAL_SIZE) ? limit : INITIAL_SIZE;
tmp->loadFactor = (loadFactor >= LOAD_FACTOR &&
loadFactor <= 1.0f) ? loadFactor : LOAD_FACTOR;
tmp->limit = (int)(tmp->loadFactor * tmp->arr_size);
tmp->size = 0;
tmp->multiplier = (multiplier >= MULTIPLIER) ? multiplier : MULTIPLIER;
tmp->data = (Node**) calloc(tmp->arr_size, sizeof(Node*));
return tmp;
}
Здесь мы защищаем пользователя от ввода "плохих" по нашему мнению значений. То есть, минимальное значение элементов массива не может быть меньше INITIAL_SIZE и т.д.
Вставка нового элемента. Вставляем пару <ключ, значение>. Эту функцию будем использовать при пересборке, чтобы не создавать и не уничтожать новые пары.
void raw_put(Hashmap **_map_, Entry *e) {
//Вспомогательный указатель, чтобы не писать *
Hashmap *map = *_map_;
unsigned long long hash = HASHCODE(e->key);
size_t index = (hash % map->arr_size);
//Проверяем загруженность карты.
//Если место есть, то вставляем новую пару
if (map->size < map->limit) {
//Если элемент масива не занят, то
//вставляем глвый узел и новую пару в него
if (map->data[index] == NULL) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->next = NULL;
newNode->value = e;
map->data[index] = newNode;
}
//Если элемент массива занят, то выстраиваем список.
else {
Node *anchor = map->data[index];
Node *newNode = NULL;
while (anchor->next) {
//Если элемент списка хранит тот же ключ, то выбрасываем ошибку
//В принципе, можно просто подменить значение, зависит от реализации
if (CMP_EQ(anchor->value->key, e->key)) {
exit(-5);
}
anchor = anchor->next;
}
newNode = (Node*)malloc(sizeof(Node));
newNode->next = NULL;
newNode->value = e;
anchor->next = newNode;
}
}
else {
//Если места не хватает, то производим пересборку со вставкой
//нового значения
*_map_ = rehashUp(_map_, e);
}
(*_map_)->size++;
}
Обёртка для неё. Она позволяет использовать в качестве аргументов непосредственный значения.
void put(Hashmap **_map_, K key, V value) {
Entry *e = (Entry*)malloc(sizeof(Entry));
e->key = key;
e->value = value;
raw_put(_map_, e);
}
Вспомогательная функция rehashUp. Создаём новую карту с новыми размерами, проходим все значения и вставляем их в новую карту.
Hashmap* rehashUp(Hashmap **_map_, Entry* e) {
Hashmap *newMap = createHashmap((size_t)(*_map_)->arr_size * (*_map_)->multiplier,
(*_map_)->loadFactor,
(*_map_)->multiplier);
size_t i, size;
Hashmap *map = (*_map_);
Node *anchor = NULL;
Node *target = NULL;
size = (*_map_)->arr_size;
for (i = 0; i < size; i++) {
anchor = map->data[i];
//Вставляем Entry, чтобы не пересоздавать их лишний раз
while (anchor) {
target = anchor;
anchor = anchor->next;
raw_put(&newMap, target->value);
free(target);
}
free(anchor);
}
//Удаляем старую карту, чтобы не было утечек
free(map->data);
free(*_map_);
*_map_ = newMap;
raw_put(&newMap, e);
return newMap;
}
Поиск элемента. Возвращаем только значение пары
V get(Hashmap *map, K key) {
unsigned long long hash = HASHCODE(key);
size_t index = (hash % map->arr_size);
V retVal = NULL;
if (map->data[index] != NULL) {
if (CMP_EQ(map->data[index]->value->key, key)) {
return map->data[index]->value->value;
} else {
Node *anchor = map->data[index]->next;
while (anchor) {
if (CMP_EQ(anchor->value->key, key)) {
retVal = anchor->value->value;
break;
}
anchor = anchor->next;
}
}
}
return retVal;
}
Удаление элемента. Заметьте, здесь мы возвращаем указатель на всю пару, так что при использовании необходимо будет явно удалять это значение.
Entry* xremove(Hashmap *map, K key) {
unsigned long long hash = HASHCODE(key);
size_t index = (hash % map->arr_size);
Node *retVal = NULL; //узел
Entry *content = NULL; //это значение узла, которое будем возвращать
if (map->data[index] != NULL) {
if (CMP_EQ(map->data[index]->value->key, key)) {
retVal = map->data[index];
map->data[index] = map->data[index]->next;
} else {
Node *back = map->data[index];
Node *anchor = back->next;
while (anchor) {
if (CMP_EQ(anchor->value->key, key)) {
retVal = anchor;
back->next = anchor->next;
}
back = anchor;
anchor = anchor->next;
}
}
}
if (retVal != NULL) {
content = NULL;
}
free(retVal);
map->size--;
return content;
}
Функция, которая проходит по всей карте и применяет функцию f ко всем парам.
void mapIterate(Hashmap *map, void(*f)(Entry*, void*), void* data) {
size_t size, i;
size = map->arr_size;
for (i = 0; i < size; i++) {
Node *anchor = map->data[i];
while (anchor) {
f(anchor->value, data);
anchor = anchor->next;
}
}
}
Например, вот так
void printEntry(Entry *e, void* data) {
printf("%s\n", e->value);
}
...
mapIterate(map, printEntry, NULL);
Удаление всей карты будем проводить совместно с удалением всех пар. Именно для этого мы создавали freeEntry
void destroyHashmap(Hashmap **_map_) {
Hashmap *map = *_map_;
size_t i, size;
Node *anchor = NULL; //текущий узел
Node *target = NULL; //предыдущий узел
size = map->arr_size;
for (i = 0; i < size; i++) {
anchor = map->data[i];
while (anchor) {
target = anchor;
anchor = anchor->next;
FREE_ENTRY(&(target->value));
free(target);
}
free(anchor);
}
free(map->data);
free(*_map_);
*_map_ = NULL;
}
Пример использования
char* initAndCopy(const char *str) {
char *word = (char*)malloc(strlen(str)+1);
strcpy(word, str);
return word;
}
void main() {
Hashmap *map = createHashmap(2, 0.72f, 2.0f);
Entry *tmp;
size_t i;
char *words[][10] = {
{"one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"},
{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"}
};
for (i = 0; i < 10; i++) {
put(&map, initAndCopy(words[0][i]), initAndCopy(words[1][i]));
}
mapIterate(map, printEntry, NULL);
destroyHashmap(&map);
for (i = 0; i < 10000; i++) {
map = createHashmap(2, 0.72f, 2.0f);
for (i = 0; i < 10; i++) {
put(&map, initAndCopy(words[0][i]), initAndCopy(words[1][i]));
}
destroyHashmap(&map);
}
_getch();
}
Основные преимущества хэш-карты это постоянство скорости вставки, удаления и поиска в среднем случае. Кроме того, ключ в карте не требует реализации операции "больше-меньше", требуется наличие операции равенства и хэш-функции. Из-за этого возникают и свои проблемы. Так как значения хранятся неупорядоченно, то поиск максимума и минимума будут порядка O(n), так как придётся просмотреть все элементы. А если хэш-функция "плохая" и даёт много одинаковых кодов, то скорость сильно снизится.
