Гарвард. CS50 на русском. 1. Короткие видео. 1. Хэш таблицы 

бабки плати - будет женская озвучка

@@medicaldoctoronyoutube йоу-йоу вай аре ю соу агрессив?

в америке все такие

Isn't there an English version of this video?

it doesnt matter because information in the video too important for complain to man voice

Тебе явно надо провериться у психиатра.

В двусвязном списке для поиска, вставки или удаления элемента нет другого пути, кроме как идти и сравнивать каждый элемент последовательно (с того или другого края). У хэш-таблиц при большом размере хэша относительно размера ключей, а также при хорошо написанной хэш-функции, коллизия встречается редко, так что в среднем такая таблица делает вышеуказанные действия за O(1). O(n) - худший случай, который можно получить, если использовать маленький размер хэша, при большом количестве ключей, а также при плохо написанной хэш-функции. То есть в общем и целом хэш-таблица может работать и за O(n), поэтому упоминают именно так, но на практике всё гораздо быстрее. В то время как в двусвязном списке нет путей для улучшения и приближения сложности алгоритма к O(1). P.S. Это то, как я понял, как это работает.

Представил какая скорость работы такого массива? При каждом добавлении элемента будет создаваться новый массив, в который будут копироваться все элементы из прошлого. По этому массивы и имеют фиксированную длину и именно об этом данное видео)

@@Jilexa list в Питоне это не совсем массив, это список, он заранее резервирует определенное количество ячеек для быстрого расширения. Естественно, при достижении конца зарезервированного места потребуется весь этот список переместить в свободную часть памяти, и снова с запасом. Что касается комментария @TakieKak Mi, то лучше было-бы привести в пример dict - словари в питоне, они представляют собой неупорядоченные коллекции произвольных объектов с доступом по ключу.

@@ivanklutru листы есть и в других яп, а массивв всегда конечны

грокаем

​@@BCR1984, программисты грокают, а погрОмисты грохают :)

@@Dima-uz8gi f[[ff[[f

Хпхаахахаххахах

АХАХАХХА

имеют

Сказали же - фиксированный размер

@@user-bi3kx5uf6d человек хочет сказать, что правильно говорить минусы

@@ktoya2131 да точно, прошу прощения. Зря быканул

@@user-bi3kx5uf6d бык

Вопрос: 4:25 если у меня после слова ant в этой строчке есть слово dog которое по идее записывается в 3, мы его записываем как 4? или сначала мы заполняем dog, а потом ant и ape

Да, есть тут такие люди)

так ответа и не получил)

В первом случае (а именно в том, который рассмотрен в видео (метод открытой адресации)) мы запишем слово dog в следующее свободное место в хэш-таблице, то есть да в 4 место, т.к. оно свободно. В том случае если 3 место ещё не будет занято, то слово dog будет записано в него (3 место), после чего будут записаны слова ant (4 место) и ape (5 место в в хэш-таблице). Во втором случае (метод цепочек) слово dog будет записано на 3 место (а именно в начало связного списка, где 3 -- это номер связного списка в данной хэш-таблице), а слова ape и ant (соответственно) будут записаны в список с индексом 0 в голову списка (в случае как это было показано в видео). Кароче, вникните в суть методов разрешения коллизий и вы всё поймёте. Это совсем не сложно + в видео это объяснено довольно детально.

@@zhhmelevskoj2013 в открытом методе не понял а как потом будем искать эти коллизии, если они ставятся уже беспорядочно и никакого алфавитного порядка нет

норм скорость. Я фигею вообще от притензий к халявному контенту.

Не понимаю , для чего она нужна ? Можете объяснить, пожалуйста?(

Почему ?

Теоретически все верно, здесь речь идет про статические массивы. Когда имеют ввиду динамические массивы, обычно уточняют это явно. Также, нужно иметь ввиду принцип работы динамических массивов. Например, возьмем структуры данных vector (C++), list (Python). Обе структуры представляют собой некие динамические массивы (каждый со своей спецификой, разумеется), но объединяет их то, что они всегда имеют какой-то диапазон ячеек про запас. То есть, даже создавая динамический массив, под капотом фактически создается массив, имеющий точное количество ячеек и не поддерживающий никакой дальнейшей расширяемости. Как только мы хотим внести в этот массив дополнительное значение, места для которого уже нет, происходит аллоцирование памяти, и весь массив переносится на новый участок памяти, размером больший, чем предыдущий. Поправьте меня, если я не прав.

@@user-zg8yl1fw4z все четко

@@user-zg8yl1fw4z все верно, если места уже не хватает в массиве то происходит копирование его всего на новый участок памяти но с еще несколькими ячейками для дальнейшего заполнения

Это ты не понимешь этих моментов

@@user-zg8yl1fw4z все отлично сказал👍