Хэш-карта с открытой адресацией

Теги: Хэш-карта с закрытой адресацией, закрытая адресация, линейный поиск, квадратичный поиск, двойное хэширование



Хэш-карта с открытой адресацией

В хэш-карте с закрытой адресацией в случае коллизии элементы кладутся в корзину, в качестве которой могут выступать, например, список или дерево. В хэш-карте с открытой адресацией в случае коллизии берётся какой-то другой элемент из этого же массива. В самом простом случае может использоваться линейный поиск, когда интервал между «пробами» элементов в массиве фиксированный. Например, индекс 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();
}
Q&A

Всё ещё не понятно? – пиши вопросы на ящик email

Хотите помочь? - отключите AdBlock и посмотрите рекламу
Хэш-карта с закрытой адресацией