Хэш-таблица - это одномерный массив, позволяющий в качестве индексов использовать объекты произвольного типа.
Одна ассоциация между индексом (ключом) и элементом (значением), хранимая в хэш-таблице, называется входом (entry). Сопоставление ключей осуществляется с помощью test-предиката, а ускорение доступа — с помощью хэш-функции. Она обеспечивает время поиска порядка О(1).