[Играет музыка] ДАГ Lloyd: В настоящее время вы знаю много о массивах, и вы знаете, много о связанных списков. И мы обсудим плюсы и минусы, мы обсуждали, что связано списки может получить больше и меньше, но они занимают больше размер. Массивы являются гораздо более проста в использовать, но они ограничительный столько как мы должны установить размер массив в самом начале и тогда мы застряли с ним. 

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

Таким образом, в хэш-таблице, мы собираемся, чтобы попытаться объединить массив с связанного списка. Мы собираемся воспользоваться преимуществами массива, как произвольного доступа, будучи в состоянии просто идти к массиву элемент 4 или элемент массива 8 без перебора всей. Это довольно быстро, не так ли? 

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

И если все сделано правильно, мы вроде принятия преимущества обоих данных структуры вы уже видели, Массивы и связанные списки. Вставка может начать имеют тенденцию к тета 1. Тета мы не обсуждали, но тета только в среднем случае, что на самом деле произойдет. Вы не всегда будет есть наихудший сценарий, и вы не всегда будете иметь в лучшем случае, так что средняя сценарий? 

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

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

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

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

Основная идея, хотя это мы берем некоторые данные. Мы бежим, что данные через хеш-функция. И так как данные обработаны и он выплевывает номер, ОК? А потом с этим номером мы просто хранить данные мы хотим, чтобы сохранить в Массив в этом месте. Так, например, у нас есть, может быть, это хэш-таблицы строк. Он получил 10 элементов в нем, поэтому мы можем соответствовать 10 строк в нем. 

Скажем, мы хотим, чтобы прояснить Иоанна. Так как Иоанн данных мы хотим вставить в этом хэш-таблицы где-то. Где мы положить его? Ну, как правило, с Массив сих пор мы, вероятно, будет положить его в массив расположения 0. Но теперь у нас есть этот новый хэш-функции. 

И давайте скажем, что мы бежим от Иоанна через этот хэш-функции и это выплевывает 4. Ну вот, где мы захочет поставить Иоанна. Мы хотим, чтобы положить Иоанна в месте массива 4, потому что если мы хэширования Иоанна again-- скажем позже мы хотите, чтобы поиск и посмотреть, если Джон существует в этом хэш table-- все, что нужно сделать, выполняется его через тот же хэш Функция, получить номер 4 из, и быть в состоянии найти Джона немедленно в нашей структуре данных. Это очень хорошо. 

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

А потом мы просто посмотреть на месте массива 6. Павел попасть? Если это так, он в хэш-таблице. Павел не так ли? Он не в хэш-таблице. Это довольно просто. 

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

Так что же делает хорошую Хэш функция, верно? Ну хорошо хэш-функция должна использовать только будучи хэшируется данные, и все данных, хэшированного. Таким образом, мы не хотим, чтобы использовать anything-- мы ничего не включать то в другом месте, чем данные. И мы хотим, чтобы использовать все данные. Мы не хотим, чтобы просто использовать кусок это, мы хотим, чтобы использовать все это. Хэш-функция должна Также быть детерминированным. Что это значит? Ну это означает, что каждый раз, когда мы пройти тот же кусок данных в хэш-функции мы всегда получить тот же хэш-код из. Если я прохожу Джона в Хэш функция я выхожу 4. Я должен быть в состоянии сделать это 10000 раз, и я всегда буду получить 4. Эффективно, так не случайные числа могут быть вовлечены в нашей хэш tables-- в наших хэш-функций. 

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

Вот пример из хэш-функции. Я написал это одно вверх раньше. Это не особенно хорошая функция хеширования по причинам, которые действительно не нести вдаваясь в прямо сейчас. Но вы видите, что здесь происходит? Похоже, мы объявлении переменной называется сумма и установив его равным 0. А потом, видимо, я делаю что-то так долго, как strstr [J] не равен в обратную косую черту 0. Что я там делал? 

Это в основном просто еще один способ реализации [? strl?] и обнаружения, когда вы достигли конца строки. Так что я не есть на самом деле вычислить длину строки, Я только с помощью, когда я попал в Обратная косая черта характера 0 Я знаю, Я достиг конца строки. А потом я собираюсь держать переборе этой строки, добавив strstr [J], чтобы подвести, а затем на Конец дня собирается вернуться суммы мод HASH_MAX. 

В основном все это хэш функция делает это добавление до все значения ASCII в мой строка, а затем это возвращение некоторое хэш Комментарии от HASH_MAX. Это, вероятно, размер моей массива, верно? Я не хочу, чтобы получать хэш коды, если мой массив имеет размер 10, Я не хочу, чтобы получать из хэш-коды 11, 12, 13, я не могу положить вещи в эти места массива, что было бы незаконным. Я страдаю ошибку сегментации. 

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

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

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

ИТАК, давайте вернуться к этому хеш-таблица на секунду. Это где мы оставили от после того как мы вставлены Джон и Пол в этом хэш-таблицы. Вы видите здесь проблему? Вы можете увидеть два. Но в частности, сделать вас посмотреть возможные проблемы? 

Что делать, если я хэш Ринго, и это Получается, что после обработки что данные через хэш-функции Ринго сформировала хэш 6. Я уже получил данные в hashcode-- расположение массива 6. Так что это, вероятно, будет немного проблемы для меня сейчас, не так ли? 

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

Как мы это делаем, хотя, если он и Павел и выход хэш 6? Мы не хотим, чтобы перезаписать Павла, мы хотим, чтобы Пол там тоже. Таким образом, мы должны найти способ, чтобы получить элементы в хэш-таблице, что все еще сохраняет наше быстрое вставка и быстрый взгляд на. И один из способов борьбы с ним является сделать что-то под названием линейный зондирования. 

Используя этот метод, если у нас есть Столкновение, ну, что же нам делать? Ну, мы не можем поставить его в месте массива 6, или что-то хэш-код был создан, давайте его на HashCode плюс 1. И если это полный давайте положить его в HashCode плюс 2. Преимущество этого существа, если он не точно, где мы думаем, что он, и у нас есть, чтобы начать поиск, может быть, мы не должны идти слишком далеко. Может быть, мы не должны искать все п элементов хеш-таблицы. Может быть, мы должны искать пару из них. 

И поэтому мы все еще тенденцию к что средняя дело быть близко к 1 против близко к п, так что, может быть, буду работать. Итак, давайте посмотрим, как это может работать в реальности. И давайте посмотрим, если возможно, мы можем обнаружить проблема, что может произойти здесь. 

Скажем, мы хэш Барта. Так что теперь мы собираемся запустить новый набор строк через хэш-функции, и мы бежим Барта через хэш Функция, мы получаем хэш 6. Мы смотрим, мы видим 6 пустой, так что мы можем поставить Барта есть. 

Теперь мы хэш Лизу, и что также генерирует хэш 6. Ну теперь, когда мы с помощью этого линейный метод зондирования мы начинаем в 6, мы видим, что 6 заполнена. Мы не можем Лизу в 6. Так куда мы идем? Давайте 7. 7 пусто, так что работает. Так давайте Лизе там. 

Теперь мы хэш Гомера, и мы получаем 7. ОК хорошо мы знаем, что 7 полно Теперь, так мы не можем поставить Гомера есть. Итак, давайте по 8. Есть 8 доступны? Да, и близко к 7 8, так, если у нас есть, чтобы начать поиск мы не придется заходить слишком далеко. И так давайте Гомера на 8. 

Теперь мы хэш Мэгги и возвращает 3, слава богу мы можем просто поставить Мэгги есть. Мы не должны делать ничего Сортировать зондирования для этого. Теперь мы хэш Мардж, и Мардж также возвращает 6. 

Ну 6 полный, 7 полный, 8 полный, 9, все в порядке, слава Богу, 9 пуст. Я могу поставить Мардж в 9. Уже сейчас мы видим, что мы начинаем чтобы иметь эту проблему, где сейчас мы начиная растянуть вещи вроде из вдали от своих хэш-кодов. И, что тета 1, что средняя Дело в том, постоянная времени, начинает получать немного more-- начинают, как правило, немного больше, к тета п. Мы начинаем терять, что Преимущество хэш-таблицы. 

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

Другая проблема, хотя это мы Тем не менее, и до сих пор до этого момента, Мы только что-то понимая, что хэш-таблица является, мы по-прежнему есть только номер для 10 строк. Если мы хотим продолжать хэш граждане Спрингфилда, мы можем получить только 10 из них там. И если мы будем пытаться добавить 11 или 12, мы не есть место, чтобы поместить их. Мы могли бы просто быть спиннинг вокруг в круги, пытаясь найти пустое место, и мы, возможно, застряли в бесконечном цикле. 

Так что это своего рода дает взаймы идеи о чем-то называется цепочки. И это, где мы собираемся, чтобы принести связанные списки вернуться в картину. Что делать, если вместо того, чтобы хранить только сами данные в массиве, каждый элемент массива может провести несколько штук данных? Ну, что не имеет смысла, не так ли? Мы знаем, что массив может только hold-- каждый элемент массива может иметь только один кусок данных этого типа данных. 

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

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

И посмотреть, хорошо мы знаем которые выглядят в виде связанного списка может быть проблема, верно? Мы должны искать через это от начала до конца. Там нет случайных доступ в связанном списке. Но если вместо того, один связан Список, где поиск будет O п, теперь у нас есть 10 связные списки, или 1000 связанные списки, теперь это О п делится на 10, или О п делится на 1000. 

И в то время как мы говорили Теоретически о сложности пренебречь константы, в реальном Мир эти вещи на самом деле имеет значения, правильно? Мы на самом деле будет заметить что это происходит для запуска 10 раз быстрее, или в 1000 раз быстрее потому что мы распространении один длинный цепь по 1000 мелких цепей. И так каждый раз, когда мы должны искать через один из этих цепей мы может игнорировать 999 цепей Мы не заботимся о, и просто искать тот. 

Какой в ​​среднем 1000 раз короче. И таким образом, мы по-прежнему являются своего рода тенденцию к этой средней случае быть постоянное время, но только потому, что мы используя деления какого-то огромного постоянного множителя. Давайте посмотрим, как это может на самом деле выглядят, хотя. Так что это было хэш-таблицы мы должны были прежде, чем мы объявили, что хэш-таблицу был способен хранить 10 строк. Мы не собираемся этого делать. Мы уже знаем, Ограничения этого метода. Теперь наша хэш-таблицы будет массив из 10 узлов, указатели руководителям связанных списков. 

И сейчас это нуль. Каждый из этих 10 указателей NULL. Там нет ничего в наших хэш-таблицы прямо сейчас. 

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

Ну теперь работает со связанными списками, мы не работаем с массивами. И когда мы работаем со связанными списками мы знаю, что мы должны начать динамически выделение пространства и строительные цепей. Это своего рода how-- те ядро элементы построения связанного списка. Так давайте динамически выделить место для Joey, а затем давайте добавим его в цепи. 

Так что теперь посмотрите, что мы сделали. Когда мы хэш Джоуи мы получили хэш 6. Теперь указатель на место массива 6 указывает на голову связанного списка, и сейчас это единственный элемент связанного списка. И узел в том, что Связанный список Джоуи. 

Так что, если мы должны смотреть на Джоуи позже, мы просто хэш Джои снова, мы получаем 6 раз, потому что наши Хэш функция является детерминированной. И тогда мы начинаем в голову связанного списка отметил чтобы по местоположению массива 6, и мы можем итерации по, что, пытаясь найти Джои. И если мы строим наш эффективно хеш-таблицы, и наша хэш-функция эффективно распространять данные и, в среднем каждый из тех, которые связаны Списки в любом месте массива будет 1/10 размер, если мы только что его как один огромный Связанный список со всем в нем. 

Если мы распределяем, что огромное связаны Список по 10 связанных списков каждый список будет 1/10 размер. И таким образом в 10 раз быстрее, искать. Так давайте сделаем это снова. Давайте теперь хэш Росс. 

И, скажем, Росс, когда мы делаем что хэш-код вернемся 2. Ну теперь мы динамически выделять Новый узел, мы ставим Росс в этом узле, и мы сейчас сказать расположение массива 2, а указывая на нуль, указывает на голову связанный список, чьи только узел Росс. И мы можем сделать это еще раз, мы может хэш Рэйчел и получить хэш-код 4. таНос новый узел, положить в Рэйчел узел, и сказать ячейку массива 4 теперь указывает на голове из связанного списка, чьи Единственный элемент, случается, Рэйчел. 

ОК, но что произойдет, если у нас есть столкновение? Давайте посмотрим, как мы обращаемся с столкновений используя отдельный метод сцепления. Давайте хэш Фиби. Мы получаем хэш 6. В нашем предыдущем примере мы просто хранения строк в массиве. Это было проблемой. 

Мы не хотим, чтобы колошматить Джоуи, и мы уже видно, что мы можем получить некоторое кластеризации проблемы, если мы попытаемся и шаг через зонд и. Но что, если мы просто вид относиться к этому так же, как, верно? Это просто, как добавление элемента в голову связанного списка. Давайте просто выделения памяти пространство для Фиби. 

Мы скажем, следующие пункты указатель Фиби в старой голове связанного списка, а затем 6 раз указывает на Новый глава связанного списка. А теперь посмотрите, что мы изменили Фиби в. Теперь мы можем хранить два элементы с HashCode 6, и мы не какие-либо проблемы. 

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

Там по-прежнему еще один Структура данных там что, возможно, даже будет немного лучше с точки зрения обеспечения что наша вставка, удаление, и Посмотрите пояс даже быстрее. И мы увидим, что в видео на попыток. Я Дуг Ллойд, это CS50.