29364

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

Доклад

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

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

Английский

2013-08-21

51.5 KB

0 чел.

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

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

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


 

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

26006. СМО с бесконечной очередью и частичной взаимопомощью для произвольных потоков. Граф, система уравнений, расчетные соотношения 35.06 KB
  Эта система в строгом смысле является саморегулируемой. Подходящей моделью для описания такой системы является процесс размножения и гибели при следующем выборе параметров: Система является эргодической.
26007. СМО с бесконечной очередью и полной взаимопомощью для пуассоновских потоков. Граф, система уравнений, расчетные соотношения 32.91 KB
  Каждое вновь поступившее требование подается на свой отдельный обслуживающий прибор однако если требование поступает в момент когда все приборы заняты то оно теряется.
26008. СМО с бесконечной очередью и полной взаимопомощью для произвольных потоков. Граф, система уравнений, расчетные соотношения 46.78 KB
  Такая модель задается следующим образом: Эта система является эргодической. СМО типа М М ∞ М Для вероятностей pk этой системы из: Имеем: Где биноминальные коэффициенты определяются обычным образом: Определяя p0 получаем: И следовательно: Таким образом: Не составляеет труда вычислить среднее число требований в системе: Используя частную производную получаем:.
26009. СМО с конечной очередью для пуассоновских потоков. Граф, система уравнений, расчетные соотношения 76.36 KB
  Длина очереди m число мест в очереди. Если все места в очереди заняты то заявка получает отказ. Если при обслуживании освобождается канал то из очереди переходит очередная заявка на обслуживание; все заявки сдвигаются и вновь поступившая заявка ставится в конец очереди. вероятность того что заявке придется стоять в очереди вероятность очереди: 4.
26010. Понятие системного обслуживания. Классификация 39.96 KB
  Системой массового обслуживания СМО называется любая система для выполнения заявок поступающих в нее в случайные моменты времени. Оптимизация и оценка эффективности СМО состоит в нахождении средних суммарных затрат на обслуживание каждой заявки и нахождение средних суммарных потерь от заявок не обслуженных. Каналом обслуживания называется устройство в СМО обслуживающее заявку. СМО содержащее один канал обслуживания называется одноканальной а содержащее более одного канала обслуживания многоканальной.
26011. СМО с конечной очередью и частичной взаимопомощью для пуассоновских потоков. Граф, система уравнений, расчетные соотношения 37 KB
  Интенсивность обслуживания заявки каждым каналом равна а максимальное число мест в очереди равно m. Рисунок 1 Граф состояний многоканальной СМО с ограниченной очередью все каналы свободны очереди нет; заняты l каналов l = 1 n очереди нет; заняты все n каналов в очереди находится i заявок i = 1 m. Данная система является частным случаем системы рождения и гибели если в ней сделать следующие замены: В результате получим: Образование очереди происходит когда в момент поступления в СМО очередной заявки все каналы заняты т.
26012. СМО с конечной очередью и частичной взаимопомощью для произвольных потоков. Граф, система уравнений, расчетные соотношения 42.71 KB
  Предполагается, что имееется конечное число М требований, причем интенсивность поступления каждого требования равна λ. Кроме того, система содержит m обслуживающих приборов, каждый из которых описывается параметром µ. В системе имеется конечное чмсло мест для ожидания
26013. СМО с конечной очередью и полной взаимопомощью для пуассоновских потоков. Граф, система уравнений, расчетные соотношения 48.02 KB
  Граф система уравнений расчетные соотношения. В частности для такого описания будем перекрывать входящий пуассоновский поток на время когда система запоняется следующим образом: Эта система эргодична всегда.
26014. Понятие дисциплины обслуживания. Основные классы 14.6 KB
  Дисциплина ожидания определяет порядок приема заявок в систему и размещения их в очереди дисциплина обслуживания порядок выбора заявок из очереди для назначения на обслуживание. Возможны следующие бесприоритетные дисциплины обслуживания то есть правила выборки заявки из очереди при необходимости назначения на обслуживание: выбирается первая в очереди заявка дисциплина первым пришел первым вышел FIFO First Input First Output; выбирается последняя в очереди заявка дисциплина последним пришел первым...