Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/11: Рейтинг темы: голосов - 11, средняя оценка - 5.00
26 / 26 / 9
Регистрация: 22.09.2012
Сообщений: 116
1

Хэш-таблица для быстрого поиска строки в массиве

15.09.2014, 19:35. Просмотров 2281. Ответов 3
Метки нет (Все метки)

Объясните, пожалуйста, как реализуется хэш-таблица. Например, есть двухмерный массив строк с большим количеством записей [key -> value] (строки состоят только из латинских символов и цифр). Необходимо по входной строке [key] выдать значение [value].
Нужно выбрать хэш-функцию, которая распределит значения возможных входных данных по массиву. Есть пример подобной функции, который можно использовать для моего случая? И тогда какого размера выбирается массив (хэш таблица), ведь значение хэш-функции может быть большим (если мне нужно обеспечить уникальность каждого возможного входного значения). Или допускаются повторения? тогда каждому хэш-значению будет соответствовать массив с соответствующими [key], который нужно дополнительно проверять.
В общем, объясните нубу
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.09.2014, 19:35
Ответы с готовыми решениями:

Отсортированный хэш-вектор бинарной схожести для быстрого поиска
Есть набор 64-х разрядных чисел, их может быть примерно 20 000 ... 40 000. Нужна какая-то хеш...

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

Список для максимально быстрого поиска по нему
Сейчас у меня есть два списка строк - List<string> один MainBase, второй TempBase, мне надо выбрать...

Оптимизировать структуру таблицы для быстрого поиска
Здравствуйте. Имеется таблица контактов компаний с огромным количеством данных. Сами контакты...

3
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
15.09.2014, 22:00 2
Цитата Сообщение от WhooogyMan Посмотреть сообщение
двухмерный массив
Одномерный. Ключ - это индекс элемента в массиве.

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

Или допускаются повторения?
Выбор за вами. Если весь набор ключей известен заранее, Perfect hash, обычно, лучшее решение. В противном случае, таблицу желательно брать с запасом, коллизии обрабатываются отдельно.

Тема обширная, начните с Hash Tables
1
26 / 26 / 9
Регистрация: 22.09.2012
Сообщений: 116
15.09.2014, 22:12  [ТС] 3
Цитата Сообщение от gazlan Посмотреть сообщение
Сообщение от WhooogyMan
двухмерный массив
ну вот, снова. Я честно не знаю, как правильно пишется, хотя недавно спорил о том же.
http://ru.wiktionary.org/wiki/... 1%8B%D0%B9 - здесь посмотрите синонимы.
http://orf.textologia.ru/defin... 32&n=28224 - здесь
хотя на запрос "двумерный" гугл находит на 200000 страниц больше
По теме - спасибо. Главное прояснил. Была трудность с осознанием, что все ключи будут меньше ВЫБРАННОГО размера хэш-таблицы. Разобрался
0
1229 / 596 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
16.09.2014, 08:53 4
Цитата Сообщение от WhooogyMan Посмотреть сообщение
И тогда какого размера выбирается массив (хэш таблица), ведь значение хэш-функции может быть большим (если мне нужно обеспечить уникальность каждого возможного входного значения). Или допускаются повторения? тогда каждому хэш-значению будет соответствовать массив с соответствующими [key], который нужно дополнительно проверять.
Значение хеш-ключа делится на размер хеша, остаток от деления есть индекс "корзины" (bin). Хеш-ключ НЕ уникальный, корзина может содержать любое кол-во пар ключ-значение с одинаковым хеш-ключом (так называемые "коллизии"). Поэтому когда попали в корзину - ищем перебором (часто по списку). Если надо супер-пупер - ставят еще хеш на корзину. Ну это редко
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.09.2014, 08:53

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Описать класс "хэш-таблица", используя unordered_set и заданную хэш-функцию
Здравствуйте. Есть класс объектов и ключ сравнения: #pragma once #include <iostream> #include...

Разработка приложения для более быстрого, индексированного поиска файлов по заданному имени (хэширование)
Задача: разработать приложение для более быстрого, индексированного поиска файлов по заданному...

Создать программу для поиска первого нечетного элемента в заданном массиве методом бинарного поиска
Бинарный поиск Первый нечетный, помогите пожалуйста.

Хэш таблица
Как работает метод цепочек, для разрешения коллизий в хэш таблице?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.