Разработка контейнера для хранения данных с поддержкой операций добавления/удаления/получения записи/объединения и итератора к нему

Размещено на http://www.allbest.ru/

Содержание

1. Организация хеш-таблицы с открытой адресацией

2. Словесные алгоритмы основных функций

3. Тестовые примеры

4. Сравнение с хеш-таблицей из библиотеки Qt

5. Исходный код

1. Организация хеш-таблицы с открытой адресацией

Хеш-таблица с открытой адресацией представляет собой массив, в котором хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. При отсутствии свободных ячеек требуется выделить новый массив, больший, чем текущий, затем перенести в него элементы из текущего массива и произвести перехеширование.

Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность h0(x), h1(x), …, hn - 1(x), где x - ключ элемента, а hi(x) - произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него одним из приведённых ниже способов:

1) Линейное пробирование: ячейки хеш-таблицы последовательно просматриваются с некоторым фиксированным интервалом k между ячейками (обычно, k = 1), то есть i-й элемент последовательности проб - это ячейка с номером (hash(x) + ik) mod N. Для того чтобы все ячейки оказались просмотренными по одному разу, необходимо, чтобы k было взаимно-простым с размером хеш-таблицы.

2) Квадратичное пробирование: интервал между ячейками с каждым шагом увеличивается на константу. Если размер хеш-таблицы равен степени двойки (N = 2p), то одним из примеров последовательности, при которой каждый элемент будет просмотрен по одному разу, является hash(x) mod N, (hash(x) + 1) mod N, (hash(x) + 3) mod N, (hash(x) + 6) mod N, …

3) Двойное хеширование: интервал между ячейками фиксирован, как при линейном пробировании, но, в отличие от него, размер интервала вычисляется второй, вспомогательной хеш-функцией, а значит, может быть различным для разных ключей. Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв простое число в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до N - 1.

Алгоритм поиска просматривает ячейки хеш-таблицы в том же самом порядке, что и при вставке, до тех пор, пока не найдется либо элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).

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

2. Словесные алгоритмы основных функций

Алгоритм вставки элемента

1. Проверить, есть ли свободные ячейки, если нет - произвести выделение большего участка памяти, скопировать в него имеющиеся элементы и произвести перехеширование.

2. Вычислить предполагаемый индекс вставки как частное от деления хеша ключа на текущий размер выделенной таблицы.

3. Попытаться вставить элемент в полученную позицию. Если она занята (произошла коллизия), методом линейного пробирования пытаться вставить элемент в последующие ячейки. При достижении конца таблицы сбросить индекс в ноль и просмотреть аналогичным образом все индексы до начального (вычисленного в предыдущем пункте).

Алгоритм поиска элемента

1. Вычислить предполагаемый индекс вставки как частное от деления хеша ключа на текущий размер выделенной таблицы.

2. Пока не найден элемент с нужным ключом, просматривать все ячейки от начального индекса до конца таблицы, а затем от нуля до начального индекса.

3. Если ключа не найдено, или ячейка с нужным ключом помечена как удаленная - возвратить итератор на конец таблицы. Иначе возвратить итератор на найденную ячейку.

Алгоритм удаления элемента

1. Вычислить предполагаемый индекс вставки как частное от деления хеша ключа на текущий размер выделенной таблицы.

2. Пока не найден элемент с нужным ключом, просматривать все ячейки от начального индекса до конца таблицы, а затем от нуля до начального индекса.

3. Если ключ найден, пометить соответствующую ячейку как удаленную.

адресация алгоритм исходный код

3 Тестовые примеры

Ниже описаны тестовые примеры на последовательные операции добавить (ключ, значение), удалить (ключ) и найти (ключ).

Действия (добавление, удаление)	Содержимое контейнера
Начальное состояние	Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted]
добавить(1, 10);	Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 1, Value = 10
добавить(3, 24);	Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 3, Value = 24 Key = 1, Value = 10
добавить(3, 25);	Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 3, Value = 25 Key = 1, Value = 10
добавить(134, 234);	Key = 134, Value = 234 Key = 0, Value = 0 [deleted] Key = 0, Value = 0 [deleted] Key = 3, Value = 25 Key = 1, Value = 10
добавить(24, 3);	Key = 134, Value = 234 Key = 24, Value = 3 Key = 0, Value = 0 [deleted] Key = 3, Value = 25 Key = 1, Value = 10
удалить(134);	Key = 24, Value = 3 Key = 24, Value = 3 [deleted] Key = 0, Value = 0 [deleted] Key = 3, Value = 25 Key = 1, Value = 10
удалить(135413);	Key = 24, Value = 3 Key = 24, Value = 3 [deleted] Key = 0, Value = 0 [deleted] Key = 3, Value = 25 Key = 1, Value = 10

Поиск в полученном контейнере	Результат
найти(1);	10
найти(3);	25
найти(24);	3
найти(134);	NULL

4. Сравнение с хеш-таблицей из библиотеки Qt

В таблице ниже приведены результаты сравнения производительности написанной хеш-таблицы и хеш-таблицы из библиотеки Qt. Тестировались операции добавления, удаления и поиска на 1000, 10 000 и 100 000 элементах.

Операция	Реализация	1000 элементов	10 000 элементов	100 000 элементов
Добавление	Qt	0.001	0.033	0.315
	Эта	0.013	0.015	0.023
Удаление	Qt	0.005	0.193	4.467
	Эта	0.000	0.002	0.009
Поиск	Qt	0.000	0.001	0.002
	Эта	0.001	0.002	0.008

Результаты: при добавлении и удалении небольшого количества элементов данная реализация уступает в скорости реализации из библиотеки Qt, однако при большом количестве элементов ее скорость заметно больше; время поиска в данной реализации больше, чем в Qt, но все же имеет с ним один порядок.

5. Исходный код

#include <stdlib.h>

class HashProvider

{

public:

inline static unsigned int Hash(unsigned char key8)

{

unsigned int key = key8;

key += ~(key << 15);

key ^= (key >> 10);

key += (key << 3);

key ^= (key >> 6);

key += ~(key << 11);

key ^= (key >> 16);

return key;

}

inline static unsigned int Hash(unsigned short int key16)

{

unsigned int key = key16;

key += ~(key << 15);

key ^= (key >> 10);

key += (key << 3);

key ^= (key >> 6);

key += ~(key << 11);

key ^= (key >> 16);

return key;

}

inline static unsigned int Hash(unsigned int key)

{

key += ~(key << 15);

key ^= (key >> 10);

key += (key << 3);

key ^= (key >> 6);

key += ~(key << 11);

key ^= (key >> 16);

return key;

}

inline static unsigned int Hash(unsigned long long int key)

{

key += ~(key << 32);

key ^= (key >> 22);

key += ~(key << 13);

key ^= (key >> 8);

key += (key << 3);

key ^= (key >> 15);

key += ~(key << 27);

key ^= (key >> 31);

return static_cast<unsigned int>(key);

}

};

template <class KeyType, class ValueType> class HashTable

{

private:

/*

* Пара ключ-значение.

*/

class HashTablePair

{

public:

KeyType Key; // Ключ.

ValueType Value; // Значение.

bool Deleted;// Удалена ли пара из хеш-таблицы.

HashTablePair()

{

Key = KeyType();

Value = ValueType();

Deleted = true;

}

HashTablePair(const KeyType Key, const ValueType Value)

{

this->Key = Key;

this->Value = Value;

this->Deleted = false;

}

};

unsigned int BlockSize;// Размер выделяемого блока памяти.

unsigned int BlocksAllocated;// Количество выделенных блоков памяти.

unsigned int FreeCells;// Количество свободных ячеек для записи пар.

HashTablePair * Table;// Указатель на выделенный участок памяти.

static unsigned int Hash(const KeyType & Key)

{

switch (sizeof(Key))

{

case 1:

return HashProvider::Hash(static_cast<unsigned char>(Key));

case 2:

return HashProvider::Hash(static_cast<unsigned short int>(Key));

case 4:

return HashProvider::Hash(static_cast<unsigned int>(Key));

case 8:

return HashProvider::Hash(static_cast<unsigned long long int>(Key));

default:

return HashProvider::Hash(static_cast<unsigned int>(Key));

}

}

/*

* Вставка пары ключ-значение в таблицу, в которой должна существовать хотя бы одна свободная ячейка.

*/

static void InsertInner(const KeyType & Key, const ValueType & Value, HashTablePair * Table, unsigned int TableSize)

{

unsigned int StartIndex = Hash(Key) % TableSize;// Индекс = хеш / размер таблицы.

for (unsigned int i = StartIndex; i < TableSize; i++)

if (Table[i].Deleted || Table[i].Key == Key)

{

Table[i].Value = Value;

Table[i].Key = Key;

Table[i].Deleted = false;

return;

}

for (unsigned int i = 0; i < StartIndex; i++)

if (Table[i].Deleted || Table[i].Key == Key)

{

Table[i].Value = Value;

Table[i].Key = Key;

Table[i].Deleted = false;

return;

}

}

/*

* Выделение нового участка памяти.

*/

void Reallocate(int DeltaBlocksCount)

{

// Вычисление нового количества блоков, не менее одного.

unsigned int NewBlocksAllocated = BlocksAllocated + DeltaBlocksCount;

if (NewBlocksAllocated < 1)

NewBlocksAllocated = 1;

// Выделение нового участка памяти и запись в него пар из старого, если он существовал.

unsigned int NewFreeCells = BlockSize * NewBlocksAllocated;

HashTablePair * NewTable = new HashTablePair[NewFreeCells];

if (Table != NULL)

{

for (unsigned int i = 0; i < BlockSize * BlocksAllocated; i++)

if (!Table[i].Deleted)

{

InsertInner(Table[i].Key, Table[i].Value, NewTable, BlockSize * NewBlocksAllocated);

NewFreeCells--;

}

delete Table;

}

Table = NewTable;

BlocksAllocated = NewBlocksAllocated;

FreeCells = NewFreeCells;

}

public:

/*

* Прямой итератор.

*/

class Iterator

{

private:

friend class HashTable;

HashTable * Table;// Таблица, по которой перемещается итератор.

unsigned int Index;// Индекс в таблице.

/*

* Пропуск удаленных элементов проходом вперед.

*/

void SkipDeletedForward()

{

unsigned int Size = Table->BlockSize * Table->BlocksAllocated;

if (Index == Size)

return;

while (Index < Size && Table->Table[Index].Deleted)

Index++;

if (Table->Table[Index].Deleted)

Index = Size;

}

/*

* Пропуск удаленных элементов проходом назад.

*/

void SkipDeletedBackward()

{

unsigned int Size = Table->BlockSize * Table->BlocksAllocated;

if (Index == Size)

return;

while (Index != 0 && Table->Table[Index].Deleted)

Index--;

if (Table->Table[Index].Deleted)

Index = Size;

}

public:

Iterator()

{

Table = NULL;

Index = -1;

}

Iterator(HashTable & Table)

{

this->Table = &Table;

Index = 0;

SkipDeletedForward();

}

/*

* Получение ключа текущей позиции.

*/

KeyType Key()

{

unsigned int Size = Table->BlockSize * Table->BlocksAllocated;

if (Table == NULL || Index == Size)

return KeyType();

return Table->Table[Index].Key;

}

/*

* Получение значения текущей позиции.

*/

ValueType Value()

{

unsigned int Size = Table->BlockSize * Table->BlocksAllocated;

if (Table == NULL || Index == Size)

return ValueType();

return Table->Table[Index].Value;

}

Iterator & operator=(Iterator & Other)

{

Table = Other.Table;

Index = Other.Index;

return *this;

}

bool operator==(Iterator & Other)

{

return Table == Other.Table && Index == Other.Index;

}

bool operator!=(Iterator & Other)

{

return !(*this == Other);

}

/*

* Пре-инкремент.

*/

Iterator & operator++()

{

unsigned int Size = Table->BlockSize * Table->BlocksAllocated;

if (Index < Size)

Index++;

SkipDeletedForward();

return *this;

}

/*

* Пост-инкремент.

*/

Iterator operator++(int)

{

unsigned int Size = Table->BlockSize * Table->BlocksAllocated;

Iterator tmp = *this;

if (Index < Size)

Index++;

SkipDeletedForward();

return tmp;

}

/*

* Пре-декремент.

*/

Iterator & operator--()

{

unsigned int Size = Table->BlockSize * Table->BlocksAllocated;

if (Index > 0)

Index--;

else

Index = Size;

SkipDeletedBackward();

return *this;

}

/*

* Пост-декремент.

*/

Iterator operator--(int)

{

Iterator tmp = *this;

if (Index > 0)

Index--;

else

Index = Size;

SkipDeletedBackward();

return tmp;

}

};

HashTable()

{

HashTable(1024, 1);

}

HashTable(unsigned int BlockSize, unsigned int NumberOfBlocks)

{

this->BlockSize = BlockSize;

this->BlocksAllocated = 0;

this->FreeCells = 0;

this->Table = NULL;

Reallocate(NumberOfBlocks);

}

~HashTable()

{

if (Table != NULL)

delete Table;

}

/*

* Вставка пары ключ-значение.

*/

void Insert(const KeyType & Key, const ValueType & Value)

{

if (FreeCells == 0)

Reallocate(1);

InsertInner(Key, Value, Table, BlockSize * BlocksAllocated);

FreeCells--;

}

/*

* Поиск значения по ключу.

*/

Iterator Find(const KeyType & Key)

{

unsigned int Size = BlockSize * BlocksAllocated;

unsigned int StartIndex = Hash(Key) % Size;// Индекс = хеш / размер таблицы.

for (unsigned int i = StartIndex; i < Size; i++)

if (Table[i].Key == Key)

if (!Table[i].Deleted)

{

HashTable<KeyType, ValueType>::Iterator Result(*this);

Result.Index = i;

return Result;

}

else

return End();

for (unsigned int i = 0; i < StartIndex; i++)

if (Table[i].Key == Key)

if (!Table[i].Deleted)

{

HashTable<KeyType, ValueType>::Iterator Result(*this);

Result.Index = i;

return Result;

}

else

return End();

return End();

}

/*

* Удаление значения по ключу.

*/

void Remove(const KeyType Key)

{

unsigned int Size = BlockSize * BlocksAllocated;

unsigned int StartIndex = Hash(Key) % Size;// Индекс = хеш / размер таблицы.

unsigned int DeleteIndex = Size;

// Удаление элемента из таблицы.

for (unsigned int i = StartIndex; DeleteIndex == Size && i < Size; i++)

if (Table[i].Key == Key)

{

Table[i].Deleted = true;

DeleteIndex = i;

}

for (unsigned int i = 0; DeleteIndex == Size && i < StartIndex; i++)

if (Table[i].Key == Key)

{

Table[i].Deleted = true;

DeleteIndex = i;

}

// Сдвиг элементов с таким же хешем, как у удаляемого элемента.

if (DeleteIndex != Size)

{

FreeCells++;

unsigned int Index = DeleteIndex + 1;

if (Index >= Size)

Index = 0;

while (Index != DeleteIndex && !Table[Index].Deleted && Hash(Table[Index].Key) % Size == StartIndex)

{

unsigned int PrevIndex = Index - 1;

if (Index == 0)

PrevIndex = Size - 1;

Table[PrevIndex].Key = Table[Index].Key;

Table[PrevIndex].Value = Table[Index].Value;

Table[PrevIndex].Deleted = false;

Table[Index].Deleted = true;

Index++;

if (Index == Size)

Index = 0;

}

}

}

Iterator Begin()

{

return HashTable<KeyType, ValueType>::Iterator(*this);

}

Iterator End()

{

HashTable<KeyType, ValueType>::Iterator Result(*this);

Result.Index = BlockSize * BlocksAllocated;

return Result;

};

Размещено на Allbest.ru