Открытое хеширование

⇐ Предыдущая 1 2 3 456 Следующая ⇒

Основная идея базовой структуры при открытом (внешнем) хешировании заключается в том, что потенциальное множество (возможно, бесконечное) разбивается на конечное число классов. Для В классов, пронумерованных от 0 до В-1, строится хеш-функция h(x) такая, что для любого элемента х исходного множества функция h(x) принимает целочисленное значение из интервала 0,1,...,В-1, соответствующее, классу, которому принадлежит элемент х. Часто классы называют сегментами, поэтому будем говорить, что элемент хпринадлежит сегменту h(x). Массив, называемый таблицей сегментов и проиндексированный номерами сегментов 0,1,...,В-1, содержит заголовки для B списков. Элемент х, относящийся к i -му списку – это элемент исходного множества, для которого h(x)=i.

Если сегменты примерно одинаковы по размеру, то в этом случае списки всех сегментов должны быть наиболее короткими при данном числе сегментов. Если исходное множество состоит из N элементов, тогда средняя длина списков будет N/B элементов. Если можно оценить величину N и выбрать В как можно ближе к этой величине, то в каждом списке будет один или два элемента. Тогда время выполнения операторов словарей будет малой постоянной величиной, не зависящей от N.

Пример 1. Программная реализация открытого хеширования.

#include "stdafx.h"#include <iostream>#include <fstream>using namespace std; typedef int T; // тип элементовtypedef int hashTableIndex; // индекс в хеш-таблице#define compEQ(a,b) (a == b)typedef struct Node_ { T data;// данные, хранящиеся в вершине struct Node_ *next; // следующая вершина} Node; Node **hashTable;int hashTableSize;hashTableIndex myhash(T data);Node *insertNode(T data);void deleteNode(T data);Node *findNode (T data); int _tmain(int argc, _TCHAR* argv[]){ int i, *a, maxnum; cout << "Введите количество элементов maxnum: "; cin >> maxnum; cout << "Введите размер хеш-таблицы HashTableSize: "; cin >> hashTableSize; a = new int[maxnum]; hashTable = new Node*[hashTableSize]; for (i = 0; i < hashTableSize; i++) hashTable[i] = NULL; // генерация массива for (i = 0; i < maxnum; i++) a[i] = rand(); // заполнение хеш-таблицы элементами массива for (i = 0; i < maxnum; i++) { insertNode(a[i]); } // поиск элементов массива по хеш-таблице for (i = maxnum-1; i >= 0; i--) { findNode(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 << ": "; Node *Temp = hashTable[i]; while (Temp){ out << Temp->data << " -> "; Temp = Temp->next; } out << endl; } out.close(); // очистка хеш-таблицы for (i = maxnum-1; i >= 0; i--) { deleteNode(a[i]); } system("pause"); return 0;} // хеш-функция размещения вершиныhashTableIndex myhash(T data) { return (data % hashTableSize);} // функция поиска местоположения и вставки вершины в таблицуNode *insertNode(T data) { Node *p, *p0; hashTableIndex bucket; // вставка вершины в начало списка bucket = myhash(data); if ((p = new Node) == 0) { fprintf (stderr, "Нехватка памяти (insertNode)\n"); exit(1); } p0 = hashTable[bucket]; hashTable[bucket] = p; p->next = p0; p->data = data; return p;} //функция удаления вершины из таблицыvoid deleteNode(T data) { Node *p0, *p; hashTableIndex bucket; p0 = 0; bucket = myhash(data); p = hashTable[bucket]; while (p &&!compEQ(p->data, data)) { p0 = p; p = p->next; } if (!p) return; if (p0) p0->next = p->next; else hashTable[bucket] = p->next; free (p);} // функция поиска вершины со значением dataNode *findNode (T data) { Node *p; p = hashTable[myhash(data)]; while (p &&!compEQ(p->data, data)) p = p->next; return p;}

⇐ Предыдущая 1 2 3 456 Следующая ⇒

Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных