Я реализовал пользовательский класс HashMap (на C++, но не должен иметь значения). Реализация проста -Как улучшить сложность итерации HashMap?
- Большой массив содержит указатели на элементы.
- Каждый элемент содержит пару ключ-значение и указатель на элемент (чтобы сформировать связанный список в случае столкновения ключей).
- Я также использовал итератор для него.
Моя реализация приращения/уменьшения итератора не очень эффективна. Из текущей позиции итератор просматривает массив хэшей для следующей непустой записи. Это очень неэффективно, когда карта малонаселена (что было бы для моего случая использования).
Может ли кто-нибудь предложить более быструю реализацию, не затрагивая сложность других операций, таких как вставка и поиск? Мой основной вариант использования - поиск, вторичный - вставка. Итерации даже не нужно, я просто хочу знать это ради обучения.
PS: Почему я внедрил пользовательский класс? Потому что мне нужно найти строки с некоторой допустимой погрешностью, в то время как готовые хэш-карты, которые я видел, обеспечивают только точное совпадение.
EDIT: Чтобы уточнить, я говорю об увеличении/уменьшении уже полученного итератора. Да, это в основном сделано для того, чтобы пройти всю карту.
Ошибки в строках (ключах) в моем случае происходят из-за ошибок OCR. Поэтому я не могу использовать методы обработки ошибок, используемые для обнаружения ошибок ввода. Вероятность того, что кулачный персонаж ошибается, почти такая же, как и у последней.
Кроме того, мои ключи всегда являются строкой, одним словом, точнее. Количество записей будет меньше 5000. Значит, размер таблицы хэшей 2^16 для меня достаточно. Хотя он все равно будет малонаселенным, но все в порядке.
Мой хэш-функция:
размер хэш-код 16 бит.
Первые 5 бит для длины слова. ==> Максимальная длина ключа = 32. Разумно, учитывая, что ключ - это одно слово.
Последние 11 бит для суммы кодов. Я храню только буквы английского алфавита и не нуждаюсь в чувствительности к регистру. Так что 26 кодов достаточно, от 0 до 25. Таким образом, ключ с 32 'z' = 25 * 32 = 800. Это хорошо в пределах 2^11. У меня даже есть возможность добавить чувствительность к регистру, если потребуется в будущем.
Теперь, когда вы сравниваете ключ, содержащий ошибку с правильным, сказать «ад» с «привет» 1. Длина ключей составляет примерно то же 2. сумма их символов будет отличаться от суммы отброшенных/добавленных/искаженных символов.
в хэш-коде, поскольку первые 5 бит предназначены для длины, вся таблица имеет фиксированные разделы для каждой возможной длины ключей. Все разделы имеют одинаковый размер. В первом разделе хранятся ключи длиной 1, второй длины 2 и т. Д.
Теперь «hello» хранится в 5-й секции, так как длина равна 5.«Когда мы пытаемся найти« привет », Hashcode of 'hello' = (длина - 1) (сумма символов) = (4) (7 + 4 + 11 + 11 + 14) = (4) (47) = (00100) (00000101111)
аналогично, хэш-код из 'HELO' = (3) (36) = (00011) (00000100100)
- Прыгаем в его ведро, и не найти это там.
- поэтому мы пытаемся проверить ОДИН искаженный символ. Это не изменит длину, но изменит сумму символов с max -25 до +25. Таким образом, мы ищем 25 мест назад на 25 мест вперед. т. е. мы проверяем сумму из (36-25) на (36 + 25) в том же разделе. Мы его не найдем.
- Мы проверяем дополнительную ошибку символа. Это означает, что правильная строка будет содержать только 3 символа. Итак, переходим к третьему разделу. Теперь сумма символов из-за дополнительного символа увеличилась бы на максимум 25, его нужно будет компенсировать. Поэтому ищите третий раздел для соответствующих 25 мест (36 - 0) - (36 - 25). Снова мы не находим.
- Теперь мы рассмотрим случай отсутствия персонажа. Таким образом, исходная строка будет содержать 5 символов. И вторая часть хэш-кода, сумма символов в исходной строке, будет больше в 0 - 25 раз. Поэтому мы ищем соответствующие 25 ведер в 5-й секции (36 + 0) до (36 + 25). Теперь, когда 47 (суммарная часть «hello») находится в этом диапазоне, мы найдем соответствие хэш-кода. Ans мы также знаем, что это совпадение будет связано с отсутствующим персонажем. Поэтому мы сравниваем ключи, допускающие допуски на 1 отсутствующий символ. И мы получаем матч!
В действительности, это реализовано, чтобы допускать более одной ошибки в ключе. Он также может быть оптимизирован для использования всего 25 мест для первого раздела (так как он имеет только один символ) и так далее. Кроме того, проверка 25 мест кажется излишней, так как мы уже знаем самый большой и наименьший символ ключа. Но он становится сложным в случае множественных ошибок.
Я не понимаю, когда вы пытаетесь найти значение, не должны ли вы сразу перейти к первому «Элементу», содержащемуся в массиве с заданным ключом, а затем пересечь связанный список? Если вам нужно пройти весь массив, либо ваш массив слишком мал, либо ваша хеш-функция не очень хороша (единственный способ, которым это должно произойти, - столкнуться с конфликтами _tons_). – Jared
@ Jared I * think * (возможно, неправильно), что он говорит об итерировании всей хэш-карты *, а не только одной цепочки столкновений. Было бы хорошо знать, для лучшей ясности, согласен. – WhozCraig
Вы говорите, что хотите что-то вроде «привет» и «hwllo» для меня, сопоставленного с одним и тем же значением хэша (потому что они похожи - обратите внимание, что «e» и «w» можно легко случайно ввести для один на другой, основанный на том, где они находятся на клавиатуре QWERTY). Таким образом, вам нужен быстрый поиск, чтобы по существу группировать подобные строки? Потому что, если вы говорите, смотрите каждую строку и делаете сравнение (и находите ближайшую), вы не описываете ничего, что можно было бы дистанционно интерпретировать как хеш-таблицу. – Jared