29364

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

Доклад

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

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

Английский

2013-08-21

51.5 KB

0 чел.

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

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

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


 

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

49604. Усилитель звуковой частоты на биполярных транзисторах отечественного производства 667.5 KB
  Выбор обоснование и расчет структурной схемы усилителя. Расчет АЧХ усилителя. На их основе можно сконструировать отдельные каскады и структурные блоки усилителя мощности. Выбор того или иного варианта реализации усилителя зависит от поставленной перед инженером задачи простоты исполнения и экономических соображений.
49606. ПРОЕКТИРОВАНИЕ АНАЛОГО-ЦИФРОВОГО ПРЕОБРАЗОВАТЕЛЯ С USB - ВЫХОДОМ 1.03 MB
  ПРОЕКТИРОВАНИЕ АНАЛОГОЦИФРОВОГО ПРЕОБРАЗОВАТЕЛЯ С USB ВЫХОДОМ Пояснительная записка к курсовому проекту по дисциплине Схемотехника ЭВМ ИНМВ. Омск 2013 Задание Проектирование аналогоцифрового преобразователя с USB выходом. Объектом исследования является аналогоцифровой преобразователь с USB выходом. Цель работы – разработать функциональную и принципиальную схему АЦП рассчитать входные усилители и фильтры нижних частот выбрать микросхему АЦП выбрать тип конвертора USB рассчитать и выбрать преобразователи DCDC и микросхемы...
49609. Расчёт токов короткого замыкания для оценки параметров основного оборудования подстанций сети. Выявление необходимости реактирования линий 10 кВ, отходящих от подстанций 4.99 MB
  В первой части расчетнопояснительной записки представлены обоснование и выбор вариантов схем электрической сети произведен выбор основных параметров схем сравнение техникоэкономических показателей схем и определение наилучшего варианта. Вторая часть содержит теоретические выкладки и пример практического расчета по теме: Расчёт токов короткого замыкания для оценки параметров основного оборудования подстанций сети. ФОРМИРОВАНИЕ ВАРИАНТОВ СХЕМ СЕТИ. ВЫБОР НОМИНАЛЬНОГО НАПРЯЖЕНИЯ СЕТИ.
49610. Расчет защиты зерноочистительного комплекса 1.82 MB
  Чтобы обеспечить бесперебойную и качественную работу необходимо применять защиту для электродвигателей. Для этого существует множество аппаратов, которые способны обеспечить защиту, как по току, так и по напряжению.
49611. Усилитель мощности звуковой частоты при усилении низких частот звукового тракта 572 KB
  Вследствие корреляции между величинами R и β в едином технологическом цикле при проектировании усилителя следует учитывать два предельных случая: компоненты схемы имеют значения Rмин и βмин или Rмакс и βмакс величина относительного разброса для конкретного технологического цикла известна разработчику заранее. Для разработки данного усилителя мощности следует произвести предварительный расчёт и оценить количество и тип основных элементов. При проектировании усилителя следует использовать такие элементы чтобы их параметры...