В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 5
Текст из файла (страница 5)
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год173.4.Шаг перемешивания обратимПри перемешивании каждый бит внутреннего состояния влияет на каждыйбит результата5.При перемешивании каждый бит внутреннего состояния влияет не меньше чемна log 2 p битов внутреннего состояния.6.For every intermediate point in the mixing step, consider running the mixing stepforward to that point from the previous combine, and backward to that point from thenext combine. For every set Y of bits in the internal state in the middle, there some setX of bits in the previous input block and Z in the next input block that affect those Ybits.
For every Y with less than v bits, |X|+|Z| must be less than or equal to |Y|. (Notethat if every bit in the previous and next block affects at least v bits in the center of themixing step, this requirement is satisfied.)7.(The postprocessing step just selects v bits of the internal state to be the v-bit result)Примеры «хороших» хэш-функций (на входе – m-байтная последовательность, навыходе – 32-битное значение):Rotate hash:int rotating( char *key, int len, int prime){int hash, i;for (hash=len, i=0; i<len; ++i)hash = (hash<<5)^(hash>>27)^key[i];return (hash % prime);}//здесь prime – простое числоболее сложные хэши:CRC hash:int crc( char *key, int len, int mask, int tab[256]){int hash, i;for (hash=len, i=0; i<len; ++i)hash = (hash<<8)^tab[(hash>>24)^key[i]];return (hash & mask);}Pearson hash:char pearson( char *key, int len, char tab[256]){char hash;int i,len;for (i=0, hash=0; i<len; ++i)hash=tab[hash^key[i]];return (hash);}CRC hash требует для своей работы еще специальную табличку из 256 элементов,поначалу инициализированную так, чтобы младшие 8 битов в записанных в нее числахявлялись бы перестановкой; mask – некоторое произвольное число.Pearson hash тоже требует для работы табличку из 256 элементов – всех возможных256 char.Все эти три хэш-функции не обладают свойством воронки.1.5.
Контейнеры.Часто требуется хранить данные заранее неизвестного размера, а не какого-тофиксированного и заранее известного (что предполагалось во всех описанных вышеструктурах). Для выхода из этой ситуации собственно и был введен механизм ключей,упоминавшихся выше – мы «кладем» наши данные куда-то, получаем на них «ключ» некоторое число, которое уже удобно использовать, поскольку оно уже имеетфиксированную длину. В частности, все описывавшиеся выше структуры оперируютЛекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год18именно с ключами, а во все развитые языки программирования изначально введенуниверсальный контейнер в лице функций динамического распределения памяти,аналогичных malloc и free, которые позволяют сохранить произвольные данные в памяти,получив на них ключ в виде указателя.Будем в дальнейшем рассматривать только ситуацию, когда наш объект можно«упаковать» в некоторый непрерывный кусок памяти некоторой длины.
Все другие случаиможно свести к этому, наиболее широко используемому (например, дерево или списокбудут записаны в виде множества небольших непрерывных кусочков памяти)Рассмотрим для начала простейшую реализацию контейнера без операции удаленияэлемента, только с операцией добавления.
В нашем распоряжении изначально имеетсянекоторая память (не важно, оперативная ли, место на диске или еще что-то), логическиорганизованная в виде длинного непрерывного массива, изначально пустая. В случае среализацией контейнера на C это означает, что при создании контейнера ему выделяетсяпустой кусок памяти длины N. Заведем указатель p на начало свободной памяти –изначально он будет совпадать с началом доступной памяти.
Теперь при необходимостидобавить в контейнер блок длины m запишем этот блок начиная с того места, котороеотмечен у нас, как первое свободное, передвинем указатель на первое свободное место на mпозиций дальше, сохраним где-нибудь информацию о добавленном блоке (длину блока и егоначало, чтобы впоследствии можно было удалить блок по его ключу), а в качестве ключавернем указатель на начало добавленного блока. Например, после добавления элементов A,B, C длины 2, 3, 4 в контейнер максимальной длины 11 получится примерно следующаяструктура:01A23B45678910Cp(цифрами указан номер ячейки памяти)На элемент A будет выдан ключ 0, на B – ключ 2, на C – ключ 5 и т.д.
(например, наследующий добавленный элемент контейнер выдаст ключ 9).Очевидно, что мы таким образом сможем эффективно хранить в контейнере данныепроизвольного размера и легко производить к ним соответствующие обращения. Легкотакже видеть, что фактически мы реализовали «обобщенный стек», с элементами разнойдлины. Проблемы возникают при необходимости удалить элемент из стека.
Например, Cудалить легко, а вот B или A – уже не получится. Конечно, можно при удалении элементапросто очищать соответствующие ячейки памяти и в дальнейшем их не использовать – этоснимает проблему, но лишь частично, потому что если нам часто приходится добавлять иудалять в контейнер элементы, то доступный участок памяти быстро исчерпается, послечего в контейнер ничего нельзя будет добавить. Тем не менее, разрешима и эта проблема. ВC, в частности, уже есть такие функции – malloc и free. Расскажем о общих принципах ихфункционирования.Будем хранить информацию о свободных и занятых блоках данных в виде списка,показывающего свободные и занятые куски.
Изначально в списке всего один кусок – всядоступная память, по мере добавления элементов в списке будут появляться все новыеэлементы. Действительно, при добавлении элемента запишем в список выделенный под негокусок памяти, а из свободного блока, откуда мы взяли память – «откусим»соответствующую часть. Например, для описанной выше ситуации с добавлением 3хэлементов получим списокЛекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год1901A23B45678910Cиз 4х записей:1.
Занятый блок, начало в 0, длина 22. Занятый блок, начало в 2, длина 33. Занятый блок, начало в 5, длина 44. Свободный блок, начало в 9, длина 2При удалении блока мы очищаем нужную область в памяти и указываем, чтосоответствующий кусок памяти свободен. Например, после удаления элемента B списокзапишется1. Занятый блок, начало в 0, длина 22. Свободный блок, начало в 2, длина 33. Занятый блок, начало в 5, длина 44. Свободный блок, начало в 9, длина 2В процессе удаления у нас может получиться, что получится от 1 до 3х кусковсвободного места, лежащих друг рядом с другом.
В это случае объединяем их в цельныйкусок памяти. Например, после удаления еще и A получим1. Свободный блок, начало в 0, длина 52. Занятый блок, начало в 5, длина 43. Свободный блок, начало в 9, длина 2При добавлении элемента мы вначале находим наиболее подходящий кусок памяти,откуда можно выделить достаточно памяти, чтобы элемент в ней целиком уместился.
Затеммы просто выдаем под объект память из начала свободного блока и возвращаем указатель нанее в качестве ключа, параллельно обновляя список. Если куска нужной длины нет, топоделать ничего нельзя – даже если у нас достаточно памяти, чтобы разместить и новыйдобавляемый объект, то в контейнер его уже не добавишь. Таким образом встает проблема«обрезков» памяти, разместить в которых ничего подходящего не удается.Поэтому встает вопрос – как выбирать этот наиболее подходящий кусок памяти, чтобыминимизировать «обрезки»? Для этого существуют различные стратегии.
В рамках одной –нужно выбирать самый длинный кусок памяти из возможных, из соображений, что если«отрезать» от длинного куска памяти, то остаток будет еще достаточно большим, чтобывместить в себя еще какие-то блоки данных и не превратится в «обрезок».
Другая стратегия,наоборот, предусматривает выбор отрезка наименьшей длины – из расчета, чтополучающийся «обрезок» будет минимального размера. К сожалению, в обоих случаяхлегко придумать ситуацию, в которой стратегия будет работать «плохо». Более общо,обычно получается, что использование любой стратегии ничем не лучше, чем стратегияслучайного выбора, когда мы берем первый подходящий свободный блок.Последний не разобранный вопрос – где хранить все те данные, что поддерживаютработоспособность самого контейнера? Здесь также существует 2 возможных подхода.Первый состоит в том, чтобы хранить данные контейнера в специальной служебной областипамяти, расположенной до или после области, в которую мы будем складывать данные,закладываемые в контейнер. Этот способ плох тем, что место в контейнере может еще незакончиться, когда закончится место в служебной области памяти – в этом случае, несмотряна принципиальную возможность добавить в контейнер еще один элемент, сделать это вданной реализации будет невозможно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
