Archive for category Статьи

LPT мигает светодиодом

Эту статью я написал года четыре назад. А сейчас внезапно нашёл её, и решил выложить в блог. Довольно забавно :) Предупреждаю, я не несу ответственности за то, что может произойти с вашей техникой в результате применения данной информации.

В последнее время довольно долгое время меня мучила мысль о том, что неплохо бы как-нибудь своими силами связать компьютер с внешним миром. Плюс ко всему впустую простаивающий параллельный порт принтера меня угнетал, ибо у меня принтер подключён через USB. Я просмотрел несколько статей, описаний и прочей литературы, и то что у меня вышло в результате экспериментов назвать оригинальным язык не поворачивается, но, тем не менее, это может показаться кому-то интересным.

Задача стоит весьма тривиальная: научиться управлять мерцанием светодиода, подключённого к ПК через LPT-порт. Почему именно LPT? Потому что он довольно прост и в меру интересен.
Поехали!

Подготовка

Итак, что нам нужно для воплощения этого ужаса в реальное существо:

  • ПК
  • Компилятор какого-нибудь языка программирования (Assembler, С, С++, Pascal, etc…).
  • Некоторый программный инструментарий
  • Светодиод на 5В
  • LPT-шнур

Шнур у меня был только разрезанный, но вы можете использовать любой, главное всё правильно соединять. Вот мой шнур, с уже выведенными контактами для подключения светодиода (об этом речь пойдёт далее):

image

Вот, собственно, светодиод, купленный на ближайшем базаре за несколько денег. Он который будет светиться ярким синим светом:

image

Железо

Прежде чем приступить к практике, немного теории.

Как работаете LPT-порт? Об этом достаточно много написано, однако я всё-таки кратко расскажу как обстаят дела.

Параллельный порт ПК обычно используется для подключения принтеров, но на этом его возможности не ограничиваются. К нему можно подключать любое внешнее, самодельное устройство. LPT-порт имеет 25 пинов, но не все 25 необходимы. В нашем примере, например, нужно только 2. Рассматривать предназначение всех не будем.

image

Подключать светодиод будем плюсом к 2 пину, а минусом – к пину 18. Смотрите, не перепутайте, в противном случае светодиод может сгореть. Лучше предварительно проверить где у него плюс, где минус на маломощной батарейке.

Если у вас шнур папа-мама, то есть при подключении к компьютеру, на вашем конце шнура остаются входы, дело простое – просто воткнуть в нужные пины диод. Следует быть осторожным, неправильно подключив, можно повредить LPT-порт.

image

Лично я, раскурочив шнур, определил, какой относится к D0, какой к земле, и у меня всё выглядит примерно так, как показано на следующем рисунке. Я сидел с пробником, и вычислял, какая линия относится к D0. Очень занимательно! Вы можете найти более удочное решение.

image

В мерах предосторожности можно последовательно к диоду припаять сопротивление. Рекомендуют 470 Ом. На счёт заземления: кто-то заземляет не на пин GRD, а на корпус коннектора, но я предпочитаю пин.

На этом этапе вы должны представлять себе, как можно подключить светодиод к LPT-порту.

Программная часть

Подключить светодиод к компьютеру мы готовы, но вот, дальше-то что? А дальше самое интересное: управление им с бортового пульта. С одним светодиодом много не сделаешь: только включать/выключать его можно. Но зато можно менять частоту мигания, можно подключить ещё 7 светодиодов к остальным пинам D1-D8, и сделать светомузыку. Или приобрести яркие белые светодиоды, и сделать настольную лампу, питающуюся от LPT-порта, которая включается, когда вы начинаете печатать, чтобы подсветить вам клавиатуру. Можно вывести зелёненький светодиод куда-нибудь на видное место и написать программу, мигающую им, когда вам на E-mail приходит письмо. Сколько всего можно сделать только лишь с использованием светодиода! А подковав себя в электронике, можно собирать полноценные внешние устройства, но это, к сожалению, выходит за рамки данной скромной статьи.

Управление LPT-портом зависит от ОС. В былые времена, операционные системы DOS и Windows 95/98 разрешали пользовательским программам напрямую иметь доступ к железу. С появлением Windows NT/2000/XP всё изменилось, теперь общение с портами напрямую пользовательским программам запрещено, а разрешено только коду, выполняющемуся в режиме ядра. Всё это сделано в целях защиты и в других нужных и полезных целях, однако всё это одновременно и усложняет нашу задачу по подмигиванию светодиодом. Нам пришлось бы писать специальный драйвер устройства, разбираться в HAL (Hardware Abstraction Layer) и прочих премудростях. Вы можете заняться этим, почитав материалы по Microsoft DDK (Device Driver Kit). Но существует несколько обходных путей, позволяющих напрямую общаться с нашим LPT. Вообще, так делать не рекомендуется, но всё же, мы сделаем именно так, ибо так проще и нагляднее. Другими словами, напрямую получить доступ к регистрам LPT-порта просто так не удастся. Вы можете работать с драйвером устройства LPT как с обычным файлом при помощи функций CreateFile, ReadFile, WriteFile, а так же получать некоторую информацию о состоянии устройства функцией DeviceIoContol. Но работать с регистром, например, D0, который включает наш светодиод, не получится.

В ОС Linux всё обстоит по-иному. Там можно делать всё просто, имея на то специальные права. Необходимо только узнать по какому адресу находится ваш LPT. Обычно он находится по адресу 0378h. Узнать адрес в вашей системе можно, просмотрев файл /proc/ioports. Хотя, проще работать с файлом устройства /dev/lp0.

Разберём, как справиться с ОС Windows, потому что это немного сложнее.

Перед тем, как перейти непосредственно к программированию своими силами, проверим, работает ли всё это дело, собранное в прошлой части статьи. Для этого я использую чудесную программу мониторинга параллельного порта, так и названную: Parallel Port Monitor by Neil Fraser.

Как делаю я: запускаю программу, выключаю в ней все пины с 2 до 9, затем подключаю светодиод к LPT-порту (в нашем случае во второй пин, в D0). После этого в Parallel Port Monitor подаю единицу на D0. Светодиод должен загореться. Если ничего не произошло, возможно, вы неправильно его подключили или же в программе выбрали не тот LPT-порт. Попробуйте LPT1, LPT2, LPT3, если у вас их несколько.

Светодиод мигает? Отлично. Теперь можно побаловаться с ним своим программным кодом. Как было сказано ранее, это делать мы будем обходным путём. Если вы используете Windows 95/98/ME, можете сразу перейти к написанию программы, обходные пути вам не нужны, эти версии ОС Windows позволяют напрямую обращаться к портам.

1) Использование драйвера UserPort

Программа UserPort (автор Tomas Franzon), это системный драйвер режима ядра для Windows NT/2000/XP, который позволяет обращаться к портам ввода-вывода напрямую. Как раз то, что нам необходимо. Найти её в любом поисковике не составит труда. Скачав, настроив, согласно документации и запустив, мы получаем возможность мигать светодиодом из наших программ.

Сперва определим адреса портов в Device Manager. Видим, LPT1 по адресу 0378-037F. Именно туда мы и будем писать биты управления светодиодом. Пишем 1 – на контакты светодиода подаётся напряжение +5В, он загорается, пишем бит 0 – светодиод гаснет.

image

Напишем тестовую программу, мигающую светодиодом раз в секунду. Исходный текст приведён ниже. Здесь я использовал С++ со вставками ассемблерного кода и компилятор Visual C++. Вы можете использовать свой любимый язык программирования и компилятор, суть не меняется.

#include <iostream>
#include <windows.h>

void doLight(bool on)
{
	__asm
	{
		mov DX,0378h
		mov AL,on
		out DX,AL
	}
}

int main()
{
	while(1)
	{
		doLight(true);
		std::cout<<"Light On!"<<std::endl;
		Sleep(1000);
		doLight(false);
		std::cout<<"Light Off!"<<std::endl;
		Sleep(1000);
	}
	return 0;
}

Компилируем, запускаем, проверяем. Если светодиод стал мигать, значит всё ОК, всё работает, и можно издеваться дальше. Если же появилось сообщение об ошибке, например «First-chance exception at 0×00411524 in program.exe: 0xC0000096: Privileged instruction», значит, вы неправильно запустили или настроили UserPort. Обратитесь к документации по нему, там есть пример.

2) Использование библиотеки inpout32.dll.

Домашняя страница разработчиков библиотеки: http://www.logix4u.net. Там же можно найти много полезной информации. Перед тем как писать код, поместим в каталог с нашим проектом файлы inpout32.dll и inpout32.lib. В этих библиотеках имеются функции, позволяющие читать и записывать в порты.

Вот как выглядит исходный текст программы, с использованием этой библиотеки:

#include <iostream>
#include <windows.h>

#pragma comment(lib, "inpout32.lib")

// прототип функции
void _stdcall Out32(short PortAddress, short data);

void doLight(bool on)
{  Out32(0x378, on);
}

int main()
{   while(1)   {   doLight(true);   std::cout<<"Light On!"<<std::endl;   Sleep(1000);   doLight(false);   std::cout<<"Light Off!"<<std::endl;   Sleep(1000);   }  return 0;
}

Вот так вот:

image

Вроде, всё. Идею можно развить, и сделать какие-нибудь более полезные или интересные программные решения.

Заключение

Как видно, LPT-порт один из наиболее простых в работе портов, и с ним можно довольно-таки интересно работать. Умельцы собирают и подключают роботов через LPT-порт, делают в некотором роде систему управления квартирой, включают/выключают свет в комнате с компьютера и ещё много интересных вещей.

P.S.: Я где-то слышал, что люди собирают LPT- и USB-фонарики, и решил себе сделать нечто подобное из старого микрофона от наушников. Вот что вышло:

image

.NET, cc, e-mail, Hardware

ParallelFX, или как я испытывал параллельности

О существовании параллельных миров или пространств мы ничего наверняка сказать не можем, однако, если разговор заходит о компьютерах, то тут всё становится уже более определённо. Современные операционные системы поддерживают многозадачность (пусть иногда даже и псевдопараллельную). А в последнее время всё больше и больше ядер появляется в процессорах наших компьютеров.

Встаёт следующий вопрос: как эффективно использовать все ядра, и извлекать из них максимальную пользу? Есть резонный ответ: писать многопоточные программы. Мы можем самостоятельно управляться с множеством потоков, придумывать, как масштабировать наше параллельное приложение на разное количество процессоров, ловко обходиться с синхронизацией и разделением доступа к данным, пытаться избегать взаимоблокировок и прочих ужасов из мира многопоточного программирования. Но есть и другие способы (которые хоть и не избавят нас от проблем с разделяемой памятью), например, оградить себя от ручного создания и манипулирования потоками, и возложить эту тяжкую работу на кого-то другого. А именно, на послушный библиотечный код.

Не так давно был анонсирован CTP библиотеки, находящийся на верхушке .NET Framework – Parallel FX Library. Наверняка, с её помощью можно будет быстрее писать многопоточные программы, которые к тому же будут менее подвержены ошибкам. Суть в том, что наш код автоматически распараллеливается на множестве имеющихся процессоров. Это чем-то похоже на распараллеливание запросов, которое делает СУБД, но здесь мы имеем это в нашем коде и с нашими объектами.

ParallelFX состоит из двух частей: PLINQ и TPL. PLINQ – это движок параллельного выполнения запросов для LINQ (Более подробно про LINQ в вы можете почитать, например, в моей статье), благодаря которому мы можем с лёгкостью распараллелить LINQ-запросы. TPL же вводит такие конструкции, как параллельные циклы; задачи (Task, маленькие части кода, которые могут быть выполнены независимо, они чем-то похожи на Thread, но легче синхронизируемые), и «будущие времена» (Future, специальная задача, которая возвращает результат). Стоит отметить, что информации по библиотеке совсем мало, а та, что есть, уже немного устарела, поскольку всё это ещё находится в разработке и меняется…

Что к чему

Для того, чтобы испытать PFX в действии вам потребуется .NET Framework 3.5, а так же PFX December 2007 CTP, который вы можете закачать отсюда. Если вы не поклонник сугубо текстовых редакторов и сборки из мейкфайлов, вам так же потребуется Visual Studio 2008. Так же было бы неплохо иметь доступ к многопроцессорному компьютеру, чтобы проверить всё собственноручно.

Добавьте ссылку на сборку System.Threading.dll, так, все необходимые нам классы находятся в пространстве имён System.Threading.

PLINQ

Допустим, у нас имеются какие-то сложные и большие LINQ-запросы. А машина, на которой исполняется наша программа – многоядерная. Так, мы хотим использовать каждое ядро по максимуму с минимумом затрат времени и сил. PLINQ – то, что нам поможет. Мы просто вызываем метод расширения AsParallel() для наших данных, и они «обвёртываются» чем-то, что знает, как всё распараллелить.

IEnumerable<T> data = ...;
var q = from a in data.AsParallel() where w(a) orderby o(a) select f(a);

Так же нам доступен «параллельный» аналог класса Enumerable – ParallelEnumerable с аналогичными статическими методами.

Таким образом, PLINQ помогает LINQ-запросам работать быстрее и обрабатывать большее количество данных, используя доступные процессоры.

TPL и Параллельные циклы

Взгляните на последовательный простой цикл:

for (int i = 0; i < N; i++) {   a[i] = Math.Sqrt(a[i]);
}

Мы можем попросить нашу библиотеку распараллелить его. Для этого мы пользуемся параллельной версией цикла for – статической функцией из класса Parallel:

Parallel.For(0, N, i => {   a[i] = Math.Sqrt(a[i]);
});

Так, если у нас двуядерная машина, то половина итераций будет выполняться на одном ядре, тогда как другая половина – на другом. Библиотека адаптируется к конкретному компьютеру, и распараллеливает наш код на доступное число процессоров. На однопроцессорной машине настоящего распараллеливания не получится, и данный цикл выльется в простой последовательный.

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

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

Считаем Pi

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

Pi/4 = 1/1 - 1/3 + 1/5 - 1/7 + 1/9 - ...

Последовательное вычисление можно организовать так:

public double CalculatePi()
{   double sum = 0;   int sign = 1;   for (int i = 1; i < ITER_COUNT; i += 2, sign = -sign;)   sum += (double)sign / i;   return 4 * sum ;
}

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

В следующем коде присутствуют некоторые причудливые синтаксические конструкции из новой версии С#, так что для понимания, что же здесь происходит рекомендую сперва ознакомиться с C# 3.0. Здесь так же используется перегрузка параллельного цикла For с шагом и состоянием потока.

const int ITER_COUNT = 100000000;
const int INNER_ITER_COUNT = 1000;     

public double CalculatePi_ParallelFor()
{   double sum = 0;   Parallel.For<double>(1, ITER_COUNT, INNER_ITER_COUNT, () => 0,   (i, state) =>   {   int sign = (i / 2) % 2 == 0 ? 1 : -1;   for (int j = i; j < i + INNER_ITER_COUNT; j += 2, sign=-sign)   state.ThreadLocalState += (double)sign / j;   }, partialSum => { lock (this) {sum += partialSum;} }   );   return 4 * sum;
}

Здесь в каждую параллельную итерацию внешнего цикла, помимо счётчика передаётся переменная состояния state, в её свойстве ThreadLocalState мы сохраняем «частичную сумму». Впоследствии все частичные суммы добавляются к общей сумме sum, формируя окончательный результат. Я запустил оба варианта на компьютере с четырёхядерным процессором, и вот что из этого вышло:

D:\>ParallelPi.exe
Calculating Pi in total 1000000000 iterations
And 1000 inner iterations in each process
OS: Microsoft Windows NT 5.2.3790 Service Pack 2
Processors count: 4     

Working Non-Parallel For...
> 3,14159265
00:00:07.3516085     

Working Parallel For...
> 3,14159265
00:00:03.9321267     

Time rating:
1. 00:00:03.9321267     Parallel For
2. 00:00:07.3516085     Non-Parallel For

Параллельная версия почти в двое быстрее последовательной:

image

Обратите внимания на график загрузки ядер: при параллельной обработке все четыре ядра используются на 100%, в то время как при последовательном исполнении процессор загружен на ~25%.

image

Запустив этот же расчёт на своей однопроцессорной машине, я получил следующий результат:

Calculating Pi in total 1000000000 iterations
And 1000 inner iterations in each process
OS: Microsoft Windows NT 5.1.2600 Service Pack 2
Processors count: 1    

Working Non-Parallel For...
> 3,14159265
00:00:04.4050481    

Working Parallel For...
> 3,14159265
00:00:09.2341356    

Time rating:
1. 00:00:04.4050481     Non-Parallel For
2. 00:00:09.2341356     Parallel For

Последовательная версия оказалась в два раза быстрее «параллельной». Наверняка так получилось из-за того, что затраты на организацию параллелизма (а как его получить на однопроцессорной машине?) не окупились из-за отсутствия реального распараллеливания.

image

Заключение

На мой взгляд, технология ParallelFX весьма интересна. В виду нынешнего расцвета многоядерных процессоров идея параллельности становится как нельзя актуальнее. С появлением технологии LINQ, и функциональных расширений для C# и других языков, что-то подобное обязательно должно было появиться. Ну что ж, посмотрим, что будет дальше…

Мне было бы очень интересно услышать о ваших экспериментах с PFX, если вы решите испытать её :).

.NET, CSharp, framework, LINQ

Введение в хеш-таблицы

Среди всех структур данных, имеющихся в распоряжении у замечательной науки информатики, есть одна, которой многие люди восхищаются больше, чем другими. Это – хеш-таблица (Hash Table), несомненное достижение в области компьютерных наук. Практически все современные языки программирования имеют реализации хеш-таблиц в своих библиотеках. Чаще всего мы работаем с ними в виде словарей (или ассоциативных массивов), представляющих собой контейнеры множества пар ключ-значение.

Так как же устроены хеш-таблицы, почему они удобны, эффективны, и зачем нам или пользоваться? Здесь я привожу краткое введение в хеш-таблицы для тех, кто не знает и по каким-то причинам не хочет или не может изучить классические труды (они приведены в конце статьи). Одна из причин, побудивших меня написать этот текст, так это то, как показал мой опыт, что тема хеш-таблиц достаточно часто встречается в вопросах на собеседованиях ;).

Введение в хеш-таблицы

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

  • Добавление новой пары ключ-значение
  • Поиск значения по ключу
  • Удаление пары ключ-значение по ключу

Так, простой пример сессии работы с хеш-таблицой может выглядеть так (пример на Python):

>>> a = { "Vasya" : "123-23-12", "Petya" : "223-21-32" }
>>> a["Vasya"]
‘123-23-12′
>>> a["Masha"] = “264-32-32″
>>> a["Vasya"] = “000-00-00″
>>> a
{’Vasya’: ‘000-00-00′, ‘Petya’: ‘223-21-32′, ‘Masha’: ‘264-32-32′}

Среднее время поиска значения по ключу в хеш-таблице равно O(1). Это значит, что в среднем, наш поиск не будет зависеть от количества элементов в хеш-таблице, и будет равен некоторому константному значению. В зависимости от самой внутренней реализации хеш-таблицы, время поиска для наихудшего случая может быть O(n), то есть линейно завесить от количества элементов в таблице, либо же оставаться O(1).

Что же такое хеширование? Идея хеширования основана на распределении ключей в обычном массиве H[0..m-1]. Распределение осуществляется вычислением для каждого ключа элемента некоторой хеш-функции h. Эта функция на основе ключа вычисляет целое число n, которое служит индексом для массива H. Конечно, необходимо придумать такую хеш-функцию, которая бы давала различный хеш-код для различных объектов.

Например, если в качестве ключа хеш-таблицы нам нужно использовать строки, то можно выбрать хеш-функцию, основанную на следующем алгоритме (пример на С):

int hash(char* str) {
    int h = 0;
    for (int i=0; i<strlen(str); i++)
        h = (h*C + ord(str[i])) % m;
}

Где m – размер хеш-таблицы, C – константна, большая любого ord(c), а ord() – функция, возвращающая числовой код символа. Для каждого типа данных можно разработать свою хеш-функцию. Однако есть основные требования к хеш-функции: она должна распределять ключи по ячейкам хеш-таблицы как можно более равномерно, и должна просто вычисляться.

Вот иллюстрация хеш-таблицы. Мы видим, что индексами ключей в хеш-таблице является результат хеш-функции h, применённой к ключу.

image

Так же этот рисунок иллюстрирует одну из основных проблем. При достаточно маленьком значении m (размера хеш-таблицы) по отношению к n (количеству ключей) или при плохой хеш-функции, может случиться так, что два ключа будут хешированны в одну и ту же ячейку массива H. Такая ситуация называется коллизией. Хорошие хеш-функции стремятся минимизировать вероятность коллизий, однако, учитывая то, что пространство всех возможных ключей может быть больше размера нашей хеш-таблицы H, всё же избежать их вряд ли удастся. На этот случай имеются несколько технологий для разрешения коллизий. Основные из них мы и рассмотрим далее.

Хеширование с цепочками

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

image

Так, идея достаточно проста. Если при добавлении в хеш-таблицу в заданную ячейку мы встречаем ссылку на элемент связного списка, то случается коллизия. Так, мы просто вставляем наш элемент как узел в список. При поиске мы проходим по цепочкам, сравнивая ключи между собой на эквивалентность, пока не доберёмся до нужного. При удалении ситуация такая же.

Процедура вставки выполняется даже в наихудшем случае за O(1), учитывая то, что мы предполагаем отсутствие вставляемого элемента в таблице. Время поиска зависит от длины списка, и в худшем случае равно O(n). Эта ситуация, когда все элементы хешируются в единственную ячейку. Если функция распределяем n ключей по m ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка n/m ключей. Это число называется коэффициентом заполнения хеш-таблицы. Математический анализ хеширования с цепочками показывает, что в среднем случае все операции в такой хеш-таблице в среднем выполняются за время O(1). Ссылки на рассуждения и математические выкладки будут даны в конце статьи.

Хеширование с открытой адресацией

В случае метода открытой адресации (или по-другому: закрытого хеширования) все элементы хранятся непосредственно в хеш-таблице, без использования связанных списков. В отличии от хеширования с цепочками, при использовании метода открытой адресации может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, так что будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.

Для разрешения же коллизий применяются несколько подходов. Самый простой из них – это метод линейного исследования. В этом случае при возникновении коллизии следующие за текущей ячейки проверяются одна за другой, пока не найдётся пустая ячейка, куда и помещается наш элемент. Так, при достижении последнего индекса таблицы, мы перескакиваем в начало, рассматривая её как «цикличный» массив. Иллюстрация этого способа представлена на следующем рисунке:

image

Линейное хеширование достаточно просто реализуется, однако с ним связана существенная проблема – кластеризация. Это явление создания длинных последовательностей занятых ячеек, которое увеличивает среднее время поиска в таблице. Для снижения эффекта кластеризации используется другая стратегия разрешения коллизий – двойное хеширование. Основная идея заключается в том, что для определения шага смещения исследований при коллизии в ячейке используется другая хеш-функция, вместо линейного смещения на одну позицию.

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

Практика. Хеширование и ООП-языки

В некоторых популярных объектно-ориентированных языках программирования можно встретить методы вроде GetHashCode() и Equals() в интерфейсе корневого базового класса. Это даёт возможность использовать объекты любого класса в качестве ключей хеш-таблиц. В своих классах мы переопределяем эти методы в зависимости от наших потребностей, так GetHashCode() возвращает хеш-код нашего объекта, основываясь на его внутреннем состоянии. Так, вышеупомянутые методы должны подчинятся некоторым условиям:

  • a.Equals(a) == true
  • a.Equals(b) == b.Equals(a)
  • Если a.Equals(b) и b.Equals(c), то а.Equals(c)
  • Переопределяя в потомке Equals, следует переопределить и GetHashCode()
  • Если a.Equals(b) == true, то a.GetHashCode() == b.GetHashCode()
  • Значение a.GetHashCode() зависит только от внутреннего состояния объекта (его полней и свойств).

Так, реализация хеш-функции GetHashCode() зависит от класса объекта, и здесь мы можем использовать различные техники при расчётах.

Заключение

В статье было дано введение в хеш-таблицы. Однако многие темы остались за «бортом», например, методология подбора хорошей хеш-функции, и идеальное хеширование, при котором поиск даже в наихудшем случае выполняется за O(1). Так же формальный анализ и доказательства некоторых приведённых утверждений вы можете найти в литературе, обозначенной ниже.

Дополнительная литература

Тема хеширования достаточно широко описана в литературе. Следующие книги я могу рекомендовать в качестве авторитетных и достоверных источников информации:

  • Кормен, Лейзерсон, Ривест, Штайн – Алгоритмы. Построение и анализ. Издание 2-е, Вильямс, 2007 г. – Глава 11, страница 282.
  • Дональд Э. Кнут – Искусство программирования, том 2. Получисленные алгоритмы, Вильямс, 2007 г. – Глава 6.4.
  • Ахо, Хопкрофт, Ульман – Структуры данных и алгоритмы, Вильямс, 2000 г.
  • Левитин – Алгоритмы. Введение в разработку и анализ, Вильямс, 2006 г. – Глава 7.3, страница 323.

Пример реализации хеширования с цепочками можно найти в следующей книге:

  • Керниган, Пайк – Практика программирования. Издание 4-е, Вильямс, 2004 г. – Глава 2.9, страница 72.

Data structure, opera, Programming, python