Изменения

Перейти к: навигация, поиск

Хеш-таблица

1106 байт добавлено, 21:06, 4 июня 2015
Нет описания правки
На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно <tex>\Theta(n)</tex>, но на практике хеширование более эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.
При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо [[Перехеширование. Амортизационный анализ|перехешировать]] таблицу: увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.
 
===Хеширование в современных языках программирования===
 
Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.
*Java
**HashMap {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
**HashSet {{---}} реализация интерфейса множества с использованием хеш-таблицы,
**LinkedHashMap {{---}} потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.
*C++
**hash_map {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
**hash_set {{---}} реализация интерфейса множества с использованием хеш-таблицы.
== Примечания ==
Анонимный участник

Навигация