- •1. АССОЦИАТИВНАЯ ПАМЯТЬ. ОПРЕДЕЛЕНИЯ И КОНЦЕПЦИИ
- •1.2. Определение и модель ассоциативной памяти
- •Непрямые (или косвенные) ассоциации
- •Отношение
- •1.3.4. Классические законы ассоциаций
- •Обобщая наблюдения над явлениями человеческой памяти, греческий философ Аристотель (384–322 гг. до н.э.) выдвинул ряд постулатов, впоследствии послуживших основой при построении классических законов ассоциаций [3].
- •2.1. Основные принципы хеширования
- •2.1.2. Функции хеширования
- •Перевод ключевых слов в числовую форму
- •Преобразование числовых значений в хеш-адреса
- •2.2.4. Методы ускорения процедур поиска
- •2.3. Структура и форматы таблиц хеширования
- •2.3.1. Непосредственная и косвенная адресация
- •2.3.2. Форматы таблиц хеширования
- •2.4.2. Списки и списочные структуры
- •2.4.5. Применение методов хеширования для поиска по соответствию
- •3.1.2. Логические основы организации АЗУ
- •Таблица 3.1
- •параллельного действия
- •3.2.2. Анализатор многократных совпадений
- •Приоритетные анализаторы последовательного типа
- •Структурная схема АЗУ с поиском, параллельным по словам и разрядам, приведена на рис. 3.8.
- •Построение АЗУ на базе ЗУ с линейной выборкой
- •Процедура записи в память разрядного столбца
- •Считывание разрядного столбца
- •3.6. АЗУ, параллельные по записям и последовательные по байтам
- •3.8. Схемотехническая база АЗУ
- •4. МЕСТО АССОЦИАТИВНОЙ ПАМЯТИ
- •4.2. Программируемая логика
- •4.2.2. Программирование логики при помощи ассоциативной памяти
- •функциональной памяти
- •4.2.4. Другие способы реализации программируемой логики
- •4.3. Применение АЗУ для выполнения различных
- •управляющих функций
- •5. АССОЦИАТИВНЫЕ ПРОЦЕССОРЫ
- •5.1. Основные тенденции развития ассоциативной памяти
- •5.3. Ассоциативные процессоры с высоким уровнем параллелизма
- •5.4.1. Базовая структура матричного процессора
- •Рассмотрим связи между ячейками МП.
- •5.4.3. Ассоциативный управляющий переключатель
- •5.4.4. Ассоциативный матричный процессор RADCAP
- •5.4.5. Ассоциативный групповой процессор PEPE
- •5.5.1. Вычислительная система STARAN
- •Отличие этого уровня от предыдущих:
Из известных методов программного поиска хеширование является самым быстродействующим. Это особенно важно при работе с наборами данных большого размера. Высокое быстродействие обусловлено тем, что элементы данных запоминаются, а затем выбираются из ячеек памяти, адреса которых являются простыми арифметическими функциями содержимого соответст-
вующих ключевых слов. Вычисление подобных функций в современных ЭВМ занимает весьма малое время по сравнению с продолжительностью доступа к памяти.
Методы хеширования получили наиболее широкое распространение в системном программировании. В настоящее время практически все символьные таблицы ассемблеров и компиляторов строятся по принципу хеширования, поскольку эти таблицы очень часто и в произвольном порядке опрашиваются в процессе компиляции и выполнения программы.
Эффективно применение методов хеширования в управлении базами данных (УБД) в алгоритмах выполнения операций поиска по многим ключам, в системах с многоуровневой памятью, при поиске информации в базах данных по заданным идентификаторам или дескрипторам (поиск документов, публикаций и т.д.), а также при создании языков высокого уровня и при построении лингвистических структур [1, 4, 5].
2.1.2. Функции хеширования
При хешировании адрес памяти, по которому заносится элемент данных, олределяется содержимым ключевого слова (КлСл), присвоенного этому элементу. В качестве КлСл могут использоваться обычные имена или произвольные числовые коды. Длина КлСл выбирается произвольно, хотя в вычислениях участвуют обычно только несколько символов. В результате набор допустимых слов (т.е. пространство имен) может оказаться весьма обширным. Например, из шести букв алфавита можно составить 256 млн слов. Однако, как уже говорилось ранее, пространство имен (ПрИм) реально оказывается крайне малым, поэтому встает задача подобрать такую функцию преобразования пространства имен в пространство адресов (ПрАдр), у которой в области значений (совпадающей с адресным пространством) адреса распределялись бы более равномерно и с большей плотностью.
Формирование хеш-функции обычно проводится в два этапа:
26