Хэш-таблицы, часть I. Бывают ситуации когда нужно хранить какое-то значение на основе определенного ключа и не просто хранить, а еще иметь возможность быстро его изменить, например это может быть кэш для картинок или загруженных файлов: // храним картинки в кэше, в качестве ключа используется адрес val imageCache = mutableMapOf<Uri, Bitmap>() // храним файлы в кэше, в качестве ключа также используется адрес val downloadCache = mutableMapOf<Uri, File>() Для реализации подобной структуры данных часто используется обычный массив, индексы которого вычисляются с помощью хэш функции, отсюда название хэш-таблица: val images = Array(10) { "" } val url = "https://images.com/image0" val image = downloadImage(url) // за счет практически мгновенного вычисления индекса в хэш-таблице время добавления и изменения значений в среднем составляет O(1) val index = hash(url) images[index] = image fun downloadImage(url: String) { ... } // простая хэш-функция fun hash(url: String): Int { return url.last().digitToInt() } В примере достаточно примитивная хэш функция, которая просто извлекает цифру из строки и принимает ее за индекс. В боевой же реализации HashMap используется другая хэш-функция, а также метод hashCode(): // что-то типо модульного деления, ограничивает индекс до размера массива - 1 int index = hash(key) & (size - 1); // боевая версия хэш-функции static final int hash(Object key) { if (key == null) return 0; // о переопределении этого метода уже наверно книги есть, короче если он плохо написан индексы будут одинаковые, а это коллизия и ее надо как-то решать int h = key.hashCode(); // смешивает младшие биты со старшими return h ^ (h >>> 16); } Смешивание младших и старших битов нужно для более равномерного распределения индексов, так как при небольшом размере HashMap старшие биты могут просто обрезаться и не учитываться из-за операции по модулю. В следующем посте поговорим о коллизиях и способах их решения, короче продолжение следует...