Ассоциативный массив: Hash-таблица

Одной из часто используемых реализаций ассоциативного массива является hash-таблица.
Важной особенностью является сложность выполнения операций добавления, удаления и поиска - O(1) - другими словами, сложность алгоритма не зависит от количества элементов в массиве - хоть 10 элементов, хоть 10 млн.
Общая идея реализации

• Ключу может быть поставлено в соответствие некоторое число - hash, вычисляемое с помощью hash-функции
• Таблица содержит M сегментов (buckets), где каждый сегмент представляет из себя связанный список элементов, где каждый элемент - это пара ключ → значение
• Индекс сегмента - «масштабированный» hash на массив сегментов (свёртка)
  индекс сегмента = hashCode mod кол-во сегментов
  находим сегмент, содержащий нужный элемент и уже путём прямого перебора элементов списка находим ключ

Замечание: количество выделенных сегментов в java.util.HashMap всегда есть 2^K, что даёт возможность использовать оптимизационный трюк (см. Java Puzzlers, Puzzle #1) для нахождения индекса сегмента:
bucketIndex = hashCode & (table.length - 1)

Коллизии:

• найденный блок содержит совпадающие свёртки hash'ей - проверяем равенство значений hash'ей
• равенство hash не гарантирует равенство значений ключей - поэтому, проверяем равенство ключей.

В java hash-функция определена для каждого объекта, т.к. каждый объект в java имеет корневого родителя java.lang.Object, а он в свою очередь содержит метод hashCode. Данный метод, по-умолчанию, возвращает число связанное некоторым образом с адресом объекта в памяти.
java.lang.Object так же определяет метод равенства объектов: equals - его реализация, по-умолчанию, сравнивает объекты по ссылке.

Т.о. использовать реализацию по-умолчанию hashCode и equals для объектов, используемых в качестве ключа для hash-таблиц очень спорно, а как правило и ошибочно.

Реализация методов hashCode и equals тесно связана между собой (Effective Java, 2nd ed., Item #9).

Особо важно стоит отметить, что ключ должен быть immutable иначе у вас его огромные шансы, что вы просто не найдёте ключ в map'е.

Необходимо учитывать, что чем разброс значений hash в зависимости от значения ключа влияет на эффективность использоваться hash-структур. Hash-функция может быть построена разными способами, пример реализации из Effective Java, 2nd ed., Item #9:

• Store some constant nonzero value, say, 17, in an int variable called result.
• For each significant field f in your object (each field taken into account by the equals method, that is), do the following:
  • Compute an int hash code c for the field:
    • If the field is a boolean, compute (f ? 1 : 0).
    • If the field is a byte, char, short, or int, compute (int) f.
    • If the field is a long, compute (int) (f ^ (f >>> 32)).
    • If the field is a float, compute Float.floatToIntBits(f).
    • If the field is a double, compute Double.doubleToLongBits(f), and then hash the resulting long as in step 2.a.iii.
    • If the field is an object reference and this class’s equals method compares the field by recursively invoking equals, recursively invoke hashCode on the field. If more complex comparison is required, compute a “canonical representation” for this field and invoke hashCode on the canonical representation. If the value of the field is null, return 0 (or some other constant, but 0 is traditional).
    • If the field is an array, treat it as if each element were a separate field. That is, compute a hash code for each significant element by applying these rules recursively, and combine these values per step 2.b. If every element in an array field is significant, you can use one of the Arrays.hashCode methods added in release 1.5.
      
  • Combine the hash code c computed in step 2.a into result as follows:
    result = 31 * result + c;
    
• Return result.
  
• When you are finished writing the hashCode method, ask yourself whether
  equal instances have equal hash codes. Write unit tests to verify your intuition!
  If equal instances have unequal hash codes, figure out why and fix the problem.