Ответ 1

На самом деле, некоторые из сегодняшних имплантатов Hashmap действительно сделаны из массивов, как вы предлагаете. Позвольте мне набросать, как это работает:

Функция хеширования Хеш-функция преобразует ваши ключи в индекс для первого массива (массив K). Для этого может использоваться хеш-функция, такая как MD5 или более простая, обычно включающая оператор modulo.

Ковши Простая реализация на основе массива Hashmap может использовать ведра для обработки коллизий. Каждый элемент ( "ведро" ) в массиве K содержит сам массив (массив P) пар. Когда вы добавляете или запрашиваете элемент, хеш-функция указывает вам правильное ведро в K, которое содержит ваш желаемый массив P. Затем вы перебираете элементы в P до тех пор, пока не найдете соответствующий ключ, или вы назначаете новый элемент на конец P.

Сопоставление ключей с ведрами с помощью Hash Вы должны убедиться, что количество ведер (т.е. Размер K) равно мощности 2, скажем 2 ^ b. Чтобы найти правильный индекс ковша для некоторого ключа, вычислите Hash (ключ), но только сохраните первые b бит. Это ваш индекс при преобразовании в целое число.

Масштабирование Вычисление хэша ключа и поиск правильного ведра происходит очень быстро. Но как только ковш станет более полным, вам придется перебирать все больше и больше предметов, прежде чем вы перейдете к правильному. Поэтому важно иметь достаточное количество ведер для правильного распределения объектов, или ваш Hashmap станет медленным.

Поскольку вы, как правило, не знаете, сколько объектов вы хотите сохранить в Hashmap заранее, желательно динамически увеличивать или сжимать карту. Вы можете сохранить количество сохраненных объектов, и как только он перейдет через определенный порог, вы воссоздаете всю структуру, но на этот раз с большим или меньшим размером для массива K. Таким образом, некоторые из ковшей в K, которые были теперь они будут полностью разделены на несколько ведер, поэтому производительность будет лучше.

Альтернативы Вы также можете использовать двумерный массив вместо массива массивов, или вы можете обменивать массив P для связанного списка. Кроме того, вместо того, чтобы хранить общее количество хранимых объектов, вы можете просто выбрать воссоздать (то есть перемасштабировать) хэш-карту, как только один из ведер содержит больше определенного количества элементов.

Вариант того, что вы просите, описывается как "хэш-таблица массива" в в таблице Хеш-записи Wikipedia.

код Для образцов кода посмотрите здесь.

Надеюсь, что это поможет.

Ответ 2

Пример Объяснение:

В приведенном ниже источнике в основном он выполняет две функции:

1. Представление карты

• Некоторые (X-список списков) списков
• X, являющийся 2 степенями, количество списков неверно. A (2 power N) -1 или (2 power N) +1 или простое число.

Пример:

List myhashmap [hash_table_size];
// an array of (short) lists
// if its long lists, then there are more collisions

ПРИМЕЧАНИЕ: это массив массивов, а не два массива (я не вижу возможного общего хэш файла, в хорошем смысле всего с двумя массивами)

Если вы знаете Алгоритмы > Теория диаграмм > Список аджакции, это выглядит точно так же.

2. Хэш-функция

И хеш-функция преобразует строку (ввод) в число (хеш-значение), которое является индексом массива

• инициализировать хэш-значение до первого char (после преобразования в int)
• для каждого последующего char, сдвиг влево 4 бит, затем добавьте char (после преобразования в int)

Пример

int hash = input[0];
for (int i=1; i<input.length(); i++) {
    hash = (hash << 4) + input[i]
}

hash = hash % list.size()
// list.size() here represents 1st dimension of (list of lists)
//      that is 1st dimension size of our map representation from point #1
//      which is hash_table_size

См. по первой ссылке:

int HTable::hash (char const * str) const

Источник:
http://www.relisoft.com/book/lang/pointer/8hash.html
Как работает хеш-таблица?

Обновление
Это лучший источник: http://algs4.cs.princeton.edu/34hash/

Ответ 3

Не могли бы вы уточнить? Один массив содержит ключи, а другой - значения?

Если это так, вот пример в Java (но здесь есть несколько особенностей этого языка):

for (int i = 0; i < keysArray.length; i++) {
    map.put(keysArray[i], valuesArray[i]);
}

Конечно, вам придется создать экземпляр объекта map (если вы используете Java, я предлагаю использовать HashMap<Object, Object> вместо устаревшего HashTable), а также проверять ваши массивы, чтобы избежать null и проверьте, имеют ли они одинаковый размер.

Ответ 4

Ты имеешь в виду вот это?

В качестве иллюстрации используется Ruby irb:

 cities = ["LA", "SF", "NY"]
 => ["LA", "SF", "NY"] 

 items = ["Big Mac", "Hot Fudge Sundae"]
 => ["Big Mac", "Hot Fudge Sundae"] 

 price = {}
 => {} 

 price[[cities[0], items[1]]] = 1.29
 => 1.29 

 price
 => {["LA", "Hot Fudge Sundae"]=>1.29} 

 price[[cities[0], items[0]]] = 2.49
 => 2.49 

 price[[cities[1], items[0]]] = 2.99
 => 2.99 

 price
 => {["LA", "Hot Fudge Sundae"]=>1.29, ["LA", "Big Mac"]=>2.49, ["SF", "Big Mac"]=>2.99} 

 price[["LA", "Big Mac"]]
 => 2.49