Как работают хэш-таблицы структуры данных
содержание видео
Дата: 2023-03-12
Похожие видео
Комментарии и отзывы: 19
ATtiny13a
а я просто беру 32-х битное число, раскладываю его на 16 младших и старших бит, старшие сдвигаю на 16 позиций, умножаю с переполнением на константное нечётное без знаковое 32-х битное число обе последовательности по 16 бит. На этом этапе стоит понимать, что умножение на нечётное с переполнением обратимая операция и является идеальной хэш функцией без коллизий. Далее я вычисляю исключающее из полученных результатов, ещё раз умножаю на нечётную константу и суммирую с ещё одной константой. На входе было 32-х битное число, на выходе другое 32-х битное число, мы можем так повторять много раз, повышая энтропию (главное, чтобы для каждой итерации были заранее заготовлены разные надёжные константные случайные числа.
Используя такой подход можно, к примеру, генерировать очень качественные случайные числа на видеокарте. А из-за того, что нет коллизий, эту функцию можно использовать за основу других алгоритмов хэширования с потерями для N-ой длины. К примеру можно заготовить константы условно под максимальное число итераций, чуть переделать функцию и уже получать из 64-х бит всего лишь 32, или из 2-х 32-х битных чисел всего лишь одно, что уже достаточно для итеративного сжатия последовательности бит до желаемого размера с высокой надёжностью.
ответить
а я просто беру 32-х битное число, раскладываю его на 16 младших и старших бит, старшие сдвигаю на 16 позиций, умножаю с переполнением на константное нечётное без знаковое 32-х битное число обе последовательности по 16 бит. На этом этапе стоит понимать, что умножение на нечётное с переполнением обратимая операция и является идеальной хэш функцией без коллизий. Далее я вычисляю исключающее из полученных результатов, ещё раз умножаю на нечётную константу и суммирую с ещё одной константой. На входе было 32-х битное число, на выходе другое 32-х битное число, мы можем так повторять много раз, повышая энтропию (главное, чтобы для каждой итерации были заранее заготовлены разные надёжные константные случайные числа.
Используя такой подход можно, к примеру, генерировать очень качественные случайные числа на видеокарте. А из-за того, что нет коллизий, эту функцию можно использовать за основу других алгоритмов хэширования с потерями для N-ой длины. К примеру можно заготовить константы условно под максимальное число итераций, чуть переделать функцию и уже получать из 64-х бит всего лишь 32, или из 2-х 32-х битных чисел всего лишь одно, что уже достаточно для итеративного сжатия последовательности бит до желаемого размера с высокой надёжностью.
ответить
pcsekret
зачем так усложнять? создаем массив в котором будет грубо говоря 10 ключей, каждый ключ это простое число от 0 до 9, значением же будет такой же массив, размером 10, в котором еще один массив размером в 10.
при поиске мы указываем 1 ключ, это значение в массиве А, теперь вводим 2й ключ, это значение в массиве Б, теперь вводим 3й ключ, это значение в массиве В. Все что требуется при поиске указать 3 числа от 0 до 9, а размер массива будет 10х10х10. Тем самым мы не перебираем массив при поиске, а просто обращаемся к номерам каждого из массивов.
к примеру значение трех ключей 333, будет обращением к элементу 3 в каждом массиве. ни какого поиска быстрая работа алгоритма.
Пример словарь русского языка, создаем 33 массива, в каждом размещаем слова из букв, где-то слов аж 7 тысяч с небольшим, поиск слов на эту букву будет долгим. вместо этого я создал переменный массив, в котором размещаю массивы по 1000 слов, и на эту конкретную букву. в случае, если идет переполнение массива, создаем еще один массив на 1000 слов.
В конкретном случае получается, что я указываю 2 ключа, и ищу в массиве из 1000 слов.
ответить
зачем так усложнять? создаем массив в котором будет грубо говоря 10 ключей, каждый ключ это простое число от 0 до 9, значением же будет такой же массив, размером 10, в котором еще один массив размером в 10.
при поиске мы указываем 1 ключ, это значение в массиве А, теперь вводим 2й ключ, это значение в массиве Б, теперь вводим 3й ключ, это значение в массиве В. Все что требуется при поиске указать 3 числа от 0 до 9, а размер массива будет 10х10х10. Тем самым мы не перебираем массив при поиске, а просто обращаемся к номерам каждого из массивов.
к примеру значение трех ключей 333, будет обращением к элементу 3 в каждом массиве. ни какого поиска быстрая работа алгоритма.
Пример словарь русского языка, создаем 33 массива, в каждом размещаем слова из букв, где-то слов аж 7 тысяч с небольшим, поиск слов на эту букву будет долгим. вместо этого я создал переменный массив, в котором размещаю массивы по 1000 слов, и на эту конкретную букву. в случае, если идет переполнение массива, создаем еще один массив на 1000 слов.
В конкретном случае получается, что я указываю 2 ключа, и ищу в массиве из 1000 слов.
ответить
TOMAS
Очередное прекрасное видео про доступные знания, спасибо тебе Алек! За свой опыт (C, C#, Python, Js) не разу не притрагивался к хеш-таблицам только с открытым ртом смотрел как работает sha256 и думал о том какой вообще должна быть хеш-функция чтобы исключить коллизии потом понял что буду говорить что это невозможно пока кто нибудь не сделает такую реализацию наверно это уже и не будут называть страшным словом хеш-функция. Так вот я думаю что скорее всего этим типом хранения данных я займусь в следующим году)
ответить
Очередное прекрасное видео про доступные знания, спасибо тебе Алек! За свой опыт (C, C#, Python, Js) не разу не притрагивался к хеш-таблицам только с открытым ртом смотрел как работает sha256 и думал о том какой вообще должна быть хеш-функция чтобы исключить коллизии потом понял что буду говорить что это невозможно пока кто нибудь не сделает такую реализацию наверно это уже и не будут называть страшным словом хеш-функция. Так вот я думаю что скорее всего этим типом хранения данных я займусь в следующим году)
ответить
Кирилл
Столкнулся тут с оптимальным поиском, почитывая какую-то книгу была приведена ссылка на статью о том, что оптимальный поиск задан как суперпозиция поиска в глубину и ширину с разными весами, и веса подобраны в статье эмпирически. Поистине нет предела совершенству, некорректных мат задач тьма тьмущая, и огромная зияющая дыра в развитии методов их решений. Чем дальше заходим с развитием выч техники, тем больше проблем для решения)
ответить
Столкнулся тут с оптимальным поиском, почитывая какую-то книгу была приведена ссылка на статью о том, что оптимальный поиск задан как суперпозиция поиска в глубину и ширину с разными весами, и веса подобраны в статье эмпирически. Поистине нет предела совершенству, некорректных мат задач тьма тьмущая, и огромная зияющая дыра в развитии методов их решений. Чем дальше заходим с развитием выч техники, тем больше проблем для решения)
ответить
Dmitry
В конце (выбор хэш-функции, надо полагать, имелось в виду не создание объекта В хэш-таблице, а создание объекта хэш-таблицы. И еще мне не совсем понятно, при чем тут взлом. Специально выбирать данные для максимизации числа коллизий - это достаточно странное занятие. Не уверен, что в реальной жизни можно с этим столкнуться, учитывая, если только вместо произвольных данных для вставки не выбирать одинаковые, приводящие к коллизиям.
ответить
В конце (выбор хэш-функции, надо полагать, имелось в виду не создание объекта В хэш-таблице, а создание объекта хэш-таблицы. И еще мне не совсем понятно, при чем тут взлом. Специально выбирать данные для максимизации числа коллизий - это достаточно странное занятие. Не уверен, что в реальной жизни можно с этим столкнуться, учитывая, если только вместо произвольных данных для вставки не выбирать одинаковые, приводящие к коллизиям.
ответить
Ivan
единственное и может быть самое главное что не сказал автор:
используйте хеш-таблицы тогда, когда более простые структуры данных ну вот совсем никак реализовать не получается
следствие:
в 95% случаев хеш-таблицы вообще то избыточны и совершенно не нужны, потому что [может быть и сложнее в реализации] можно обойтись более простыми и сильно сильно быстрее работающими структурами данных
ответить
единственное и может быть самое главное что не сказал автор:
используйте хеш-таблицы тогда, когда более простые структуры данных ну вот совсем никак реализовать не получается
следствие:
в 95% случаев хеш-таблицы вообще то избыточны и совершенно не нужны, потому что [может быть и сложнее в реализации] можно обойтись более простыми и сильно сильно быстрее работающими структурами данных
ответить
Дмитрий
А почему для 32-битного инта возможно только 231 - 1 значений хэш-функции (см. 5: 13? В Python отрицательные значения хэш-фукции совершенно точно возможны даже у объектов самых базовых типов, и что мешает сопоставить номера строк в хэш-таблицы в том числе и отрицательным значениям хэш-функции? Почему не честные 232?
ответить
А почему для 32-битного инта возможно только 231 - 1 значений хэш-функции (см. 5: 13? В Python отрицательные значения хэш-фукции совершенно точно возможны даже у объектов самых базовых типов, и что мешает сопоставить номера строк в хэш-таблицы в том числе и отрицательным значениям хэш-функции? Почему не честные 232?
ответить
Александр
Кстати, в Java реализации хэш-таблиц гораздо эффективнее (распределение по массиву более равномерно и оптимизировано, при множестве коллизий списки перестраиваются в деревья и обратно, при увеличении массива хэши не пересчитываются, есть варианты с сохранением порядка, конкурентнобезопасные и т. п)
ответить
Кстати, в Java реализации хэш-таблиц гораздо эффективнее (распределение по массиву более равномерно и оптимизировано, при множестве коллизий списки перестраиваются в деревья и обратно, при увеличении массива хэши не пересчитываются, есть варианты с сохранением порядка, конкурентнобезопасные и т. п)
ответить
Сергей
Сразу по поводу рекламы. Ни один курс. Вообще ни один - не даст вам знания уровня мидла. Самый максимум вы будете толковым стажёром, которого могут взять на джуна. Джун это примерно от полугода коммерческого опыта (именно коммерческого, а не опыта самостоятельного писания пет-проектов для портфолио)
ответить
Сразу по поводу рекламы. Ни один курс. Вообще ни один - не даст вам знания уровня мидла. Самый максимум вы будете толковым стажёром, которого могут взять на джуна. Джун это примерно от полугода коммерческого опыта (именно коммерческого, а не опыта самостоятельного писания пет-проектов для портфолио)
ответить
idodo
Привет, анимация не перекроет то, что всё скомкано. Человек, который первый раз знакомиться с этой темой, просто н проймет. Может стоит останавливаться на некоторых моментах. Не раскидывать код по разным частям экрана. Может вместо c#(это вроде он) стоит использовать псевдокод?
ответить
Привет, анимация не перекроет то, что всё скомкано. Человек, который первый раз знакомиться с этой темой, просто н проймет. Может стоит останавливаться на некоторых моментах. Не раскидывать код по разным частям экрана. Может вместо c#(это вроде он) стоит использовать псевдокод?
ответить
RusL
Видимо производители железа без работы не останутся.
Вывод - используйте меньше функций, и обращение по индексу. Это усложнит вам жизнь, зато ускорит работу программы.
Если переживаете за безопасность - размещайте рандомом, каждый раз при запуске программы.
ответить
Видимо производители железа без работы не останутся.
Вывод - используйте меньше функций, и обращение по индексу. Это усложнит вам жизнь, зато ускорит работу программы.
Если переживаете за безопасность - размещайте рандомом, каждый раз при запуске программы.
ответить
Line
Жесть, вот пишешь ты код, а на деле видишь только верхушку айсберга, вместе с твоими видео можно окунуться в самую глубину и понять, что ты ничего не знаешь, как все устроено на самом деле. Спасибо тебе за твою работу, которая мотивирует продвигаться в изучении)
ответить
Жесть, вот пишешь ты код, а на деле видишь только верхушку айсберга, вместе с твоими видео можно окунуться в самую глубину и понять, что ты ничего не знаешь, как все устроено на самом деле. Спасибо тебе за твою работу, которая мотивирует продвигаться в изучении)
ответить
Макс
Миф про то, что не нужно знать ничего за пределами своих прямых обязанностей порождён теми, кто заинтересован, чтобы программисты пахали, никуда не стремились и умерли на работе. Современный программист -- почти полный аналог фабричного рабочего 19го века.
ответить
Миф про то, что не нужно знать ничего за пределами своих прямых обязанностей порождён теми, кто заинтересован, чтобы программисты пахали, никуда не стремились и умерли на работе. Современный программист -- почти полный аналог фабричного рабочего 19го века.
ответить
Я
Не хочу показаться душнилой НО хэш таблица это не абстрактный тип, а структура данных, которая является одной из возможных реализаций ассоциативного массива, который в свою очередь уже является абстрактным типом данных. Если конечно я ничего не путаю)
ответить
Не хочу показаться душнилой НО хэш таблица это не абстрактный тип, а структура данных, которая является одной из возможных реализаций ассоциативного массива, который в свою очередь уже является абстрактным типом данных. Если конечно я ничего не путаю)
ответить
Igor
От 0 до (232)-1 в инт может поместится значений. Если мы говорим что хэш 32бита то на все равно положительное там число или отрицательные, мы все равно будем его использовать поэтому для наглядности чтения его записывают как unsigned int.
Или я что то не понял?
ответить
От 0 до (232)-1 в инт может поместится значений. Если мы говорим что хэш 32бита то на все равно положительное там число или отрицательные, мы все равно будем его использовать поэтому для наглядности чтения его записывают как unsigned int.
Или я что то не понял?
ответить
nfdfneq
Разве нельзя проблему коллизии свести к приемлемому минимуму путём добавления соли к ключу, который в свою очередь сам есть строка фиксированной длины? Или путём получения индекса пересечением двух или даже более хэшей одного ключа?
ответить
Разве нельзя проблему коллизии свести к приемлемому минимуму путём добавления соли к ключу, который в свою очередь сам есть строка фиксированной длины? Или путём получения индекса пересечением двух или даже более хэшей одного ключа?
ответить
First
После первого просмотра осталось очень много открытых вопросов, но закрывать их не вижу смысла, так как я на своем пути пока не сталкивался с необходимостью понимать внутреннее устройство. Может быть изза того что я новичок. Хз
ответить
После первого просмотра осталось очень много открытых вопросов, но закрывать их не вижу смысла, так как я на своем пути пока не сталкивался с необходимостью понимать внутреннее устройство. Может быть изза того что я новичок. Хз
ответить
Сан
крайне крутой контент, спасибо большое. к сожалению или счастью я не смог найти даже аналогов такого качества. доступно, красиво, интересно. было бы крайне круто ещё послушать про деревья, красно чёрные и про set
ответить
крайне крутой контент, спасибо большое. к сожалению или счастью я не смог найти даже аналогов такого качества. доступно, красиво, интересно. было бы крайне круто ещё послушать про деревья, красно чёрные и про set
ответить
KKKompot
Интересно, что же будет, если запросить у хэш-таблицы значение по ключу, которого нет, но хэш которого совпадает тем ключом, которой есть в таблице? Ведь не каждый же элемент хэш-таблицы есть связный список?
ответить
Интересно, что же будет, если запросить у хэш-таблицы значение по ключу, которого нет, но хэш которого совпадает тем ключом, которой есть в таблице? Ведь не каждый же элемент хэш-таблицы есть связный список?
ответить
Добавить отзыв, комментарий
Другие видео канала
1:10
1:23
1:17
0:57
