|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
|||||||||||
Хэш - таблица методом цепочек20.03.2015, 22:55. Показов 28158. Ответов 20
Метки нет (Все метки)
Всем привет!
Есть задание реализовать хеш-таблицу методом цепочек + с хэш - функциями: деление и умножение. Я не до конца понимаю, что вообще из себя представляет хэш - таблица в плане реализации на языке C++. Я создал структуру (пока что я думаю, что это структура):
0
|
|||||||||||
| 20.03.2015, 22:55 | |
|
Ответы с готовыми решениями:
20
Хэш-таблица (метод цепочек) Хеш-таблица методом цепочек |
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|||
| 20.03.2015, 23:19 | |||
|
2
|
|||
|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
|
| 20.03.2015, 23:27 [ТС] | |
|
Renji, 1) А какой список вы имеете в виду? Структуру с указателями на начало и следующий элемент или какую-то конструкцию C++ (List<int>...) (последнюю не проходили).
2) Но а если у меня например 10 элементов и попадаются элементы 39 и 49. Их код будет равен у обоих 9, как тогда к ним обращаться и записывать в список?
0
|
|
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
||||||||
| 20.03.2015, 23:44 | ||||||||
1
|
||||||||
|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
||||||
| 20.03.2015, 23:53 [ТС] | ||||||
|
Renji, а что делает эта строчка?
Все равно не понимаю, что происходит во время коллизии (как выглядит кодом и т.д.)
0
|
||||||
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|||
| 21.03.2015, 00:03 | |||
|
2
|
|||
|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
||||||||||||||||
| 21.03.2015, 00:09 [ТС] | ||||||||||||||||
|
Renji, конечно говорят, просто немного удивило то, что экземпляр table[] cоздается после того, как используется в строке
1) Вот эта функция
2) Здесь:
Большое спасибо за Ваши ответы, пролили свет
1
|
||||||||||||||||
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|||
| 21.03.2015, 00:30 | |||
Сообщение было отмечено d3vn как решение
Решение
1
|
|||
|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
|||||||||||
| 21.03.2015, 11:40 [ТС] | |||||||||||
|
Renji, спасибо за помощь!
Получился вот такой код, который вставляет элементы, но не получается реализовать функцию int find(int key); которая бы говорила есть ли такой элемент в очереди или нет. Вы не могли бы помочь ее написать или как-то хотя бы словесно строки выполнения объяснить?
Renji, пока есть только такая функция, которая проверяет на хэш-код как бы внешне, но не заходит внутрь списка по значению.
0
|
|||||||||||
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|||||||
| 21.03.2015, 11:41 | |||||||
1
|
|||||||
|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
|
| 21.03.2015, 11:47 [ТС] | |
|
Renji, супер, спасибо, оказалось все так просто.
А, кстати, препод говорил, что вот этот поиск должен выполняться за линейное время, типо в этом и фишка этих хэш - таблиц, мол, если бы мы решали в лоб, то делали бы прогон двумя форами, а так в одном форе запускаем функцию поиска и у нас все линейно... Но мне кажется, что это нереально что ли? По крайней мере для хэширования цепочкой, ведь все равно фором нужно будет пробегать элементы, если их несколько. Так ли это?
0
|
|
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
||
| 21.03.2015, 11:59 | ||
|
0
|
||
|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
|
| 21.03.2015, 12:00 [ТС] | |
|
Renji, можно еще вопрос?
Так же в задании нужно подсчитать количество коллизий. Есть входной массив: A[] = { 40, 12, 79, 35, 43, 52, 83, 66, 89, 79 }; Моя программа выводит, что в трех строках располагается больше, чем один элемент, то есть 3 коллизии? (А то и 4, если считать количество всех "лишних" элементов), но в результирующих файлах - примерах, для хэш-таблицы цепочкой с хэш-функциями по методу деления и методу умножения указано, что их (коллизий) - 0. Не подскажите как вообще тогда считать коллизии, если в данном случае их получается ноль? Я думал, что достаточно посчитать количество строк, где dataQuantity > 1...?
0
|
|
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
| 21.03.2015, 12:05 | |
|
А в примерах, видимо, в хеш-функцию запихали другие коэффициенты. Например, приняли ее за key%100500.
0
|
|
|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
|
| 21.03.2015, 12:08 [ТС] | |
|
Renji, 1) Но ведь если использовать хэш-функцию методом деления, то мы делаем key % N, где N - количество элементов, то есть в данном случае 10?. Просто дело в том, что задание будет проверяться именно по этим файлам. В других случаях есть файл с 1000 элементов, так там 150 коллизий указано.
2) Так все-таки, количеством коллизий будет количество "лишних" элементов или строк с "лишними"?
0
|
|
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
| 21.03.2015, 12:16 | |
|
1) Нет, N в данном случае размер хеш-таблицы. То есть, "сколько не жалко". Хотя, брать N меньше чем число элементов действительно не сильно хорошо, ибо гарантирует наличие коллизий.
2) Как я понимаю, количество лишних элементов.
0
|
|
|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
|
| 21.03.2015, 15:52 [ТС] | |
|
Renji, ах вот оно что. Вот зачем написали, что размер таблицы не должен превышать тройного размера массива. Все равно одна коллизия остается, ну ничего, буду разбираться, большое Вам спасибо.
Добавлено через 3 часа 27 минут Renji, извините, что еще беспокою. Как я понял количество коллизий зависит от размера таблицы. В моем исходном массиве есть два повторяющихся числа - 79. Я подобрал размер так, чтобы коллизий не было, но эти одинаковые числа естественно лезут в одну ячейку, а тот файл, с которым мне нужно сравнить результат, говорит, что коллизий должно быть - 0. Реально ли как-то разрешить эту проблему для одинаковых чисел, чтобы не было коллизий? Так же для меня допускается погрешность в коллизиях в 2 раза, но для нуля она вряд ли применима наверное...
0
|
|
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
| 21.03.2015, 16:14 | |
|
А это вам уже авторов задачи спрашивать надо. Тут есть две стратегии - или дубли отбрасываются (логика unordered_map), или хранятся все вместе (unordered_multimap). И что там подразумевал автор задачи - ХЗ.
0
|
|
|
3 / 3 / 5
Регистрация: 18.11.2013
Сообщений: 118
|
|||||||||||
| 21.03.2015, 20:07 [ТС] | |||||||||||
|
Renji, я понял. Решил удалять.
Можете еще сюда взглянуть, я теперь добавил хэш - функцию по методу умножения и в функции поиска (строка 131) получаю ошибку:
0
|
|||||||||||
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
| 21.03.2015, 20:31 | |
|
Выход за границы массива Nodes. Включайте отладчик и в пошаговом режиме разбирайтесь чего там getHashByMultiplication вернуло и каких размеров на тот момент был массив.
1
|
|
| 21.03.2015, 20:31 | |
|
Помогаю со студенческими работами здесь
20
Описать класс "хэш-таблица", используя unordered_set и заданную хэш-функцию Хеш-таблица (метод цепочек) Хеш таблица с функцией (метод цепочек) Хэш-таблица Хэш таблица Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 01.02.2026
Содержание блога
Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
|
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
|
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 31.01.2026
Содержание блога
В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
|
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога
Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
|
|
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога
Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
|
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
|
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования.
Часть библиотеки BedvitCOM
Использованы. . .
|
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога
SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
|