Хэш-таблицы, часть 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 старшие биты могут просто обрезаться и не учитываться из-за операции по модулю.

В следующем посте поговорим о коллизиях и способах их решения, короче продолжение следует...