Хешування як метод організації та пошуку даних

Abstract

У доповіді розглянуто хешування як фундаментальний метод швидкого доступу до даних. Хеш-функція трактується як відображення множини ключів на множину індексів таблиці. Проаналізовано проблему колізій та методи їх розв’язання – ланцюжки і відкриту адресацію. Показано, що за рівномірної хеш-функції основні операції виконуються в середньому за сталий час. Окремо розглянуто криптографічне хешування та сфери практичного застосування.

The report considers hashing as a fundamental method of fast data access. A hash function is treated as a mapping of a set of keys onto a set of table indices. The collision problem and methods of its resolution – chaining and open addressing – are analysed. It is shown that with a uniform hash function the main operations are performed on average in constant time. Cryptographic hashing and areas of practical application are also discussed.