Хеш-таблица, Реализация на базе указателей. Хеш-таблица - что это? Реализация на базе указателей... как это ?

Хеш-таблица - это таблица значений хеш-функций.. . Н-да.. . Хеш-функция - это функция отобращающая большее множество в меньшее, причем мощность второго всегда известна заранее, именно поэтому хеш-функции называют также функциями свертки. Поскольку мощность известна, можно реализовать хеш-таблицу массивом. Для экономии памяти можно организовать связный список - это и будет реализация на базе указателей.
Теперь примеры, чтобы стало хоть более-менее понятно.. .
Задача: написать программу поиска файлов-дубликатов на диске. Для простоты файлами-дубликатами будем называть файлы с одинаковыми именами.
Идея проста: полным перебором проходим по дереву каталогов и имя каждого найденного файла где-то сохраняем, чтобы была возможность отследить-таки дубли.
Вопрос: где их сохранять?
Вариантов, на самом деле, не так уж много: это либо массив, либо список.
Первый не подходит, особенно если массив статический. Остается список, где каждый элемент списка - это имя файла. При этом надо отметить, что множество имен файлов можно считать условно бесконечным. И мы сталкиваемся с проблемой поиска дубля: поскольку список неупорядоченный то поиск можно осуществить только полным проходом по списку. Если список сортировать - будет еще дольше :) А поскольку его размер растет до бесконечности то и время поиска увеличивается соответственно.
Что мы можем сделать?
Можно придумать такую функцию, которая произвольную строку "свернет", скажем, в строку фиксированной длины (как, например делает это серия алгоритмов MD) или вообще в число фиксированной разрядности (например, если сумму кодов символов строки взять по модулю 0хFF - то любая строка свернется в число размером всего байт!) .
Но вопрос "выдумывания" хеш-функций - очень сложный теоретический вопрос, поскольку для каждого конкретного случая подходит определенная функция, потому как эти функции должны отвечать определенным требованиям: например, равномерностью распределения
Так вот.. . теперь мы уже можем работать не с бесконечно длинным списком - а со списком, вообще говоря, строго определенной длины. Вычисляя значение хеш-функции для имени файла мы в дальнейшем будем оперировать с ним.
Тут еще надо отдельно говорить о способе разрешения коллизий: понятно, что ни одна хеш-функция не дает обратного преобразования, т. е. a.txt и b.txt могут иметь совершенно одинаковый ключ и что-то надо делать, чтобы по ключу не записать b.txt как дубль a.txt!
Ну а про реализацию хеш-таблиц упоминал выше.