По-перше що таке HashMap. HashMap - це асоціативний масив. Якщо коротко, то асоціативний масив - це структура даних, яка зберігає пари ключ-значення.
Щоб було простіше зрозуміти що це таке, можна представляти HashMap як пронумеровані кошики, в яких зберігаються якісь дані (Рис. 1). При додаванні нового об'єкта в HashMap. ми крім самого об'єкта передаємо ще й ключ, за яким в подальшому, його можна буде відшукати.
Як по ключу можна визначити положення шуканого об'єкта? Для цього нам потрібно знати hashCode ключа. Де ж його взяти? Все дуже просто, якщо розуміти, що в якості ключа, може виступати будь-який об'єкт в java. Всі знають що клас Object реалізує метод hashCode (), це означає що він буде успадкований або перевизначений самим "ключем". Оскільки все в java успадковуються від класу Object. Тепер зрозуміло звідки у ключа береться hashCode!
Після того як в hashMap. був переданий ключ + зберігається об'єкт, спеціальна hash-функція обчислює то в яку корзину віднести наші дані.
Як ви розумієте, ніяких кошиків в HashMap -е немає. Замість них є масив, який зберігає посилання на пов'язані списки в яких зберігаються наші дані. Кожному елементу масиву відповідає один список.
Дане питання мені жодного разу не задавали я його знайшов на Хабре. Відповідь - 16. Але як і з ArrayList-ом в конструкторі можна задати інше кількість.
Це питання так само часто зустрічається. Колізія це коли два різних об'єкта потрапляють в один кошик (зв'язаний список). Причиною цього є те, що вони мають однаковий hashcode. Для більш ефективної роботи з HashMap, hashcode не повинен повторюватися для не еквівалентні об'єктів.
Як я вже згадав вище, всі дані зберігаються в списках. Чому так? Чому не зберігати всього один об'єкт? Відповідь проста. Все тому, що це спосіб вирішення колізій. Як відбувається додавання? Огляд код 1
- Перше - ми з'ясовуємо то який кошик відповідає ключу об'єкта. Потім перевіряємо, чи є в ній вже якісь об'єкти, якщо немає - то додаємо поточний. Якщо так, то це трапилася колізія.
- Тоді ми починаємо порівнювати ключ і hashcode поточного об'єкта і тих які всередині (якщо звичайно їх там декілька).
- Спочатку перевіряємо чи рівні hashcode ключів.
- Якщо так, то порівнюємо їх ключ методом equals.
- Якщо equals повертає true, значить ключі збігаються з "значенням" і hashcode - проводиться заміна, новий об'єкт замінює той який вже там знаходиться під тим же ключем,
- Якщо hashcode і "значення" ключа нерівні - новий об'єкт додається в кінець списку.
HashMap має поле loadFactor. Воно може бути задано через конструктор. За замовчуванням дорівнює 0.75. Для чого це потрібно? Його твір на кількість кошиків дає нам необхідну кількість об'єктів, яке потрібно додати, щоб відбулося подвоєння кількості кошиків. Наприклад, якщо у нас МАПком з 16-ю кошиками, а loadFactor дорівнює 0.75, то розширення відбудеться коли ми додамо 16 * 0.75 = 12 об'єктів. МАПком збільшується вдвічі.
Розглянемо спочатку випадок в якому немає колізій. В цьому випадку додавання, видалення і пошук об'єктів по ключу виконується за константне час O (1). Зрозуміло, не враховується випадок з розширенням кількості елементів. Взагалі кажучи, коли Ви працюєте з HashMap, краще відразу вказати в конструкторі, скільки кошиків потрібно для роботи і добре якщо воно дорівнює числу унікальних об'єктів з якими Ви будите працювати. В такому разі не доведеться витрачати час і ресурси на створення нового HashMap з подвоєною кількістю bucket-ов. Чому така гарна продуктивність? Тут все просто. Повторюся що колізій немає - в такому випадку немає ніякої залежності від інших елементів з цієї МАПком. Видалення, Вставка, Пошук виконуються приблизно за однією схемою. Береться HashCode ключа, обчислюється кошик, і проводиться видалення, вставка або пошук. Усе! Ніде не зустрічаються інші об'єкти. Але це лише в тому випадку, якщо немає колізій.
Тепер поговоримо про випадок коли колізії все-таки присутні. Теоретично працюючи з HashMap в якому можуть бути присутніми колізії, ми отримуємо тимчасову складність O (log (n)) на операції вставки, збереження і видалення. У найгіршому випадку, коли всі об'єкти повертають один і той же HashCode, а значить потрапляють в одну корзину. Насправді це зв'язний список і тоді тимчасова складність як у LinkedList O (n).
На цьому поки все. Хай щастить.
Для того, щоб зрозуміти що людина дійсно знає як це працює. Те як працює HashMap знати потрібно обов'язково і не тому, що це запитують на інтерв'ю.
Знати як работвет HashMap. Програмісту треба знати. що собою являє Map інтерфейс. І як цей інтерфейс реалізований Sun / Oracle - це лише питання допитливості. Є маса реалізацій інтерфейсу Map (Google, Apache etc.) І що, треба зупинятися на тому як зсередини це робить Oracle? Набагато важливіше програмісту знати, що в кінцевому рахунку для реалізації використовуються native методи. А то багато хто вважає, що використовуються масиви java. А вже як там Oracle будує якісь внутрішні структури абсолютно не важливо.