29364

Хеш – адресация в информационных таблицах

Доклад

Информатика, кибернетика и программирование

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

Английский

2013-08-21

51.5 KB

0 чел.

32) Хеш – адресация в информационных таблицах.

В основе организации таблиц с хеш-адресацией лежит процедура хешированияХеширование – преобразование символьного имени идентификатора в числовой индекс элемента таблицы с помощью простых арифметических и логических операций.
Конкретный способ хеширования задает 
хеш-функция., аргументом которой является символьная величина, т.е. имя идентификатора, а значение – числовой индекс элемента таблицы.
Простейший вариант 
таблицы с хеш-адресацией может служить использованием кода внутреннего представления 1-го символа имени. В этом случае: ABD-01000001ый соответствует предствавлению символа – «А»
Схематично такой способ адресации можно представить след-м образом:

С помощью 
хеш-функции каждое имя само указывает свое место в таблице. До тех пор, пока для двух различных имен результаты хеширования отличаются, время поиска элемента в таблице равно времени вычисления хеш-функции.
Хеш-функция задает отображение множества имен на множество индексов элементов таблицы и в идеале должна давать различные значения для двух любых отличающихся имен. Но это невозможно, т.к. любой язык допускает бесконечное количество имен, а объем таблицы ограничен. Т.о. всегда возможен конфликт при попытке записи двух отличающихся имен в одну ячейку таблицы. Такой конфликт называется коллизией и возникает, когда для отличающихся имен значения хеш-функциисовпадают. Коллизии можно разрешить 2 методами: 
- рехеширование и 
- методом цепочек.
Т.о. результат 
хеширования имени, записанного в таблицу, определяет начальный индекс, начиная с которого в таблице производится поиск этого имени.


 

А также другие работы, которые могут Вас заинтересовать

6702. Гельминтология. Характерные признаки типа Плоские черви - Plathelmintes 26.13 KB
  Гельминтология. Введение в гельминтологию. Характерные признаки типа Плоские черви - Plathelmintes. Класс Сосальщики - Trematoda. Класс Ленточные черви - Cestoda. Характеристика типа Круглые черви Гельминтология...
6703. Членистоногие (Arthopoda). Класс паукообразные 26.06 KB
  Тип Членистоногие (Arthopoda) Общая характеристика. Класс паукообразные. Членистоногие - самый многочисленный тип. Характерные признаки: двусторонняя симметрия трехслойная организация гетерономная метамерия...
6704. Членистоногие. Тип Членистоногие. Подтип Трахейнодышащие. Класс Насекомые 25.32 KB
  Тип Членистоногие. Подтип Трахейнодышащие. Класс Насекомые. Насекомые произошли от 1 из групп многоножек перешедших к жизни на земле. Организация усложнялась, появлялись приспособления к наземному образу жизни. Насекомых очень много и они распростра...
6705. Человек и биосфера. Человечество как активный элемент биосферы. Ноосфера 29.05 KB
  Человек и биосфера. Биосфера как историческая система. Современные концепции. Организация биосферы - живое вещество, количественная и качественная характеристика биосферы. Эволюция биосферы. Человечество как активный эл...
6706. Биологические ритмы и их закономерности. Хронобиология 26.93 KB
  Биологические ритмы и их закономерности. Хронобиология. С понятием ритм связана организация живой материи. Ритмос - соразмерность. 1751- часы цветов Карла Линнея. В настоящее время все ученые знают, что одно из фундаментальных свойств организмов...
6707. Экология как наука. Введение в экологию человека 30.25 KB
  Экология как наука. Введение в экологию человека. Определение и строение экологии. Среда как экологическое понятие. Факторы среды. Особенности экологии человека. Охрана природы. Рациональное природопользование. Основные...
6708. Система оценки рифм. Качество рифмы и словоблудие 18.82 KB
  Система оценки рифм Из истории развития рифмы Рифмой, как мы ранее определили, является созвучие в некоторой заранее определённой позиции, как правило, в конце строк. Однако не всегда она была такой выраженной, как сейчас. До того, как в Россию приш...
6709. Хорошая рифма, плохая рифма или Система оценки рифм 21.39 KB
  Хорошая рифма, плохая рифма или Система оценки рифм Сейчас часто можно услышать от людей, сведущих в поэзии: хорошая рифма, плохая рифма. Они вполне могут объяснить, почему они считают тот или иной рифменный ряд плохим ил...
6710. Понятие, классификация и особенности инструментов государственного регулирования внешнеторговой деятельности 21.7 KB
  Понятие, классификация и особенности инструментов государственного регулирования внешнеторговой деятельности. Одним из основополагающих элементом государственной экономической политики в современной экономике, является торговая политика, то есть пол...