Какова временная сложность извлечения элемента из LinkedHashMap в случае столкновения?

Question

Предположим, что у меня есть объект LinkedHashMap с 8 кодами, пронумерованными от 0 до 7. Теперь я хочу добавить элементы. Я добавил 7 элементов, и результат следующий:

1) Element_1: номер ведра 2. Это станет началом связанного списка, который поддерживает LinkedHashMap для поддержания порядка вставки.
1) Element_2: Ковш номер 3. Это связано с Element_1
2) Element_3: Ковш номер 1. Это связано с Element_2
3) Element_4: Ковш Номер 4. Это связано с Elemetn_3
4) Element_5 : Bucket Number 5. Это связано с Element_ 5) Element_6: номер ведра 3. Это связано с Element_5 (произошло столкновение)
6) Element_7: номер ведра 3. Это связано с Element_6 (снова столкновение)

Теперь предположим, что хочу получить Element_7. Хеширование этого элемента дает мне ведро номер 3. Теперь элементы в ковшом числа 3 являются Element_2, Element_6, Element_7.
Итак, каков порядок прохождения следующих двух:
a) Element_2-> Element_3-> Element_4-> Element_5-> Element_6-> Element_7.
OR
b) Element_2-> Element_6-> Element_7.

Я думал, что ответ будет (а), потому что LinkedHashMap поддерживает связанный список для поддержания порядка вставки. Поэтому, если порядок (b) означает, что конкретный элемент хранит две ссылки, одну для следующего элемента в порядке вставки и одну для следующего элемента в том же ведре.

Если ответ (б), как решается конкретный элемент, какой из них следует посетить, т. Е. из двух ссылок, которые нужно выбрать.

Сценарий использования является гипотетическим, и он может быть несовместим с тем фактом, что с числом элементов, меньшим, чем количество ведер, вероятность столкновения меньше. Пожалуйста, ответьте, имея в виду вышеупомянутый сценарий.
Спасибо заранее.

Answer 1

LinkedHashMap расширяет HashMap и, следовательно, ссылка не имеет отношения к get, поэтому добавив ссылку, они не должны были сделать LinkedHashMap менее эффективным на get - так как get не нуждается в этой связи.

Answer 2

LinkedHashMap расширяет HashMap, а его метод get вызывает метод HashMap getEntry. Реализация HashMap хранит каждый ведро в отдельном массиве, поэтому ему не нужно будет перебирать весь набор данных только по данным внутри этого ведра.Взятые форма Oracle JDK 7:

final Entry<K,V> getEntry(Object key) { 
    int hash = (key == null) ? 0 : hash(key.hashCode()); 
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
     e != null; 
     e = e.next) { 
     Object k; 
     if (e.hash == hash && 
      ((k = e.key) == key || (key != null && key.equals(k)))) 
      return e; 
    } 
    return null; 
} 

РЕДАКТИРОВАТЬ

e.next определяется в HashMap.Entry и находится в пределах одной и той же ведро, в отличие от e.after и e.before определены в LinkedHasMap.Entry, которые могут находиться в разных ковшей.