АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Понятие хеширования

Читайте также:
  1. I. Понятие и значение охраны труда
  2. I. Понятие общества.
  3. II. ОСНОВНОЕ ПОНЯТИЕ ИНФОРМАТИКИ – ИНФОРМАЦИЯ
  4. II. Понятие социального действования
  5. Авторское право: понятие, объекты и субъекты
  6. Активные операции коммерческих банков: понятие, значение, характеристика видов
  7. Акты официального толкования: понятие и виды
  8. Акты применения права: понятие, признаки, виды
  9. Анализ различных критериев периодизации психического развития. Понятие ведущей деятельности
  10. Арбитражное соглашение - понятие, виды, применимое право.
  11. Аристотелево понятие метафизики
  12. Архитектурные стили, понятие, признаки, виды. Основные стили белорусской архитектуры.

Для решения задачи поиска необходимого элемента среди данных большого объема был предложен алгоритм хеширования (hashing – перемешивание), при котором создаются ключи, определяющие данные массива и на их основании данные записываются в таблицу, названную хеш-таблицей. Ключи для записи определяются при помощи функции i = h (key), называемой хеш-функцией. Алгоритм хеширования определяет положение искомого элемента в хеш-таблице по значению его ключа, полученного хеш-функцией.

Понятие хеширования– это разбиение общего (базового) набора уникальных ключей элементов данных на непересекающиеся наборы с определенным свойством.

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

Фактически хеширование – это специальный метод адресации данных для быстрого поиска нужной информации по ключам.

Если базовый набор содержит N элементов, то его можно разбить на 2 N различных подмножеств.

15.7.1. Хеш-таблица и хеш-функции

Функция, отображающая ключи элементов данных во множество целых чисел (индексы в таблице – хеш-таблица), называется функцией хеширования, или хеш-функцией:

i = h (key);

где key – преобразуемый ключ, i – получаемый индекс таблицы, т.е. ключ отображается во множество целых чисел (хеш-адреса), которые впоследствии используются для доступа к данным.

Однако хеш-функция для нескольких значений ключа может давать одинаковое значение позиции i в таблице. Ситуация, при которой два или более ключа получают один и тот же индекс (хеш-адрес), называется коллизией при хешировании.

Хорошей хеш-функцией считается такая функция, которая минимизирует коллизии и распределяет данные равномерно по всей таблице, а совершенной хеш-функцией – функция, которая не порождает коллизий:

Разрешить коллизии при хешировании можно двумя методами:

– методом открытой адресации с линейным опробыванием;

– методом цепочек.

Хеш-таблица

Хеш-таблица представляет собой обычный массив с необычной адресацией, задаваемой хеш-функцией.

Хеш-структуру считают обобщением массива, который обеспечивает быстрый прямой доступ к данным по индексу.

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)