Главная > Программирование > Распределенные хэш-таблицы.Теория

Распределенные хэш-таблицы.Теория

Распределенные хэш-таблицы
Эрик Сух
Хэш-таблицы – это эффективная реализация ключевого массива структуры данных, структура иногда известная как ассоциативный массив или карта(map). Всем программистам известно что браузеры и даже темы для Google Chrome делаются таким же способом с помощью этого же программного языка.
Если вы работаете в С++, возможно, вы встречались с STL map containter для ключевых массивов, реализованного с помощью бинарных деревьев, и эта статья даст вам понимание теории работы распределенных хэш таблиц.
Ключевые массивы и индексированные массивы.
Один из больших недостатков языков типа С то, что они не имеют ключевых массивов. В массиве языка С (также называемом индексированным массивом) есть только один путь для получения доступа к элементу и он лежит через номер индекса. Чтобы найти элемент 50 массива «сотрудники», вы должны получить доступ примерно таким путем:
Employees [50];
В ключевом массиве, однако, у вас есть возможность ассоциировать каждый элемент с «ключом», который может быть любым, начиная с имени до номера модели продукта. Таким образом, если у вас есть ключевой массив списков сотрудников, вы можете получить доступ к сотруднику «Джон Браун» таки образом:
Employee[“Brown,John”];
Базовая форма ключевого массива называется хэш-таблица. В хэш-таблице, ключ служит для поиска элемента независимо от порядкового номера.
Так как хэш-таблица использует индексированный массив, существует путь для преобразования ключа в порядковый номер (числовой показатель). Этот путь называется хэш-функция.
Хэш-функция
Хэш-функцией может быть что угодно. Как именно пишется хэш-функция, зависит от ситуации, но обычно, хэш-функция возвращает значение, опираясь на ключ и размер массива на котором основывается хэш-таблица. Также, есть одна важная вещь, которую иногда пропускают — хэш-функция возвращает одно значение, каждый раз, когда задается один и тот же ключ.
Скажем, вам потребуется систематизировать список из примерно 200 адресов по фамилиям. Хэш-таблица будет идеальна для этого, и вы сможете получить доступ к записям с помощью фамилий использованных как ключи.


Комментарии:

Об авторе: Johan8888