— простая реализация trie, неаккуратный переход к парадоксу Банаха-Тарского и прочие махинации
Я люблю хеш-таблицы. Получите любой объект, найдите для него ключ и бум, вы можете сохранить коллекцию из них и взять один или бросить туда новый в мгновение ока. Но что происходит, когда ключ не работает так, как вы хотите? Что происходит, когда вы получаете столкновения? Что вы делаете, когда эти коллизии происходят из-за того, что вы пытаетесь хэшировать строки, для которых почти невозможно разработать надежный уникальный хэш?
Я дарю вам хэш-стол-цепочку! Также известен как дерево префиксов.
Выглядеть круто? Отлично, давайте посмотрим, как это на самом деле работает. Код в этой статье будет написан на Java, но его можно легко реализовать на любом языке, поддерживающем полиморфизм.
Круто, так что давайте начнем. Чтобы начать с базового шага, давайте рассмотрим случай, когда мы хешируем только символы. И чтобы было еще проще, давайте рассмотрим только строчные буквы алфавита в кодировке ASCII. Сколько различных возможностей у нас есть?
У нас есть 26 различных символов нижнего регистра. Таким образом, мы должны учитывать 26 различных случаев. Таким образом, мы могли бы учесть эти возможные случаи, используя хеш-таблицу размера 26. Мы даже можем представить ее в виде массива.
// Each bucket represents a single ASCII lowercase character String[] buckets = new String[26];
Хорошо, пока это имеет смысл. Итак, давайте сделаем еще один шаг вперед в нашем стремлении к хеш-строкам и рассмотрим возможные комбинации из двух символов. Что происходит тогда?
Теперь за каждым из этих 26 возможных первых символов может следовать любой из 26 вторых символов. Таким образом, количество возможных вариантов равно 26², или 676. Итак, есть 26 возможных первых символов: это уже учтено в базовом случае. В этом есть смысл.
Следующий шаг также покрывается базовым случаем. Вам просто нужно 26 различных хеш-таблиц, по одной для каждого ключа в хеш-таблице для первого символа. Что ж, теперь мы застряли с 27 различными хеш-таблицами. Вау, это быстро выросло, не так ли?
Первое, что вы, вероятно, заметите, это то, что количество необходимых вам хеш-таблиц растет экспоненциально с количеством символов, если вы делаете это таким образом. Что мы делаем прямо сейчас, так это автоматически назначаем 26 хеш-таблиц для каждого символа, чтобы хранить различные возможные символы для следующей позиции в строке.
Это ужасно неэффективно. Подумайте, что произойдет, если нам нужно всего лишь хешировать 5 слов из 5 букв: «привет», «привет», «привет», «йалло» и «привет». Итак, в том виде, в котором эта структура видится в настоящее время, мы будем иметь:
1+26+26²+26³+26⁴ = 475 255 хэш-таблиц
Правильно, 475 255 хеш-таблиц, все для хеширования всего 5 слов! Так вообще жизнеспособна такая структура, особенно для разреженного списка слов, как в этом примере?
Что ж, одна оптимизация, которую мы можем сделать немедленно, состоит в том, чтобы убедиться, что новая хэш-таблица создается только при потенциальном столкновении хэш-ключа. Что-то вроде ленивого распределения. Так что же это означает для нас в приведенном выше примере?
Что ж, у нас будет первая хеш-таблица из 26 начальных символов. Сначала мы хэшируем «hello», что приводит к сохранению «hello» в сегменте «h» хеш-таблицы. Затем, когда мы пытаемся хэшировать «привет», происходит коллизия, и мы выделяем вторую хеш-таблицу в сегменте «h», чтобы различать вторые символы «e» и «o» в «привет» и «привет». . Затем мы сохраняем «привет» в сегменте «e» этой хеш-таблицы, а «привет» — в сегменте «o». Итак, на данный момент у нас всего 2 хеш-таблицы.
Затем мы пытаемся хэшировать «оклик» и получаем еще одно столкновение, на этот раз в ведре «о» для второго символа. Итак, на этом этапе мы выделяем другую хеш-таблицу для третьего символа, следующего за «о», чтобы различать «w» в «привет» и «l» в «оклик». Затем мы сохраняем «привет» и «привет» в ведрах «w» и «l» соответственно. Итак, теперь у нас есть 3 хеш-таблицы.
Хорошо, пока 3 хеш-таблицы для 3 слов. Это, безусловно, лучше, чем то, что было раньше, но выделение новой хэш-таблицы для каждого нового слова все еще не так уж и здорово. Что ж, давайте хэшировать остальные по тому же шаблону и посмотрим, что произойдет.
Теперь это 3 хеш-таблицы для 5 слов. Разница между количеством слов и количеством таблиц, безусловно, стала лучше. Ясно, что эту оптимизацию из предыдущей структуры стоит сохранить. Теперь вопрос в том, как вы кодируете это? Как создать хеш-таблицу, которая может хранить либо строки, либо другие хеш-таблицы? Что ж, ответ — полиморфизм.
// Because these can be either Strings or other hash tables, // we can store either with impunity private Object[] buckets = new Object[26];
При сохранении нового слова (или при извлечении) нам теперь нужно проверить, является ли данное ведро хэш-таблицы узлом или другой хеш-таблицей, а затем действовать соответствующим образом. В Java это можно сделать с помощью ключевого слова instanceof. Итак, учитывая это, как бы мы реализовали функцию put?
Прежде чем углубиться в полномасштабную реализацию, нужно обсудить еще 1 вещь. До сих пор мы обсуждали случаи, когда все слова в наших гипотетических словарях имеют одинаковую длину. Что произойдет, если это не так?
Что ж, легкое исправление для этого состоит в том, чтобы иметь хеш-таблицу из 27 вместо 26. 26 из 27 сегментов представляют следующие символы, а последний сегмент представляет собой отсутствие следующего символа. Красиво и просто.
Круто, так что давайте сделаем некоторую реализацию. Так как же будет работать функция put? Предположим, мы храним константу OFFSET, которая определяет начальное значение ASCII для строчных букв, 96 для «a». Давайте также предположим, что у нас есть сохраненный индекс, представляющий глубину, на которой текущая хэш-таблица существует в структуре. Назовите его pos_index. Четыре условия, которые мы должны были бы рассмотреть: 1) слово еще не было хешировано в этом месте, 2) там есть хеш-таблица, нам нужно дифференцировать по более позднему индексу, 3) это слово уже находится в этом месте, мы видите дубликат, или 4) есть коллизия, нам нужно создать хеш-таблицу, дифференцированную по следующему индексу.
Тогда функция put может выглядеть следующим образом:
public boolean put(String key) {
int hash_key = 0;
if(key.length() > pos_index) {
hash_key = (int)(key.charAt(pos_index)) - OFFSET;
}
Object temp = buckets[hash_key];
// Nothing in the bucket, create a node and store it there
if (temp == null) {
DataNode new_word_node = new DataNode(key);
buckets[hash_key] = new_word_node;
}
// Contains a table, put into that table to telescope and avoid collisions
else if (temp instanceof WordHashTable) {
WordHashTable table = (WordHashTable)(temp);
table.put(key);
}
// Contains a node, either a match or a collision
else if (temp instanceof DataNode) {
DataNode word_node = (DataNode)temp;
String word = word_node.getWord();
// If the same word is already there
if (key.equals(word)) {
word_node.newOccurrence();
}
// If word there is a collision,
// telescope by making another hash table for the differing letter
else {
WordHashTable table = new WordHashTable(pos_index+1);
table.set(word, temp);
DataNode new_word_node = new DataNode(key);
table.set(key, new_word_node);
buckets[hash_key] = table;
}
}
return true;
}
Я использовал структуру данных DataNode, о которой не упоминал, но структура довольно тривиальна. Для этой реализации я решил использовать структуру с 3 полями: строка слова, счетчик количества вхождений и счетчик количества обращений. Соответственно, с инкрементаторами, геттерами и сеттерами для чисел. Итак, как вы, вероятно, можете себе представить, функция put имеет дело со счетчиком вхождений, а функция get — со счетчиком обращений. Давайте также рассмотрим возможную реализацию функции get.
public DataNode get(String key) {
if (key == null) {
return null;
}
int hash_key = 0;
if(key.length() > pos_index) {
hash_key = (int)(key.charAt(pos_index)) - OFFSET;
}
Object temp = buckets[hash_key];
DataNode ret_val = null;
// Nothing in the bucket, return null
if (temp == null) {
}
// Contains a table, return what you get from table
else if (temp instanceof WordHashTable) {
WordHashTable table = (WordHashTable)(temp);
ret_val = table.get(key);
}
// Contains a node, either a match or a collision
else if (temp instanceof DataNode) {
DataNode word_node = (DataNode)temp;
String word = word_node.getWord();
// If the same word is already there
if (key.equals(word)) {
ret_val = word_node;
word_node.newRequest();
}
// If word isn't there, return null
else {
ret_val = null;
}
}
return ret_val;
}
Теперь, когда я изложил для вас идею, я просто дам вам остальную часть кода прямо здесь. Функции put и get — основная хитрость, так что все остальное довольно просто.
Реализация DataNode довольно тривиальна и показана в виде исходного кода ниже.
Итак, теперь, когда у нас есть работающая структура данных trie, давайте посмотрим на некоторые интересные последствия. Прямо сейчас, даже с этой реализацией, со средним корпусом слов, все еще есть некоторые ненужно выделенные пустые ведра.
Хорошо, теперь предположим, что эта структура была построена для хранения идеального словаря, который представляет собой гипотетический набор всех строк, возможных для латинского алфавита. Так, например, сюда входят «а», «аа», «ааа», «ааа…» и так далее до бесконечности, а также то же самое из b-z. И такие комбинации, как «abaa…», «acbdasdf…» и т. д. В таком случае эта структура данных будет чрезвычайно эффективной, потому что каждое ведро в каждой хеш-таблице в конечном итоге будет заполнено.
Вздох, в любом случае, есть одна крутая вещь, о которой стоит подумать:
На данный момент это дерево можно с таким же успехом смоделировать как конечный автомат, где чтение каждой дополнительной буквы, независимо от того, какая это буква, является возможным конечным состоянием.
Так что в основном, перефразируя комментарий Азимова о парадоксе неподвижного двигателя, это «хеш-таблицы до самого низа» или, возможно, более уместно на языке нашего поколения, «хэш-таблицы на несколько дней».
Хорошо, это была моя ужасная шутка для статьи. Извините, ребята, если вы сейчас уйдете, я пойму. Если вы все еще читаете, я аплодирую вам за то, что вы со мной! Будем надеяться, что я смогу дать вам что-то стоящее.
Такой словарь напоминает мне о парадоксе Банаха Тарского, математическом парадоксе, который вкратце утверждает, что подмножество объекта может быть использовано для создания точной копии объекта. В случае идеального словаря взятие подмножества словаря, начинающегося со второго символа, а не с первого символа, также даст полный совершенный словарь.
На самом деле на Youtube есть видео Майкла из Vsauce, в котором обсуждается этот самый парадокс. Это очень информативно и действительно стоит проверить. Ссылка на видео находится в разделе ссылок. Ну, на этом мои бредни на этот раз заканчиваются. Помните, что простые хэш-таблицы могут дать потрясающие результаты!
