Создать хеш-таблицу с двумя массивами

Question

Кто-нибудь знает, как это сделать и как будет выглядеть псевдокод?

Как мы все знаем, в хеш-таблице хранятся пары ключ-значение, а когда вызывается ключ, функция возвращает значение, связанное с этим ключом. То, что я хочу сделать, это понять основную структуру при создании этой функции отображения. Например, если бы мы жили в мире, где не было ранее определенных функций, кроме массивов, как мы могли бы воспроизвести хэш-карты, которые у нас есть сегодня?

Answer 1

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

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

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

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

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

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

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

Вариант того, кем вы являетесьзапрос описывается как 'таблица хеш-функции массива' в записи .

Code в хэш-таблице для хеш-кодов. Взгляните здесь

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

Answer 2

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

В приведенном ниже источнике, в основном, он делает две вещи:

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

• Некоторые (X номер списка) списков
• X в 2 степени N количество списков плохое. A (2 степени N) -1 или (2 степени N) +1, или простое число - это хорошо.

Пример:

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

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

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

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

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

• инициализировать значение хеша первым символом (после преобразования в int)
• для каждого последующего символа, сдвиг влево на 4 бита, затем добавление символа (после преобразования в 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/

Answer 3

Вы имеете в виду, как это?

Следующее использует Ruby's 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 

Answer 4

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

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

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

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