Хэш-таблица

рубрики: Структуры данных | Дата: 3 мая, 2026
Скачать обработку с примерами из статьи: professia1c_HashTable.epf
Платформа: 8.3; Тип формы: управляемая.

В современных реалиях каждый разработчик должен иметь хотя бы минимальное представление о структурах данных. И о применимости их в различных алгоритмах. Так как часто это позволяет, во-первых, существенно ускорить производительность, а во-вторых, минимизировать количество строк кода. И сегодня я хочу поговорить об одной из таких структур данных. Это — хэш-таблица. В синтакс-помощнике вы конечно же не найдете описания такого типа объектов. Но тем не менее реалазация хэш-таблиц присутствует в любом современном языке программирования. И поскольку отличительной чертой хэш-таблицы является наличие пар ключ-значение, рискну предположить, что в 1С в этом качестве может выступать Соответствие. Плюс, если мы посмотрим на описание соответсвтвия в синтакс-помощнике, мы увидим, что при обходе элементов соответствия в цикле, порядок обхода не определен. Это также косвенно намекает на то, что при сохранении элементов в данной коллекции, для ключа высчитывается хэш. Далее мы проверим на практике насколько использование соответствия дает прирост в производительности в отдельных случаях, по аналогии с использованием хэш-таблиц.

Задача

Итак представим, что у нас есть два достаточно больших массива. И нам надо найти количество элементов первого массива, которые встречаются во втором массиве. Для простоты будем рассматривать ситуацию, когда каждое значение в массиве уникально, так как нас в первую очередь будет интересовать скорость выполнения нашего кода. Давайте создадим два массива одинаковой длины. Первый мы заполним сплошной последовательностью чисел от 1 до 5000 с шагом 1. А второй только четными числами.

МассивСплошной = Новый Массив;
МассивЧетных = Новый Массив;

СчетчикЧетных = 0;
Для Счетчик = 1 По 5000 Цикл
	СчетчикЧетных = СчетчикЧетных + 2;
	МассивСплошной.Добавить(Счетчик);
	МассивЧетных.Добавить(СчетчикЧетных);
КонецЦикла;

Очевидно, что количество найденных элементов должно быть в 2 раза меньше чем количество элементов в массиве, т.е. 2500. Теперь рассмотрим способы, которыми можно решить данную задачу.

Метод перебора. Цикл в цикле

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

&НаСервере
Функция ВыполнитьПоискПеребором(МассивСплошной, МассивЧетных)

	Счетчик = 0;
	ВремяНачала = ТекущаяУниверсальнаяДатаВМиллисекундах();
	
	Для каждого Элемент Из МассивСплошной Цикл
	
		Для каждого ЭлементЧетный Из МассивЧетных Цикл
		
			Если Элемент = ЭлементЧетный Тогда
				Счетчик = Счетчик + 1;
			КонецЕсли;
		
		КонецЦикла;
	
	КонецЦикла;
	
	ВремяОкончания = ТекущаяУниверсальнаяДатаВМиллисекундах();
	ВремяВыполнения = ВремяОкончания - ВремяНачала;
	
	Возврат "Поиск перебором." + Символы.ПС +
		"Найдено элементов: " + Счетчик + Символы.ПС +
		"Время выполнения: " + ВремяВыполнения + " миллисекунд";

КонецФункции

И я уверен, что большинство 1С-ников будут как раз таки решать эту задачу вышеприведенным способом. Особенно, если до этого не программировали на других языках и не получали профильного образования. Но как известно почти каждую задачу можно решить несколькими способами. Давайте попробуем использовать при решении соответствие.

Решение с использованием соответствия

Обойдем в цикле второй массив с четными числами и запишем его в соответствие. В качестве ключа будем использовать значение элемента массива. А в качестве значения элемента соответствия будем записывать количество повторяющихся элементов массива, значение которого указано в виде ключа. Поскольку мы договорились, что элементы массива у нас повторяться не будут, значение элементов соответствия всегда будет равно 1. Далее перебираем в цикле первый массив и для каждого элемента пытаемся найти его в соответствии. Если в соответствии есть элемент с таким ключом, увеличиваем счетчик.

&НаСервере
Функция ВыполнитьПоискЧерезХэшТаблицу(МассивСплошной, МассивЧетных)

	Счетчик = 0;
	ВремяНачала = ТекущаяУниверсальнаяДатаВМиллисекундах();
	СоответствиеЧетных = Новый Соответствие;

	Для каждого ЭлементЧетный Из МассивЧетных Цикл
		СоответствиеЧетных.Вставить(ЭлементЧетный, 1);
	КонецЦикла;

	Для каждого Элемент Из МассивСплошной Цикл
		КоличествоСоответствий = СоответствиеЧетных.Получить(Элемент);
		Если КоличествоСоответствий <> Неопределено Тогда
			Счетчик = Счетчик + КоличествоСоответствий;
		КонецЕсли;
	КонецЦикла;
	
	ВремяОкончания = ТекущаяУниверсальнаяДатаВМиллисекундах();
	ВремяВыполнения = ВремяОкончания - ВремяНачала;
	
	Возврат "Поиск через соответствие." + Символы.ПС +
		"Найдено элементов: " + Счетчик + Символы.ПС +
		"Время выполнения: " + ВремяВыполнения + " миллисекунд";
	
КонецФункции

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

Сравнение скорости двух подходов.

В шапке статьи вы можете по ссылке скачать обработку в которой есть обе вышеприведенные функции, которые выполняются последовательно для одного и того же количества элементов с выводом результатов. И вот, что у меня получилось для количества элементов в массивах равное 5000.

Как видим с колоссальнейшим отрывом побеждает поиск с использованием соответствия. Разница по времени составляет более чем в тысячу раз! Давайте теперь посмотрим почему же так происходит. За счет чего получается такой выигрыш по скорости.

Устройство хэш-таблицы

В первую очередь кратко взглянем на то, что же из себя представляет хэш-таблица. По сути хэш-таблица — это всего лишь массив. Но массив с каким типом данных? Когда мы ложим в хэш-таблицу пару ключ-значение, в первую очередь к ключу применяется хэш-функция, результатом которой является некоторое целое число. это число и будет индексом ячейки массива в которой будет хранится значение. Но мы не можем сохранить значение непосредственно в ячейке массива. Так как при применении хэш-функции могут возникать коллизии. То есть существует вероятность, что считая хэш для двух разных ключей мы можем получить одно и то же целое число и вроде как обязаны сохранить в одной ячейке массива два разных значения, что сделать конечно же невозможно. Поэтому при реализации хэш-таблиц используются механизмы для разрешения таких коллизий. Например, в ячейке массива может хранится связанный список для значений у которых хэш ключа оказался одинаковым. Никто ведь нам не мешает сделать вот так:

ХэшТаблица = Новый Массив();
ХэшТаблица.Добавить(Новый СписокЗначений());
ХэшТаблица.Добавить(Новый СписокЗначений());

Ну а для тех, кто немного разбирается в объектно-ориентированных языках, позволю себе привести по-минимуму кусочки кода на java (с некотрыми упрощениями) из стандартного класса HashMap, который и реализует хэш-таблицу. Возможно для кого-то так будет понятней.

public class HashMap<K,V> {
..........
	Node<K,V>[] table;
	................
	static class Node<K,V> {
		final int hash;
		final K key;
		V value;
		Node<K,V> next;

Здесь мы видим, что хэш таблица, в первую очередь, представляет из себя массив класса Node.

Node<K,V>[] table;

Класс Node в свою очередь вложен в класс HashMap и является связанным списком. В нем мы видим несколько полей. Поле next в классе Node позволяет получить узел следующий за текущим. С помощью него мы можем идти вперед по списку. В поле key хранится исходное значение ключа. А в поле value соответственно значение. То есть поля key и value это и есть у нас пара ключ-значение, которые мы ложим в хэш-таблицу. Когда мы хотим получить значение по ключу, то сначала вычисляется хэш ключа, мы берем его в качестве индекса для массива table и по этому индексу получаем корневой элемент списка. Далее мы сверяем уже не хэш, а сам ключ со значением поля key. Если совпадают возвращаем значение — поле value. Если нет — идем дальше по списку.

Сложность алгоритмов

Теперь давайте оценим сложность двух наших алгоритмов по времени выполнения. Как известно для этого используется О-нотация. Так называемое «О большое». Которая позволяет асиптотически оценить рост времени выполнения кода при входном наборе данных n стремящемся в бесконечность. Здесь долго вдаваться в теорию не буду, т.к. это тема для отдельной статьи. Напомню лишь, что когда мы перебираем элементы массива в циле, сложность у нас O(n), то есть время выполнения линейно зависит от количества элементов в массиве. Когда мы внутри одного цикла выполняем еще один цикл, то получаем уже квадратичную зависимость O(n²). И наконец, то для чего мы рассматривали внутреннее устройство хэш-таблицы. Какова же сложность записи и чтения элементов в хэш таблицу? Поскольку под капотом используется массив, то время записи и получения элемента массива по индексу не зависит от размера массива и является константным — О(1).

Таким образом, в первом случае с вложенными циклами сложность у нас получается O(n²), а во втором, с использованием соответствия, сложность O(n). Отсюда и такая дикая разница в производительности для больших массивов. Просто представьте с какой скоростью растет координата y для параболы.

Заключение

В этой статье я на практическом примере продемонстрировал важность изучения структур данных и алгоритмов в которых они могут применяться. И наверное это сложно сделать без знания какого-либо из объектно-ориентированных языков программирования: С++, java, Python и т.д. Так как язык 1С, в отличие от перечисленных, скрывает особенности реализации своих структур данных. А как мы видим, в той же java можно провалиться в любую структуру данных, которая входит в стандартную поставку, и посмотреть как она реализована внутри. Также неплохо было бы порешать задачки на том же литкоде. И да, цикл в цикле — зло. Зачастую можно подобрать другое решение, которое позволит обойтись без влложенных циклов.