Розмір шрифта: 

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

 

Hashing as a method of organizing and searching data

Abstracts:

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.

хеш-функція; хеш-таблиця; колізія; відкрита адресація; складність; криптографічне хешування; hash function; hash table; collision; open addressing; complexity; cryptographic hashing