В современном мире информационные технологии, окружающие нас повсюду, выполняют в автоматическом режиме операции, которые еще когда-то выполнял человек. Одна из сложнейших и затратных из них является операция поиска. Сложность поиска возрастает в зависимости от количества данных, а также от способа этого самого поиска. Например, если мы будем искать данные в упорядоченном массиве данных, то поиск необходимой информации займет всего О(log2N) шагов, что является очень хорошим показателем. Но чаще всего, нам приходится искать что-либо в так называемом неупорядоченном массиве данных. Примером такого поиска может быть поиск необходимой книги, на полке, где книги не являются упорядоченными. В случае с книгами человек будет использовать один из простейших способов поиска - поиск перебором. Его суть заключается в последовательном переборе данных от начала к концу. Но в данном случае рассматривается простой вариант перебора так как мы совершаем поиск по названию книги или по инициалам автора. А что если, необходимо найти книгу красного цвета, где имя автора начинается на букву А? Будучи человеком, решить такую задачу достаточно не сложно. Лишь потому что мы можем видеть и мыслить. А может ли машина видеть и мыслить? Этим вопросом задавался великий Алан Тьюринг! Ответ на вопрос весьма неоднозначен, но можно ответить следующим образом: да, если машина будет знать что такое красный и что такое фамилия, начинающаяся с буквы А.
Я предлагаю Вам ознакомиться с несколькими способами организации любых данных в очень удобной форме как для поиска, так и для сортировки этих данных, которая будет очень кстати для уже вышеупомянутой операции поиска. Данные способы - фундаментальные алгоритмы постоянно применяются как при самой работе компьютера, так и при выполнении программ, содержащих данные алгоритмы. Таковых существует множество, но мы сравним некоторые из них - лучшие и средние по производительности. Сперва необходимо привести конкретный пример, для которого будут производиться данные исследования.
Рассмотрим следующую задачу: имеется картотека карточек с определенной информацией, где карточки имеют собственный номер от 0 до 9. А так же имеют Указатели в виде отметок на рёбрах этих карточек для сотен, тысяч номеров. Карточки имели отметки о их принадлежности не в форме цифр, а в виде полос, нанесенных определенным образом, что позволяло находить необходимые карточки за несколько секунд. Такая система называлась “Моментальная картотека” и использовалась в советских библиотеках.
Данная задача может быть решена с помощью хеш-функций, где показатели поиска - самые лучшие. Необходимая информация может быть найдена за один(!) шаг при условии отсутствия коллизий. А вставка в хеш список обладает такой же скоростью, что и поиск. Данная структура данных лучше всего выполняет свою основную задачу, а именно поиск данных и доступ к ним за наименьшее время. Но как и у любой структуры данных у нее есть и свои отрицательные стороны: при расширении хеш таблицы необходимо перестроить хеши всех значений, что займет O(N) шагов, где N - число элементов. Данная структура в реализации на одномерном массиве может занимать очень большую величину непрерывной памяти.
Основные этапы реализации структуры:
1. Создание массива, где размер массива - простое число.
2. Создание функции хеширования с возможностью неоднократного хеширования
3. Реализация метода добавления данных
4. Реализация метода вывода данных
5. И самое главное - функция поиска!
Вторым способом решения приведенной задачи может выступать так же хеш функция, но уже ее расширенный вариант, использующий динамические списки для более разумного использования памяти. Однако по сравнению с обычной хеш функцией на массиве эта реализация более затратна, где поиск элемента может быть выполнен как за O(1) шагов так и за O(1) + O(N/B), где N число элементов в списке и B блоков. А так же поиск элементов в списках может проходить гораздо быстрее, если списки будут отсортированы и количество элементов в списке будет небольшим.
Основные этапы реализации структуры:
1. Создание массива для хранения данных.
2. Создание структуры или класса для манипуляций с данными
3. Создание функции хеширования с возможностью неоднократного хеширования
4. Реализация метода добавления данных
5. Реализация метода вывода данных
хеш таблица позволяет очень быстро находить и сохранять значения, но необходимо помнить несколько важных моментов:
1. хеш таблица работает с высокой производительностью, если коэффициент ее заполненности не выходит за рамки данного неравенства: 0.5<X<0.75.
2. Если же данных наоборот слишком мало, то это отражается на нерациональных расходованиях памяти.
Подводя и итог, хочется отметить, что хеш-таблицы обладают выдающимися характеристиками производительности, при правильном использовании этой структуры данных, а также несложной реализацией.
Код:
Приложение № 1
class StringHashTable
{
string[] data = null;
//создаем экземпляр с нужной размерностью
public StringHashTable(int size)
{
this.data = new string[size];
}
//Конвертация строк в набор символов
public int convertStringToBytesTwo(string input)
{
int output = 0;
byte[] barr = ASCIIEncoding.ASCII.GetBytes(input);
for (int i = 0; i < barr.Length; i++)
output += Convert.ToInt32(barr[i]);
return output;
}
//Поиск пока не нашли или не нашли пустую строку или к-во шагов не превысит
//величину массива иначе бесконечный цикл
public int find(string input)
{
int key;
int step = 0;
int value = convertStringToBytesTwo(input);
while (true)
{
key = ((value % data.Length) + step * ((value % (data.Length - 1)) + 1)) % data.Length;
if (data[key] == input) return key;
if (data[key] == "") return -1;
if (step >= data.Length) return -1;
step++;
}
}
//аналогичные комменты как и для find
public int add(string input)
{
int key = 0;
int step = 0;
int value = convertStringToBytesTwo(input);
while (true)
{
key = ((value % data.Length) + step * ((value % (data.Length - 1)) + 1)) % data.Length;
if (data[key] == null)
{
data[key] = input;
return key;
}
if (step >= data.Length) return -1;
step++;
}
}
//простой вывод
public void Out()
{
for (int i = 0; i < data.Length; i++)
Console.WriteLine(data[i]);
}
}
Приложение №2
class HashChains
{
//Структура, используемая как тип массива
public class Item
{
public string Info { get; set; }
public int Value { get; set; }
public Chain First { get; set; }
public Chain Last { get; set; }
}
//Структура для хранения элементов в списке
public class Chain
{
public string Info { get; set; }
public int Value { get; set; }
public Chain Next { get; set; }
}
private Item[] chains = null;
public HashChains(int size)
{
chains = new Item[size];
}
// Дальнейшая реализация - расширение методов из Приложения № 1
}