14 Гру 2012 15:08Прочитав статті на хабрі: http://habrahabr.ru/post/128017/ - Структури даних у картинках. HashMap; http://habrahabr.ru/post/129037/ - Структури даних у картинках. LinkedHashMap.
Зрозумів як працює HashMap та LinkedHashMap. Стисло. HashMap – масив зв'язкових списків. Основна фішка Map-ів, що можна одразу обчислити бакет, в якому лежить елемент (позицію у масиві) по хешкоду. Просто беремо key, отримуємо його хеш, проганяємо через спеціальний метод і отримуємо позицію в масиві. Так як HashMap масив зв'язкових списків, то недоліком є саме ці списки. Адже якщо вийде так, що в одному бакеті (комірці масиву) утворюється зв'язковий список з кількох елементів (розробники гарантують, що в одному бакеті буде не більше 8 ел.), то для пошуку потрібного елемента доведеться перебирати список.
Якщо повернутися до класичних структур даних, це асоціативний масив, що підтримує три дії:
- Вставка;
- Пошук;
- Вилучення;
Разом, що ми маємо:
- Вставка нового елемента за час Θ(1);
- При рівномірному розподілі елементів (відсутності колізій), операції пошуку та видалення дорівнюють Θ(1);
- Середній час роботи (за наявності колізій) буде Θ(1+ α), де α - коефіцієнт завантаження.
- Якщо всі елементи в одному ланцюжку, час пошуку буде Θ(n)