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

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

sweet home 3d на русскомВ качестве краткого предисловия хочу сказать что даже популярная программа  sweet home 3d тоже создается с помощью этого я зыка программирования поэтому изучая этот язык ваши возможности буквально безграничны.

Во-первых, нам необходимо определить размер массива, который мы используем. Скажем, будем использовать массив из 260 элементов, значит, в среднем будет 10 элементов на каждую букву алфавита.
Сейчас, нам нужно создать хэш-функцию. Давайте создадим зависимости между буквами и цифрами:
A —> 0
B —> 1
C — >2
D —> 3

и далее до Z —> 25.
Простейший путь систематизации хэш-таблицы основывается на первой букве фамилии.
До сих пор у нас было 260 элементов, мы можем умножить первую букву фамилии на 10. Таким образом, когда задан ключ «Smith», ключ будет преобразован в индекс 180 (S – 19 буква английского алфавита, значит
S—>18, и 18*10 = 180).
Создав простую функцию для быстрой генерации порядкового номера, мы используем тот факт, что индексный номер может быть использован для получения доступа к элементу напрямую, и время, затраченное на получения доступа хэш-таблицы мало.
Но получение доступа к связанному списку ключей и элементов не будет столь быстр, пока мы вынуждены искать каждый единичную пару ключ-элемент.

Столкновения и обработка столкновения
Проблемы, возникают, когда мы имеет несколько фамилий начинающихся с одной буквы. “Webster” и “Whitney” будут соответствовать одному и тому же индексному числу – 22. Ситуация похожая на эту, когда два ключа получают одно и тоже положение в массиве называется – коллизии имен (или коллизии). Когда вы пытаетесь ввести элемент, вы обнаруживаете, что пространство уже заполнено другим значением.
Конечно, вы можете создать огромный массив, и это сделает невозможным саму возможность столкновения, но тогда теряется смысл использования хэш-таблицы. Одно из преимуществ хэш-таблицы в том, что она быстрая и маленькая.
Обработка коллизий с открытой адресацией
Простейший алгоритм обработки столкновений известен как метод открытой адресации или метод закрытого хэширования. Когда вы добавляете запись, скажем «Whitney», и обнаруживаете, что в ячейке уже существует запись(«Webster», например) тогда вы просто продолжаете запись в следующую ячейку (за «Webster»’ом). Если и она заполнена, вы идете в следующую, до тех пор, пока вы не найдете пустое пространство для заполнения новой ячейки(ведь все эти записи пригодятся после!)
…,
220 “White” | <— ### COLLISION ### : должен идти к следующему
221 “Webster” | <— ### COLLISION ### : идет дальше
222 | О, прекрасно. Ввожу сюда
223 |


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

Об авторе: Johan8888