Приведут ли похожие строки в HashMap к увеличению вероятности столкновений?

Question

Учтите следующее:

HashMap<String, Object> hm = new HashMap<>();
final String prefix = "My objects ";
int counter = 0;

void put(Object value) {
    hm.put(prefix+(counter++), value);
}

Учитывая, что ключ каждой записи начинается с одной и той же строки и отличается только числом, добавленным к нему, это может привести к большему количеству коллизий? Я пытаюсь решить, является ли этот способ создания уникальных ключей хорошей идеей с точки зрения производительности.

Answer 1

Нет, не будет. И это не обязательно из-за String#hashcode; но потому что HashMap выполнит повторное хэширование любого хэш-кода, выполнив XOR, выполнив 16 бит с последними 16.

// this is re-hashing that is done internally
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Но даже если это увеличит столкновение, вы никогда не почувствуете это. Для маленьких ведер / корзина, где записи размещаются одна за другой (в связанном виде), equals будет вызван, чтобы получить фактическую запись, о которой вы заботитесь.

Если определенная корзина / ведро достигает определенного порогового значения, оно будет преобразовано в perfectly balanced tree node, Время поиска в таком дереве 0(logn),

Даже если одни и те же записи сообщают об одном и том же хэш-коде после повторного хеширования, карта все равно должна решить, какая запись больше в случае связывания.

Затем он попытается вызвать Comparable#compareTo в случае, если ваши ключи реализуют Comparable. В случае, если они не реализуют Comparable, System.identityHashcode будет вызван, чтобы решить в случае галстука.

Как вы говорите с точки зрения производительности из-за всех этих внутренних вещей, ваше среднее время поиска будет O(1) на карте.