ТОР 5 статей:
Методические подходы к анализу финансового состояния предприятия
Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века
Характеристика шлифовальных кругов и ее маркировка
Служебные части речи. Предлог. Союз. Частицы
КАТЕГОРИИ:
- Археология
- Архитектура
- Астрономия
- Аудит
- Биология
- Ботаника
- Бухгалтерский учёт
- Войное дело
- Генетика
- География
- Геология
- Дизайн
- Искусство
- История
- Кино
- Кулинария
- Культура
- Литература
- Математика
- Медицина
- Металлургия
- Мифология
- Музыка
- Психология
- Религия
- Спорт
- Строительство
- Техника
- Транспорт
- Туризм
- Усадьба
- Физика
- Фотография
- Химия
- Экология
- Электричество
- Электроника
- Энергетика
АСОЦИАТИВНЫЕ МАССИВЫ И ХЭШИ
Массивы, в которых для обращения к элементам используются ключи, логически связанные со значениями, называют ассоциативными массивами.
Хэш-функции
Основным требованиям к хорошей хэш-функции является наиболее равномерное из возможных распределение ключей по диапазону значений индексов. Кроме выполнения этого требования, распределение не связано никакой схемой, и даже желательно, чтобы оно производило впечатление совершенно случайного.
Предположим, что имеется функция ord(k), которая определяет порядковый номер ключа k во множестве всех возможных значений ключей. Предположим также, что индексы массива занимают интервал целых чисел 0... N— 1, где N — размер массива. Тогда очевидно, что нужно выбрать следующую функцию: Н (k) = ord(k) mod N.Для нее характерно равномерное распределение ключей на всем интервале индексов, поэтому она служит основой большинства преобразований ключей. Кроме того, она очень эффективно вычисляется при N, равном степени двойки. Но как раз этого случая следует избегать, если ключи являются последовательностями букв: предположение, что все ключи равновероятны, в этом случае совершенно ошибочно, в результате слова, различающиеся лишь несколькими символами, будут с большой вероятностью отображаться в одинаковые индексы, что приведет к чрезвычайно неравномерному распределению. Ситуация, когда в указанном месте нет элемента с заданным ключом, называется конфликтом. Задача формирования альтернативного индекса – решение конфликта.Если обнаруживается, что строка таблицы, соответствующая заданному ключу, не содержит желаемого элемента, то произошел конфликт, т. е. два элемента имеют такие ключи, которые отображаются в один и тот же индекс. В этом случае нужно сформировать еще один индекс. Существует несколько методов формирования вторичного индекса (разрешения конфликтов):
1) Прямое связывание – связывание в линейный список всех строк с идентичным первичным индексом H(k). Но тогда необходимо следить за вторичными списками и в каждой строке отводить место для ссылки (или индекса) на соответствующий список конфликтных элементов.
2) Открытая адресация – нужно просматривать другие строки этой же таблицы до тех пор, пока не найдется желаемый элемент или пустая строка (тогда считаем, что ключа в таблице нет).
В этом случае алгоритм просмотра будет выглядеть следующим образом:
h=H(k); i=0;do{ if (T[h] == k) { элемент найден; } else if T[h] = свободно { элемента нет в таблице; } else // конфликт i=i+l, h=H(k) + G(i); // G(i)- функция разрешения конфликтов}while (! Найден || нет в таблице || таблица полна) Выбор G(i):1) Линейные пробы
Недостаток – строки имеют тенденцию группироваться вокруг первичных ключей, т. е. тех, для которых при включении конфликта не возникало.2) Квадратичные пробы 
Недостаток – при поиске пробуются не все строки таблицы. Анализ метода: Будем полагать, что все допустимые ключи равновероятны, и функция расстановки равномерно отображает их на весь диапазон индексов таблицы.
Пусть в таблице размера n уже содержится k элементов.
Среднее число попыток при включении (k+1) элемента
Теперь можно вычислить среднее число попыток, необходимых для доступа к таблице к некоторому случайному ключу. Пусть n – размер таблицы, m – число ключей, фактически помещенных в таблицу. Тогда:
где 
– гармоническая функция; g – эйлерова константа.
Если подставить 
– коэффициент заполнения (приблизительно соответствует отношению занятой памяти по всей имеющейся), то
Среднее число попыток в зависимости от коэффициента заполнения:
| a | E |
| 0,1 | 1,05 |
| 0,25 | 1,15 |
| 0,5 | 1,39 |
| 0,75 | 1,85 |
| 0,9 | 2,56 |
| 0,95 | 3,15 |
| 0,99 | 4,66 |
Реальные методы разрешения конфликтов дают несколько худшую производительность.
Недостатки: фиксированный размер таблиц и невозможность настройки на реальные требования, изъятие сроки из расстановочной таблицы – трудоемкая операция. Поэтому, когда объемы данных неизвестны и сильно варьируются, то лучше будет организация памяти в виде деревьев.
Не нашли, что искали? Воспользуйтесь поиском: