Computer Science

Что такое хеш-таблицы?

Хеш-таблица — это контейнер для хранения пар ключей и их значений. По сути это ассоциативный массив, в котором ключ представлен в виде хеш-функции. Главное свойство hash-таблиц — три операции: вставка, поиск и удаление — в среднем выполняются за время O(1),

Принято считать, что хорошей, с точки зрения практического применения, является такая хеш-функция, которая удовлетворяет следующим условиям: 
 ⁃ функция должна быть простой с вычислительной точки зрения; 
 ⁃ функция должна распределять ключи в хеш-таблице наиболее равномерно; 
 ⁃ функция не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов; 
 ⁃ функция должна минимизировать число коллизий – то есть ситуаций, когда разным ключам соответствует одно значение хеш- функции(ключи в этом случае называются синонимами ).

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

www.tgoop.com/CScience1/2539

2.33K viewsDec 22, 2023 at 09:00

Что такое хеш-таблицы?

Хеш-таблица — это контейнер для хранения пар ключей и их значений. По сути это ассоциативный массив, в котором ключ представлен в виде хеш-функции. Главное свойство hash-таблиц — три операции: вставка, поиск и удаление — в среднем выполняются за время O(1),

Принято считать, что хорошей, с точки зрения практического применения, является такая хеш-функция, которая удовлетворяет следующим условиям: 
 ⁃ функция должна быть простой с вычислительной точки зрения; 
 ⁃ функция должна распределять ключи в хеш-таблице наиболее равномерно; 
 ⁃ функция не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов; 
 ⁃ функция должна минимизировать число коллизий – то есть ситуаций, когда разным ключам соответствует одно значение хеш- функции(ключи в этом случае называются синонимами ).

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

BY Computer Science