Copyright(c) 2005 by Sergey Lyubka
Перевод (denk@RusNet)


			ЧТО ТАКОЕ ХЕШИ
			---------------

Давайте начнём с практического примера. Представим, что мы пишем
приложение сетевого мониторинга. Цель приложения - вычислить объём трафика,
переданных каждым IP адресом. Чтобы сделать это создадим структуру,
который содержит следующие данные:

struct ipstat {
	uint32_t	ip;		/* Исходный IP адрес */
	unsinged	bytes;		/* Переданные байты */
};

Итак, программа будет иметь множество таких структур, одну на каждый
"пойманный" IP адрес. Когда пришёл IP-пакет мы должны:
	1)  найти структуру во множестве
	2)  если не найдена, разместить новую структуру и добавить её во множество
	3)  для найденной структуры увеличить 'bytes' на длину пакета.

Наипростейший способ сделать это - организовать структуры в связный список:

struct ipstat {
	struct ipstat	*next;		/* Следующий элемент списка */
	uint32_t	ip;		/* IP адрес */
	unsigned	bytes;		/* Переданные байты */
};

Это будет прекрасно работать, если число структур в списке не очень большое.
Шаг "1)  найти структуру во множестве" требует сканирования всего списка:

struct ipstat *
lookup(uint32_t ip)
{
	struct ipstat	*p;

	for (p = head; p != NULL; p = p->next)
		if (p->ip == ip)
			return (p);

	return (NULL);
}

Большие сети могут генерировать многие тысячи пакетов в секунду. Если различия
трафика большое, наш список может содержать тысячи элементов. Подразумевается,
что мы должны искать (т.е. вызывать функцию lookup()) много тысяч раз в секунду.
Связный список, показанный выше, не обеспечивает требуемую скорость.
Он, фактически, едва ли не самый медленный потому, что выполняется линейное
сканирование от начала до конца всех элементов списка.

Как мы можем сделать эту функцию быстрее?

Например, это может быть оптимизировано таким образом: для каждого успешного
поиска мы переносим элемент в начало списка. При каждом следующем поиске он
может быть найден быстрее. Этот способ связного списка самоорганизуется:
менее требующиеся ноды будут вытолкнуты в конец списка, а наиболее "популярные"
окажутся в начале.

Сделав такое, довольно трудно предсказать среднее время поиска:
это зависит от природы трафика. В некоторых случаях этого может быть
достаточно. Этот способ работает только при маленьком числе активных
машин в сети, пока другие не активны.

В общем, чтобы обеспечить быстрый поиск, множество должно быть организовано
другим способом. Под поиском здесь я имею в виду 'поиск структуры ipstat по
указанному IP адресу'. Какой способ может быть самым быстрым? Наискорейшая
возможность это индексированный поиск (хотя это уже не поиск, прим.пер.).
Давайте создадим массив:

	#define	IPRANGE	4294967296
	struct ipstat	*array[IPRANGE];

IP адрес это 32-битное целое, возможный диапазон IP адресов будет от 0
до 4294967296. Мы создаём массив указателей на структуры ipstat и для каждого
входящего пакета делаем поиск:

struct ipstat *
lookup(uint32_t ip)
{
	return (array[ip]);
}

Да, это на много бытрее - наибыстрейший способ поиска значения (struct ipstat *)
по ассоциированному ключу (uint32_t ip). Единственная проблема с этим - это
память, которую возьмёт 'struct ipstat *array[IPRANGE]'.

На 32-битных машинах это 4ГБ * sizeof(pointer), это 16 Гигабайт.
Нехорошо. Другое дело, что почти вся память этого массива не будет использована.
Массив содержит около 4 миллиардов элементов. Мы же собираемся просматривать
тысячи IP адресов. Память будет потеряна. И, вероятно, ни одна современная
операционная система не позволит нам распределить 16 ГБ памяти под массив.

Что же нам делать? Ну, уменьшать массив. Давайте уменьшим его, скажем, до 1000:

	#define	SIZE	1000
	struct ipstat	*array[SIZE];

И каждый IP адрес мы должны 'отобразить' в этот диапазон: от 0 до SIZE.
Давайте напишем функцию 'hash', которая делает это:

unsigned
hash(uin32_t key)
{
	/* Переводим ключ (ip-адрес) в индекс массива */
	return (key % SIZE);
}

Теперь hash(ip) всегда будет возвращать значения между 0 и SIZE - 1.
Функция поиска может выглядеть примерно так:

struct ipstat *
lookup(uint32_t ip)
{
	unsigned	index;

	index = hash(ip);
	
	return (array[index]);
}

Бинго! Мы сделали это. lookup() всё ещё очень быстрая потому, что функция
hash() очень простая. Этот метод называется 'хеширование', а переменная
'array' называется 'хеш-таблицей'.

Осталась единственная проблема - когда два или более IP адреса отображаются
в один индекс. Это называется 'хеш-коллизией'. Есть несколько способов бороться
с этой ситуацией. Один из самых простых методов это организовать сталкивающиеся
ноды в связный список. При таком способе хеш-таблица не содержит самих
значений, но содержит головы связных списков.
Функция поиска станет выглядеть примерно так:

struct ipstat *
lookup(uint32_t ip)
{
	unsigned	index;
	struct ipstat	*p, *head;

	index = hash(ip);
	head = array[index];

	for (p = head; p != NULL; p = p->next)
		if (p->ip == ip)
			return (p);
	
	return (NULL);
}

Это очень сильно похоже на первый пример, на функцию поиска, основанную на
связном списке, про которую мы сказали, что она имеет очень плохое исполнение.
Да, это правда. Разница в том, что реализация связного списка содержит ВСЕ
элементы в одном списке. Хеш-таблица это множество более маленьких связных
списков, где каждый список содержит только столкнувшиеся элементы. Если
хеш-функция хорошая и равномерно разбрасывает ключи, то средняя длинна списка
будет
	
	ОБЩЕЕ_ЧИСЛО_ЭЛЕМЕНТОВ / SIZE

О том как выбрать хеш-функцию, динамическом изменении размера хеш-таблиц
в следующих обзорах.