29364

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

Доклад

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

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

Английский

2013-08-21

51.5 KB

0 чел.

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

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

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


 

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

7143. Электронная коммерция на примере интернет-магазина www.OZON.ru 307 KB
  Электронная коммерция на примере интернет-магазина www.OZON.ru Введение Начиная с середины 90-х годов, во всем мире наблюдается рост активности в области онлайновой торговли. Вслед за крупными компаниями, производящими компьютерное оборудование в Се...
7144. Финансирование строительства 183 KB
  ВВЕДЕНИЕ Кардинальная перестройка хозяйственного механизма основана на широком использовании товарно-денежных отношений, присущих рыночной экономике. Важнейшим экономическим инструментом товарно-денежных отношений служит кредит, который способствует...
7145. Исследование RC - автогенераторов для операционных усилителей с мостом Вина 1.76 MB
  Исследование RC - автогенераторов для операционных усилителей с мостом Вина Задание к курсовой работе: Задать номер варианта следующим образом: N=M M - две последние цифры номера зачетной книжки. Значение N определить по форму...
7146. Денежная масса и движение денег во внутреннем экономическом обороте страны 401.38 KB
  Введение Проблемами денег, организации денежного обращения человеческая мысль была занята больше, чем всеми остальными экономическими проблемами. С глубокой древности до наших дней вопросами теории денег занимались экономисты, философы, юристы. И се...
7147. Понятие первобытной культуры. Культура Средневековья и Возрождения 115.5 KB
  Лекция 3. Мировая культура. Часть 1 Шаяхметова А.М., Коровина С.В. А. Понятие первобытной культуры. Б. Культура Древних цивилизаций. В. Античная культура. Г. Культура Средневековья и Возрождения. Понятие первобытной культуры Первобытность - эт...
7148. Основное уравнение передачи по световоду 81 KB
  Основное уравнение передачи по световоду. Рассмотрим волоконный световод без потерь двухслойной конструкции, приведенный на рис...
7149. Построение принципиальной схемы 147 KB
  Построение принципиальной схемы Принципиальная схема строится с учетом помех, фильтров, по входу/выходу, с учётом нагрузок способности, для чего ставятся различные фильтры низких или высоких частот. В результате принципиальные схемы реализуют те же ...
7150. Особенности и периодизация культуры Нового времени. Личность и культура 70 KB
  А. Особенности и периодизация культуры Нового времени. Б. Культура ХХ века. В. Личность и культура. Роль интеллигенции в обеспечении духовного развития общества. Особенности и периодизация культуры Нового времени Специфические особенности рассматрив...
7151. Типы волн в световодах. Критические длины и частоты 76 KB
  Типы волн в световодах. Критические длины и частоты. В сетоводах могут существовать два типа волн: симметричные E0m , H0m несимметричные дипольные EHnm, HEnm. В индексе n - число изменений поля по диаметру m - число изменений поля по периметру. Сим...