Хэш-карта с открытой адресацией
Хэш-карта с открытой адресацией
В хэш-карте с закрытой адресацией в случае коллизии элементы кладутся в корзину, в качестве которой могут выступать, например, список или дерево. В хэш-карте с открытой адресацией в случае коллизии берётся какой-то другой элемент из этого же массива. В самом простом случае может использоваться линейный поиск, когда интервал между «пробами» элементов в массиве фиксированный. Например, индекс 12345, элементов в массиве 10, поэтому берём элемент с индексом 5. Если он занят и интервал равен единице, то берём шестой элемент. Если шестой занят, то седьмой и т.д. Так как у нас имеется коэффициент заполнения, то известно, что пустая ячейка всё-таки существует.
При квадратичном поиске интервал между элементами увеличивается как значение некоторого полинома второй степени.
При использовании метода двойного хэширования интервал вычисляется с помощью ещё одной хэш-функции.
Проблемой такого подхода (открытой адресации) является то, что скорость при заполнении значительно снижается и становится неприемлемой уже при заполнении от 70%, поэтому требуются более агрессивные схемы изменения размера. Очевидно также, что в хэш-таблице с открытой адресацией не может храниться элементов больше, чем всего элементов в массиве пар.
Кроме того, открытая адресация более требовательна к хэш-функции. Кроме того, что она должна давать равномерное распределение, она должна давать минимальную кластеризацию – то есть, множество идущих друг за другом значений кодов (в то время как в хэш-таблице с закрытой адресацией достаточно того, чтобы функция не давала много одинаковых значений).
Открытая адресация избегает частого выделения памяти и поэтому может быть эффективно использована и при отсутствии пула памяти. Открытая адресация предоставляет более быстрый доступ к элементам таблицы. Кроме того, если таблица хранит только указатели, то она может быть полностью закеширована процессором.
Реализация
Начало почти такое же, как и у хэшкарты с закрытой адресацией. Так как у нас нет списков, то отсутствует структура «узел».
static const float LOAD_FACTOR = 0.5f;
static const size_t INITIAL_SIZE = 100;
static const float MULTIPLIER = 2.0f;
//Тип для ключа и для значения
typedef char* K;
typedef char* V;
//Пара <ключ, значение>
typedef struct Entry {
K key;
V value;
} Entry;
__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))
//Нахождение хэш-кода строки
__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;
}
typedef struct Hashmap {
Entry **data; //массив корзин
size_t size; //количество элементов в карте
size_t arr_size; //размер массива корзин
size_t limit; //целочисленное значение количества элементов карты
//при превышении которого происходит пересборка
float loadFactor; //процентное заполнение карты, при котором
//происходит пересборка карты
float multiplier; //во столько раз увеличится размер карты при пересборке
} Hashmap;
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 = (Entry**)calloc(tmp->arr_size, sizeof(Entry*));
return tmp;
}
Вставка элемента гораздо проще. Вставляем элемент по индексу. Если занято, то идём по массиву, пока не найдём пустую ячейку. В данном случае используется алгоритм лнейного поиска с шагом 1.
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) {
map->data[index] = e;
}
else {
while (map->data[index]) {
index++;
if (index >= map->arr_size) {
index = 0;
}
}
map->data[index] = e;
}
}
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);
}
Функция пересборки
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_);
size = (*_map_)->arr_size;
for (i = 0; i < size; i++) {
//не создаём новых пар, вставляем прежние
if (map->data[i]) {
raw_put(&newMap, map->data[i]);
}
}
free(map->data);
free(*_map_);
raw_put(&newMap, e);
*_map_ = newMap;
return newMap;
}
Уничтожение карты весьма простое. Уничтожаем все инициализированные элементы массива, после чего сам массив и карту.
void destroyHashmap(Hashmap **_map_) {
Hashmap *map = *_map_;
size_t i, size;
size = map->arr_size;
for (i = 0; i < size; i++) {
if (map->data[i]) {
FREE_ENTRY(&(map->data[i]));
}
}
free(map->data);
free(*_map_);
*_map_ = NULL;
}
Поиск осложняется тем, что можно наткнуться на NULL
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]->key, key)) {
retVal = map->data[index]->value;
} else {
//Если элемент не NULL, только тогда сравниваем
while (map->data[index] == NULL ||
!CMP_EQ(map->data[index]->key, key)) {
index++;
if (index >= map->arr_size) {
index = 0;
}
}
retVal = map->data[index]->value;
}
}
return retVal;
}
Удаление затирает нулём значение элемента и возвращает пару. Удалять её должен сам пользователь карты.
Entry* xremove(Hashmap *map, K key) {
unsigned long long hash = HASHCODE(key);
size_t index = (hash % map->arr_size);
Entry *retVal = NULL;
if (map->data[index] != NULL) {
if (CMP_EQ(map->data[index]->key, key)) {
retVal = map->data[index];
map->data[index] = NULL;
} else {
while (!CMP_EQ(map->data[index]->key, key)) {
index++;
if (index >= map->arr_size) {
index = 0;
}
}
retVal = map->data[index];
map->data[index] = NULL;
}
}
map->size--;
return retVal;
}
Обход карты – просто идём по массиву и перебираем все ненулевые элементы.
void mapIterate(Hashmap *map, void(*f)(Entry*, void*), void* data) {
size_t size, i;
size = map->arr_size;
for (i = 0; i < size; i++) {
if (map->data[i]) {
f(map->data[i], data);
}
}
}
Наконец, какое-нибудь использование
void printEntry(Entry *e, void* data) {
printf("%s\n", e->value);
}
char* initAndCopy(const char *str) {
char *word = (char*)malloc(strlen(str) + 1);
strcpy(word, str);
return word;
}
void main() {
Hashmap *map = createHashmap(2, 0.5f, 2.0f);
size_t i;
Entry *tmp;
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);
printf("\n");
printf("%s\n", get(map, "four"));
printf("%s\n", get(map, "five"));
printf("%s\n", get(map, "six"));
printf("\n");
tmp = xremove(map, "six");
FREE_ENTRY(&tmp);
mapIterate(map, printEntry, NULL);
for (i = 0; i < 10000; i++) {
map = createHashmap(2, 0.5f, 2.0f);
for (i = 0; i < 10; i++) {
put(&map, initAndCopy(words[0][i]), initAndCopy(words[1][i]));
}
destroyHashmap(&map);
}
_getch();
}
