Усовершенствованный алгоритм внешнего интерфейса 8: проблема с хеш-таблицей в заголовках

внешний интерфейс алгоритм

введение

Этот раздел начинается с главного вопроса интервью: как проектировать хеш-функции и как решать конфликтные проблемы, шаг за шагом объясняя следующие аспекты:

  • Что такое хеш-таблица?
  • Что такое хэш-функция?
  • Каковы общие хеш-функции?
  • Как разрешить конфликт?
  • Динамическое расширение хеш-таблицы
  • отвечать
  • + вопросы на собеседовании

1. Хеш-таблица (Хеш-таблица, Хеш-таблица)

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

Например, если вы хотите найти определенного студента по номеру студента, предположим, что студентов n. Хотите найти их по одному? Временная сложность — O(n), что слишком неэффективно. Конечно, вы также можете использовать алгоритм бинарного поиска, тогда временная сложность O (logn) Есть ли более эффективное решение?

Мы знаем, что временная сложность поиска массива по индексу O(1).Если мы будем хранить номер студента в массиве, это будет намного проще.Мы можем напрямую найти соответствующего студента по индексу (ключу).

Но в повседневной жизни клавишам обычно присваивают определенные значения, и использование 0, 1, 2... слишком просто. К номеру ученика обычно необходимо добавить такую ​​информацию, как класс и класс. Если мы знаем номер ученика определенного одноклассника, мы можем напрямую найти соответствующего ученика.

Это хеширование!С заданным номером ученика получить доступ к алгоритму преобразования (метод преобразования номера ученика 010121 в 1-й класс, 1-й класс, номер 21) и получить адрес соответствующего ученика (1-й класс, 1-й класс, номер 21).

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

Как показано ниже:

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

// 散列表
function HashTable() {
  let table = []
  this.put = function(key, value) {}
  this.get = function(key) {}
  this.remove = function(key) {}
}

Продолжаем смотреть на пример номера ученика выше.Каждому ученику соответствует номер ученика.Если учеников больше,если их 10w,то нам нужно хранить

  • 10w номеров студентов, каждый номер студента имеет 6 десятичных чисел, десятичное число представлено 4 битами (1 байт = 8 бит)
  • хэш-функция
  • 10w информация о студентах

Это требует дополнительной емкости хранения 100000 * 6 / 2 / 1024 = 292,97 КБ для хранения идентификатора учащегося каждого учащегося Таким образом, хеш-таблица представляет собой структуру хранения пространства во времени, которая является эффективным способом улучшения алгоритма. , Это более распространенный способ, но требуемое пространство также может быть головной болью, поэтому обычно между ними существует компромисс.

2. Хеш-функция

Здесь нужно понимать, что построение хеш-функции должно следоватьв общемДа:

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

Возьмем другой пример: недавно в школе собираются построить библиотеку для самостоятельных занятий учеников, если каждому учащемуся предоставить отдельный столик, то потребуется 10w листов, что заведомо невозможно, а есть ли способ? чтобы получить О? (1) А как насчет эффективности поиска без больших затрат на место?

Хеш-функции обеспечивают это решение, 10w — это много, но если мы разделим на 100, это будет от 0 до 999, что легко найти и не требует большого количества таблиц.

Соответствующая хэш-функция:

function hashTables(key) {
    return Math.floor(key / 100)
}

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

function hashTables(key) {
    return key >= 1000 ? 999 : key
}

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

####1. Создание лучших хеш-функций

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

Хорошая хеш-функция должна соответствовать следующим основным требованиям:

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

2. Общие хэш-функции

  • Метод прямой адресации: возьмите ключ или линейную функцию ключа в качестве хеш-адреса.
  • Метод цифрового анализа: посредством анализа данных найдите часть данных с меньшим конфликтом и создайте хеш-адрес. Например, номер ученика, обычно номер ученика того же класса учеников, первая часть которого не сильно отличается, поэтому вторая часть используется для построения хеш-адреса.
  • Метод взятия середины квадрата: Когда невозможно определить, какие биты ключевого слова распределены относительно равномерно, можно сначала найти квадратное значение ключевого слова, а затем взять средние биты квадратного значения в качестве хеша. адрес по мере необходимости. Это связано с тем, что: средние биты после вычисления квадрата связаны с каждым битом в ключе, поэтому разные ключи с высокой вероятностью будут генерировать разные хэш-адреса.
  • Метод случайных чисел: используйте случайную функцию, чтобы взять случайное значение ключевого слова в качестве хэш-адреса.Этот метод обычно используется в случаях с разной длиной ключевого слова.
  • Остаток после деления: в качестве хэш-адреса возьмите остаток p, полученный путем деления ключевого слова на число m, не превышающее длину таблицы n хеш-таблицы. Этот метод также можно использовать после того, как были использованы другие методы. Эта функция очень важна для выбора m, обычно берут простое число или используют n напрямую.

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

Например, в приведенном выше примере будет проблема: учащиеся, чьи номера учеников 011111 и 021111, оба равны 111 после деления на 100, что противоречит друг другу.

3. Разрешение конфликтов

При хешировании коллизии неизбежны. Как разрешить конфликт?

Существует несколько распространенных методов разрешения конфликтов:

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

Здесь мы вводим два самых простых: линейное обнаружение в методе открытой адресации и метод цепной адресации.

1. Линейное обнаружение

Линейное зондирование — простейший метод открытой адресации.При добавлении нового значения элемента в хеш-таблицу, если индексindexуже занято, попробуйтеindex + 1положение, еслиindex + 1тоже занято, то попробуйindex + 2позиция и т. д., если вы пытаетесь добраться до конца таблицы, а свободная позиция не найдена, начните с головы таблицы и продолжайте попытки, пока она не будет помещена в хеш-таблицу.

Как показано ниже:

Если это удалить: сначала проверьте хеш-значение, вычисленное хэш-функцией, сравните его с найденным хеш-значением, если оно совпадает, удалите элемент, если узел пустой, установите его какundefined, если они не равны, продолжить сравнениеindex + 1и так далее, пока не сравняются или не пройдут всю хеш-таблицу.

Если это поиск: сначала проверьте, равно ли хеш-значение, вычисленное хэш-функцией, хэш-значению, которое нужно найти, если оно равно, поиск завершен, и если он не равен, продолжайте проверкуindex + 1, пока не появится свободный узел (undefinedузел игнорируется), поиск завершается ошибкой, и в хеш-таблице нет искомого значения.

Очень просто, но и у него есть свои ограничения, так как элементов в хеш-таблице становится все больше, вероятность коллизий возрастает.

Временная сложность в худшем случае составляет O(n).

2. Метод адресной цепочки

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

Как показано ниже:

Вставить: вставить часть данных в соответствующий связанный список, временная сложность O (1)

Найти или удалить: начиная с головы цепочки, временная сложность поиска и удаления составляет O(k), где k — длина связанного списка.

4. Динамическое расширение

Когда мы ввели массив ранее, мы уже ввели расширение, вJavaScript, когда массивpushПри одних данных, если емкости массива недостаточно, тоJavaScriptОн будет динамично расширяться, и новая емкость будет в 1,5 раза больше старой емкости плюс 16.

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

5. Ответьте на вступительный вопрос

Как спроектировать хеш-функцию и как разрешить коллизии — важные вопросы для исследования хеш-таблиц.

Как спроектировать хеш-функцию?

Хорошая хеш-функция должна соответствовать следующим основным требованиям:

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

Как разрешать конфликты?

Существует несколько распространенных методов разрешения конфликтов:

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

Шесть, общие проблемы с хэш-таблицей

Мы уже почистили:

Сегодня кистьleetcode380: вставка, удаление и получение случайных элементов с постоянным временем

leetcode380: вставка, удаление и получение случайных элементов с постоянным временем

Спроектировать опору средней сложностиO(1), структура данных, которая выполняет следующие операции.

  • insert(val): вставляет элемент в коллекцию, если элемент val не существует.
  • remove(val): удаляет элемент из коллекции, если элемент val существует.
  • getRandom: случайным образом возвращает элемент из существующей коллекции. Каждый элемент должен иметьтакая же вероятностьвозвращается.

Пример :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

Ответы приветствуютсяGitHub.com/sister/JA…, здесь мы представили серию статей и тем по алгоритмам, используемым во внешнем интерфейсе (ответы), добро пожаловать в звезду, если вы чувствуете себя хорошо, нажмите здесь, чтобы поддержать его 😊

Семь, прекрасное прошлое

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

Отсканируйте код, чтобы присоединиться к тренировочному лагерю передовых алгоритмов, и создайте полную структуру данных и систему алгоритмов от 0 до 1!

Здесь мистер Боттл не только представляет алгоритм, но и объединяет алгоритм с различными полями интерфейса, включая браузеры, HTTP, V8, React, исходный код Vue и т. д.

Здесь вы можете каждый день изучать большую задачу по заводскому алгоритму (Ali, Tencent, Baidu, Byte и т. д.) или литкоду, а мистер Боттл ответит на него на следующий день!

Отсканируйте код, чтобы войти в лагерь, чтобы узнать! Отсканируйте QR-код внизу и ответьте на «алгоритм» в официальном аккаунте «Front-end Bottle King», чтобы автоматически привлечь вас в группу для обучения.

Категории