A Хэш (он же Hash Table) подразумевает более чем Карта (или Ассоциативный массив) .
В частности, Карта (или Ассоциативный массив) является Абстрактным типом данных :
... ассоциативный массив (также называемый картой или словарем) представляет собой абстрактный тип данных, состоящий из набора пар (ключ, значение), так что каждый возможный ключ появляется не более одного раза в коллекции.
В то время как Хеш-таблица является реализацией Карты (хотя ее также можно считать ADT, которая включает «стоимость»):
... хеш-таблица или хеш-карта - это структура данных, в которой использует хеш-функцию для сопоставления идентифицирующих значений, известных как ключи [...], с их соответствующими значениями [...] , Таким образом, хеш-таблица реализует ассоциативный массив [или map].
Таким образом, это утечка деталей реализации: HashMap - это Map, который использует алгоритм хеш-таблицы и, таким образом, обеспечивает ожидаемые характеристики производительности такого алгоритма. «Утечка» деталей реализации хороша в этом случае, потому что она обеспечивает некоторые основные [ожидаемые] связанные гарантии, такие как [ожидаемое] O(1) - или постоянное время - get.
Подсказка: хеш-функция является важной частью алгоритма хэш-таблицы и устанавливает HashMap отдельно от других реализаций Map, таких как TreeMap (что используется красно-черное дерево ) или ConcurrentSkipListMap (в котором используется список пропуска ).
Другой формой карты является Список ассоциаций (или «alist», который является распространенным в программировании LISP). Хотя списки ассоциаций O(n) для get, они могут иметь гораздо меньше накладных расходов для малых n, что поднимает еще одну точку: Big-Oh описывает ограничение поведения (как n -> infinity) и не касается относительной производительности для конкретного [smallish] n:
Описание функции в терминах обозначений больших О, обычно , дает только верхнюю границу скорости роста функции.
Пожалуйста, обратитесь к ссылкам выше (включая Javadoc) для ознакомления с основными характеристиками и различными стратегиями реализации. - все остальное, что я здесь говорю, уже сказано там (или в других ответах SO). Если есть конкретные вопросы, откройте новый пост SO, если это оправдано: -)
Удачного кодирования.
Вот источник для реализации HashMap, которая есть в OpenJDK 7. Изучение метода put показывает, что это простая цепочка в качестве метода разрешения конфликтов и что базовый «массив блоков» будет увеличиваться в 2 раза при каждом изменении размера (которое срабатывает при достижении коэффициента нагрузки). Коэффициент нагрузки и ожидаемая амортизированная производительность, в том числе используемая функция хеширования, описаны в документации класса.