Typedef int hashTableIndex;// индекс в хеш-таблице

int hashTableSize;

T *hashTable;

bool *used;

hashTableIndex myhash(T data);

void insertData(T data);

void deleteData(T data);

bool findData (T data);

int dist (hashTableIndex a,hashTableIndex b);

int _tmain(int argc, _TCHAR* argv[]){

int i, *a, maxnum;

cout << "Введите количество элементов maxnum : ";

cin >> maxnum;

cout << "Введите размер хеш-таблицы hashTableSize : ";

cin >> hashTableSize;

a = new int[maxnum];

hashTable = new T[hashTableSize];

used = new bool[hashTableSize];

for (i = 0; i < hashTableSize; i++){

hashTable[i] = 0;

used[i] = false;

}

// генерация массива

for (i = 0; i < maxnum; i++)

a[i] = rand();

// заполнение хеш-таблицы элементами массива

for (i = 0; i < maxnum; i++)

insertData(a[i]);

// поиск элементов массива по хеш-таблице

for (i = maxnum-1; i >= 0; i--)

findData(a[i]);

// вывод элементов массива в файл List.txt

ofstream out("List.txt");

for (i = 0; i < maxnum; i++){

out << a[i];

if ( i < maxnum - 1 ) out << "\t";

}

out.close();

// сохранение хеш-таблицы в файл HashTable.txt

out.open("HashTable.txt");

for (i = 0; i < hashTableSize; i++){

out << i << " : " << used[i] << " : " << hashTable[i] << endl;

}

out.close();

// очистка хеш-таблицы

for (i = maxnum-1; i >= 0; i--) {

deleteData(a[i]);

}

system("pause");

return 0;

}

// хеш-функция размещения величины

hashTableIndex myhash(T data) {

return (data % hashTableSize);

}

// функция поиска местоположения и вставки величины в таблицу

void insertData(T data) {

hashTableIndex bucket;

bucket = myhash(data);

while ( used[bucket] && hashTable[bucket] != data)

bucket = (bucket + 1) % hashTableSize;

if ( !used[bucket] ) {

used[bucket] = true;

hashTable[bucket] = data;

}

}

// функция поиска величины, равной data

bool findData (T data) {

hashTableIndex bucket;

bucket = myhash(data);

while ( used[bucket] && hashTable[bucket] != data )

bucket = (bucket + 1) % hashTableSize;

return used[bucket] && hashTable[bucket] == data;

}

//функция удаления величины из таблицы

void deleteData(T data){

int bucket, gap;

bucket = myhash(data);

while ( used[bucket] && hashTable[bucket] != data )

bucket = (bucket + 1) % hashTableSize;

if ( used[bucket] && hashTable[bucket] == data ){

used[bucket] = false;

gap = bucket;

bucket = (bucket + 1) % hashTableSize;

while ( used[bucket] ){

if ( bucket == myhash(hashTable[bucket]) )

bucket = (bucket + 1) % hashTableSize;

else if ( dist(myhash(hashTable[bucket]),bucket) < dist(gap,bucket) )

bucket = (bucket + 1) % hashTableSize;

else {

used[gap] = true;

hashTable[gap] = hashTable[bucket];

used[bucket] = false;

gap = bucket;

bucket++;

}

}

}

}

// функция вычисления расстояние от a до b (по часовой стрелке, слева направо)

int dist (hashTableIndex a,hashTableIndex b){

return (b - a + hashTableSize) % hashTableSize;

}

12.

Существует несколько типов функций хеширования, каждая из которых имеет свои преимущества и недостатки и основана на представлении данных. Приведем обзор и анализ некоторых наиболее простых из применяемых на практике хеш-функций.

Таблица прямого доступа

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

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

В целях экономии памяти можно назначать размер пространства записей равным размеру фактического множества записей или превосходящим его незначительно. В этом случае необходимо иметь некоторую функцию, обеспечивающую отображение точки из пространства ключей в точку в пространстве записей, то есть, преобразование ключа в адрес записи: a=h(k), где a – адрес, k– ключ.

Идеальной хеш-функцией является инъективная функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса.

Дата добавления: 2015-07-26; просмотров: 160; Нарушение авторских прав

Мы поможем в написании ваших работ!