Алгоритмы и структуры данных. Извлечение информации на языке Java

128

Глава 10. Хеширование

Моя реализация put и get выглядит следующим образом:

public V put(K key, V value) {

MyLinearMap<K, V> map = chooseMap(key);

return map.put(key, value);

}

public V get(Object key) {

MyLinearMap<K, V> map = chooseMap(key);

return map.get(key);

}

Довольно просто, не правда ли? В обоих методах мы используем

chooseMap для поиска правильной подкарты, а затем вызываем

метод для нее. Вот как это работает; теперь подумаем о произ-

водительности.

Если n записей распределено между k ключей, то в среднем на

одну карту приходится n / k записей. При поиске ключа нужно

вычислить его хеш-код, что занимает некоторое время, затем

искать соответствующую подкарту.

Поскольку списки записей в MyBetterMap в k раз короче, чем

список записей в