Ответ 1

Здесь объяснение в терминах непрофессионала.

Предположим, вы хотите заполнить библиотеку книгами, а не просто запихивать их туда, а хотите, чтобы вы могли легко найти их снова, когда они вам понадобятся.

Итак, вы решаете, что если человек, который хочет прочитать книгу, знает название книги и точное название для загрузки, то это все, что нужно. С таким названием человек с помощью библиотекаря должен легко и быстро найти книгу.

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

Вы хотите что-то, что, с названием книги, может дать вам правильное место сразу, поэтому все, что вам нужно сделать, это просто прогуляться к правой полке и забрать книгу.

Но как это можно сделать? Ну, с некоторой предусмотрительностью, когда вы заполняете библиотеку, и большой работой, когда вы заполняете библиотеку.

Вместо того, чтобы просто начинать заполнять библиотеку с одного конца до другого, вы разрабатываете маленький умный метод. Вы берете название книги, запускаете ее через небольшую компьютерную программу, которая выплевывает номер полки и номер слота на этой полке. Здесь вы размещаете книгу.

Прелесть этой программы в том, что позже, когда человек возвращается, чтобы прочитать книгу, вы снова вводите название программы и возвращаете тот же номер полки и номер слота, которые были вам изначально предоставлены, и это где находится книга

Программа, как уже упоминалось другими, называется хеш-алгоритмом или хеш-вычислением и обычно работает, беря данные, введенные в нее (в данном случае название книги), и вычисляет число из нее.

Для простоты, скажем, что он просто конвертирует каждую букву и символ в число и суммирует их все. На самом деле, все намного сложнее, но пока оставим это в покое.

Прелесть такого алгоритма в том, что если вы снова и снова вводите один и тот же вход, он будет каждый раз выплевывать одно и то же число.

Хорошо, так что в основном, как работает хэш-таблица.

Технические вещи следует.

Во-первых, есть размер номера. Обычно выходные данные такого алгоритма хеширования находятся в пределах некоторого большого числа, обычно намного большего, чем пространство, которое у вас есть в вашей таблице. Например, допустим, что в библиотеке есть место для одного миллиона книг. Результат вычисления хеша может быть в диапазоне от 0 до одного миллиарда, что намного выше.

Так что же нам делать? Мы используем то, что называется модульным вычислением, которое в основном говорит о том, что если вы сосчитали до нужного вам числа (т.е. До одного миллиарда), но хотели остаться в гораздо меньшем диапазоне, каждый раз, когда вы достигаете предела этого меньшего диапазона, с которого вы начинали. 0, но вы должны следить за тем, как далеко в большой последовательности вы прошли.

Скажем, выходной результат алгоритма хеширования находится в диапазоне от 0 до 20, и вы получите значение 17 из определенного заголовка. Если размер библиотеки составляет всего 7 книг, вы считаете 1, 2, 3, 4, 5, 6, а когда вы добираетесь до 7, вы начинаете с нуля. Так как нам нужно сосчитать 17 раз, у нас есть 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, и окончательное число равно 3.

Конечно, вычисление модуля не делается так, оно выполняется с делением и остатком. Остаток от деления 17 на 7 равен 3 (7 переходит 2 раза в 17 в 14, а разница между 17 и 14 равна 3).

Таким образом, вы положили книгу в слот № 3.

Это приводит к следующей проблеме. Столкновения. Поскольку алгоритм не имеет возможности разнести книги так, чтобы они точно заполняли библиотеку (или, если хотите, хэш-таблицу), он неизменно будет вычислять число, которое использовалось ранее. В библиотечном смысле, когда вы доберетесь до полки и с номером слота, в который хотите положить книгу, там уже есть книга.

Существуют различные методы обработки столкновений, в том числе ввод данных в еще одно вычисление для получения другого места в таблице (двойное хеширование) или просто для поиска места, близкого к тому, которое вам было дано (т.е. Прямо рядом с предыдущей книгой, принимая слот был также доступен как линейное зондирование). Это будет означать, что вам придется покопаться, когда вы попытаетесь найти книгу позже, но это все же лучше, чем просто начинать с одного конца библиотеки.

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

Я надеюсь, что это объяснение было немного более приземленным, чем ведра и функции :)

Ответ 2

Использование и Линго:

1. Хеш-таблицы используются для быстрого хранения и извлечения данных (или записей).
2. Записи хранятся в корзинах с использованием хэш-ключей
3. Хеш-ключи рассчитываются путем применения алгоритма хеширования к выбранному значению (значению ключа), содержащемуся в записи. Это выбранное значение должно быть общим для всех записей.
4. Каждое ведро может иметь несколько записей, которые организованы в определенном порядке.

Пример из реального мира:

Компания Hash & Co., основанная в 1803 году и не обладающая какими-либо компьютерными технологиями, имела в общей сложности 300 картотек для хранения подробной информации (записей) примерно для 30 000 своих клиентов. Каждая папка с файлами была четко обозначена своим номером клиента, уникальным номером от 0 до 29 999.

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

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

Чтобы получить запись о клиенте, клерки должны были получить номер клиента на листке бумаги. Используя этот уникальный номер клиента (хеш-ключ), они будут модулировать его на 300, чтобы определить, в каком картотеке есть папка клиентов. Открыв шкаф, они обнаружат, что в нем много папок, упорядоченных по номеру клиента. Просматривая записи, они быстро находят папку клиента и извлекают ее.

В нашем реальном примере наши ведра - это шкафы для документов, а наши записи - это папки с файлами.

Важно помнить, что компьютеры (и их алгоритмы) работают с числами лучше, чем со строками. Таким образом, доступ к большому массиву с использованием индекса значительно быстрее, чем последовательный доступ.

Как уже упоминал Саймон, я считаю, что очень важным является то, что часть хеширования должна преобразовывать большое пространство (произвольной длины, обычно строки и т.д.) И отображать его в небольшом пространстве (известного размера, обычно числа) для индексации. Это очень важно запомнить!

Таким образом, в приведенном выше примере 30 000 возможных клиентов или около того сопоставляются с меньшим пространством.

Основная идея в этом состоит в том, чтобы разделить весь ваш набор данных на сегменты, чтобы ускорить фактический поиск, который обычно занимает много времени. В нашем примере выше каждый из 300 картотек (статистически) будет содержать около 100 записей. Поиск (независимо от порядка) по 100 записям намного быстрее, чем поиск по 30 000.

Возможно, вы заметили, что некоторые на самом деле уже делают это. Но вместо того, чтобы разрабатывать методологию хеширования для генерации хеш-ключа, они в большинстве случаев будут просто использовать первую букву фамилии. Поэтому, если у вас есть 26 шкафов для хранения документов, в каждом из которых есть буквы от А до Я, вы теоретически только что сегментировали свои данные и улучшили процесс регистрации и поиска.

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

Jeach!

Ответ 3

Это оказывается довольно глубокой областью теории, но основной план прост.

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

Если у вас есть только небольшое количество вещей для хэша, вы можете уйти, просто интерпретируя эти вещи как целые числа, и вы закончите (например, 4 байтовых строки)

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

Это означает, что вы хотите, чтобы он вряд ли имел тот же результат, и вам, вероятно, также очень хотелось бы, чтобы хеш-функция была быстрой.

Балансировка этих двух свойств (и нескольких других) заставила многих людей заняться!

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

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

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

Конечно, на практике вы, как правило, не можете этого сделать, это слишком много памяти. Таким образом, вы делаете все, основываясь на разреженном массиве (где единственными элементами являются те, которые вы на самом деле используете, все остальное - неявно).

Существует множество схем и трюков, чтобы сделать эту работу лучше, но это основы.

Ответ 4

Много ответов, но ни один из них не очень нагляден, и хеш-таблицы могут легко "щелкнуть" при визуализации.

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

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

Несколько моментов:

• каждая из записей массива (indices [0], [1]...) называется контейнером и запускает - возможно, пустой - связанный список значений (иначе говоря, элементы, в данном примере - имена людей)
• каждое значение (например, "fred" с хэшем 42) связано с сегментом [hash % number_of_buckets] например, 42 % 10 == [2]; % является оператором модуля - остаток при делении на количество сегментов
• несколько значений данных могут сталкиваться и связываться из одного сегмента, чаще всего потому, что их значения хеш-функции конфликтуют после операции модуля (например, 42 % 10 == [2] и 9282 % 10 == [2]), но иногда потому, что значения хеша одинаковы (например, "fred" и "jane" оба показаны с хешем 42 выше)
  • большинство хеш-таблиц обрабатывают коллизии - с немного сниженной производительностью, но без функциональной путаницы - сравнивая полное значение (здесь текст) ключа, который ищется или вставляется с каждым ключом, уже имеющимся в связанном списке в корзине хэширования.

При увеличении размера таблицы хеш-таблицы, реализованные, как указано выше, имеют тенденцию к изменению размера самих себя (т.е. создают больший массив сегментов, создают новые/обновленные связанные списки оттуда, удаляют старый массив), чтобы сохранить соотношение элементов к сегментам (или загрузку). фактор) где-то в диапазоне от 0,5 до 1,0. Ганс приводит фактическую формулу в комментарии ниже, но для ориентировочных значений: с коэффициентом загрузки 1 и хэш-функцией криптографической стойкости 1/e (~ 36,8%) контейнеров будут иметь тенденцию быть пустыми, еще 1/e (~ 36,8% ) имеют один элемент, 1/(2e) или ~ 18,4% двух элементов, 1/(3! e) около 6,1% трех элементов, 1/(4! e) или ~ 1,5% четырех элементов, 1/(5! e ) с примерно ~.3% имеют пять и т.д. - средняя длина цепочки из непустых сегментов составляет ~ 1,58 независимо от того, сколько элементов в таблице (т.е. есть ли 100 элементов и 100 сегментов или 100 миллионов элементов) и 100 миллионов блоков), поэтому мы говорим, что поиск/вставка/стирание - это O (1) операций с постоянным временем.

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

Несколько слов о хэш-функциях

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

Это обычно организовано с математикой, слишком сложной для меня, чтобы впасть. Я упомяну один простой для понимания способ - не самый масштабируемый или дружественный к кэшу, но по своей природе элегантный (например, шифрование с помощью одноразовой клавиатуры!) - так как я думаю, что он помогает вернуть желаемые качества, упомянутые выше. Допустим, вы хэшировали 64-битный double - вы можете создать 8 таблиц, каждая из которых содержит 256 случайных чисел (т.е. size_t random[8][256]), а затем использовать каждый 8-битный /1-байтовый фрагмент представления double памяти для индексации в другая таблица, XOR случайных чисел, которые вы ищете. При таком подходе легко увидеть, что изменение немного в любом месте double результата приводит к поиску другого случайного числа в одной из таблиц и совершенно некоррелированному конечному значению.

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

Ну, это было менее весело и тяжелее, чем объяснение хеш-таблицы, но надеюсь, что это кому-нибудь поможет...

Ответ 5

Вы, ребята, очень близко объясните это полностью, но не хватает пары вещей. Хэш-таблица - это всего лишь массив. Сам массив будет содержать что-то в каждом слоте. Как минимум, вы сохраните значение hashvalue или его значение в этом слоте. В дополнение к этому вы также можете сохранить связанный/скованный список значений, которые столкнулись в этом слоте, или вы можете использовать метод открытой адресации. Вы также можете сохранить указатель или указатели на другие данные, которые вы хотите извлечь из этого слота.

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

uint slotIndex = hashValue % hashTableSize;

Это значение - это слот, в который будет введено значение. В открытой адресации, если слот уже заполнен другим значением hashvalue и/или другими данными, операция модуля снова будет запущена, чтобы найти следующий слот:

slotIndex = (remainder + 1) % hashTableSize;

Я предполагаю, что могут быть другие более продвинутые методы для определения индекса слота, но это общий, который я видел... будет интересоваться любыми другими, которые работают лучше.

При использовании метода модуля, если у вас есть таблица размера 1000, любое значение hash, находящееся между 1 и 1000, войдет в соответствующий слот. Любые отрицательные значения и любые значения, превышающие 1000, будут потенциально конфликтующими значениями слотов. Шансы на это зависят как от вашего метода хэширования, так и от количества общих элементов, которые вы добавляете в хеш-таблицу. Как правило, лучше всего сделать размер хеш-таблицы таким, чтобы общее количество добавленных к нему значений составляло всего около 70% его размера. Если ваша хеш-функция выполняет хорошую работу с равномерным распределением, вы, как правило, сталкиваетесь с очень небольшим количеством конфликтов без кодов/слотов, и она будет работать очень быстро для операций поиска и записи. Если общее количество добавленных значений заранее неизвестно, сделайте хороший прогноз с использованием любых средств, а затем измените размер своей хеш-таблицы, как только количество добавленных элементов достигнет 70% емкости.

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

PS - В С# метод GetHashCode() довольно медленный и приводит к действительным коллизиям значений при множестве условий, которые я тестировал. Для некоторой реальной забавы, создайте свою собственную хэш-функцию и постарайтесь, чтобы она НИКОГДА не сталкивалась с конкретными данными, которые вы хешируете, работает быстрее, чем GetHashCode, и имеет довольно равномерное распределение. Я сделал это, используя long вместо значений hashcode int size, и он неплохо работал на 32 миллионах хеш-значений в хэш-таблице с 0 столкновениями. К сожалению, я не могу использовать код, который принадлежит моему работодателю... но я могу показать, что это возможно для определенных доменов данных. Когда вы можете достичь этого, хеш-таблица ОЧЕНЬ быстро.:)

Ответ 6

Вот как это работает в моем понимании:

Вот пример: изобразите всю таблицу как серию ведер. Предположим, что у вас есть реализация с альфа-числовыми хэш-кодами и для каждой буквы алфавита есть одно ведро. Эта реализация ставит каждый элемент, чей хэш-код начинается с конкретной буквы в соответствующем ведре.

Скажем, у вас есть 200 объектов, но только 15 из них имеют хэш-коды, начинающиеся с буквы "B." Хэш-таблицу нужно будет искать и искать только 15 объектов в ведро "В", а не все 200 объектов.

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

Ответ 7

Короткий и сладкий:

Хэш-таблица обертывает массив, позволяет называть его internalArray. Элементы вставляются в массив таким образом:

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

Иногда два ключа имеют хеш с тем же индексом в массиве, и вы хотите сохранить оба значения. Мне нравится хранить оба значения в одном и том же индексе, который просто кодировать, создавая internalArray массив связанных списков:

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

Итак, если бы я хотел извлечь элемент из своей хэш-таблицы, я мог бы написать:

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

Удалить операции так же просто писать. Как вы можете сказать, вставки, поиск и удаление из нашего массива связанных списков - это почти O (1).

Когда наш innerArray становится слишком полным, возможно, с емкостью около 85%, мы можем изменить размер внутреннего массива и перенести все элементы из старого массива в новый массив.

Ответ 8

Это еще проще.

Хэш-таблица - это не что иное, как массив (обычно sparse one) векторов, которые содержат пары ключ/значение. Максимальный размер этого массива обычно меньше, чем количество элементов в наборе возможных значений для типа данных, хранящихся в хэш-таблице.

Хэш-алгоритм используется для создания индекса в этом массиве на основе значений элемента, который будет храниться в массиве.

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

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

Ответ 9

Вы берете кучу вещей и массив.

Для каждой вещи вы составляете для нее индекс, называемый хешем. Важная вещь в хеше заключается в том, что он "разбрасывает" много; вы не хотите, чтобы две подобные вещи имели похожие хэши.

Вы помещаете свои вещи в массив в позиции, обозначенной хешем. Более чем одно может завершиться при заданном хеше, поэтому вы храните вещи в массивах или что-то еще подходящее, которое мы обычно называем ведром.

Когда вы просматриваете вещи в хеше, вы проходите те же шаги, вычисляя значение хеша, а затем видите, что в ведре в этом месте, и проверяете, что именно вы ищете.

Когда ваше хеширование работает хорошо, и ваш массив достаточно велик, в любом конкретном индексе в массиве будет всего несколько вещей, поэтому вам не придется много смотреть.

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

Ответ 10

Все ответы до сих пор хороши и имеют разные аспекты работы хэш-таблицы. Вот простой пример, который может быть полезен. Допустим, мы хотим сохранить некоторые элементы с строчными алфавитными строками в виде ключей.

Как объяснил Симон, хеш-функция используется для отображения из большого пространства в небольшое пространство. Простая наивная реализация хеш-функции для нашего примера может взять первую букву строки и сопоставить ее с целым числом, поэтому "аллигатор" имеет хэш-код 0, "bee" имеет хэш-код 1, зебра "будет 25 и т.д.

Далее у нас есть массив из 26 ведер (может быть ArrayLists в Java), и мы помещаем элемент в ведро, который соответствует хеш-коду нашего ключа. Если у нас есть более одного элемента, у которого есть ключ, который начинается с той же буквы, у них будет один и тот же хеш-код, поэтому все они будут в ведре для этого хеш-кода, поэтому в ведро должен быть выполнен линейный поиск найдите определенный элемент.

В нашем примере, если бы у нас было всего несколько десятков элементов с ключами, охватывающими алфавит, это сработало бы очень хорошо. Однако, если у нас было миллион элементов или все ключи начинались с "a" или "b", то наша хеш-таблица не была бы идеальной. Чтобы получить лучшую производительность, нам понадобится другая хеш-функция и/или больше ковшей.

Ответ 11

Вот еще один способ взглянуть на него.

Я предполагаю, что вы понимаете концепцию массива A. Это то, что поддерживает операцию индексирования, где вы можете перейти к I-му элементу A [I] за один шаг, независимо от того, насколько велика A.

Итак, например, если вы хотите хранить информацию о группе людей, у всех которых есть разные возрасты, простой способ состоял бы в том, чтобы иметь массив, который достаточно велик, и использовать возраст каждого человека как индекс в массив. В любом случае, вы можете получить доступ к информации любого человека одним шагом.

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

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

Ответ 12

Как вычисляется хэш, обычно не зависит от хэш-таблицы, а от элементов, добавленных к ней. В библиотеках framework/base class, таких как .net и Java, каждый объект имеет метод GetHashCode() (или аналогичный), возвращающий хеш-код для этого объекта. Идеальный алгоритм хеш-кода и точная реализация зависят от данных, представленных в объекте.

Ответ 13

Хэш-таблица полностью работает над тем фактом, что практическое вычисление следует за машиной с произвольным доступом, то есть значение по любому адресу в памяти может быть доступно в O (1) время или постоянное время.

Итак, если у меня есть юниверс ключей (набор всех возможных ключей, которые я могу использовать в приложении, например, номер для студентки, если он имеет 4 цифры, то этот юниверс представляет собой набор чисел от 1 до 9999), и способ сопоставить их с конечным набором чисел размера, я могу выделить память в моей системе, теоретически моя хэш-таблица готова.

Как правило, в приложениях размер юниверса ключей очень большой, чем количество элементов, которые я хочу добавить в хеш-таблицу (я не хочу тратить 1 ГБ памяти на хэш, скажем, 10000 или 100000 целых значений, потому что они 32 бит в двоичном представлении). Итак, мы используем это хеширование. Это своего рода смешанная "математическая" операция, которая отображает мою большую вселенную в небольшой набор значений, которые я могу разместить в памяти. В практических случаях часто место хэш-таблицы имеет один и тот же "порядок" (большой-O) как (количество элементов * размера каждого элемента). Таким образом, мы не теряем много памяти.

Теперь большое множество, сопоставленное с небольшим множеством, отображение должно быть много-к-одному. Таким образом, разные ключи будут выделены в одно и то же пространство ( "несправедливо" ). Есть несколько способов справиться с этим, я просто знаю двух популярных из них:

• Используйте пространство, которое должно быть присвоено значению, в качестве ссылки на связанный список. Этот связанный список сохранит одно или несколько значений, которые будут находиться в одном и том же слоте во многих отображениях. Связанный список также содержит ключи, чтобы помочь тем, кто приходит на поиски. Он, как и многие люди в одной квартире, когда приходит человек доставки, он идет в комнату и спрашивает конкретно этого парня.
• Использовать двойную хэш-функцию в массиве, которая дает одну и ту же последовательность значений каждый раз, а не одно значение. Когда я иду, чтобы сохранить значение, я вижу, свободная или занятая ячейка памяти. Если он свободен, я могу сохранить там свое значение, если он занят, я принимаю следующее значение из последовательности и так далее, пока не найду свободное место, и я сохраню там свое значение. При поиске или возврате значения я возвращаюсь к тому же пути, который задан последовательностью, и в каждом месте запрашивает vaue, если он там, пока я не найду его или не поискаю все возможные местоположения в массиве.

Введение в алгоритмы с помощью CLRS дает очень хорошее представление о теме.

Ответ 14

Для всех, кто ищет язык программирования, вот как это работает. Внутренняя реализация продвинутых хеш-таблиц имеет множество тонкостей и оптимизаций для распределения/освобождения памяти и поиска, но идея верхнего уровня будет практически такой же.

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

где calculate_bucket_from_val() - это функция хеширования, в которой должна произойти вся магия уникальности.

Эмпирическое правило: При заданном значении, которое должно быть вставлено, ведро должно быть УНИКАЛЬНЫМ и ДЕЙСТВИТЕЛЬНЫМ ИЗ ЗНАЧЕНИЯ, которое предполагается для МАГАЗИНА.

Bucket - это любое пространство, в котором хранятся значения, поскольку здесь я сохранил его как индекс массива, но, возможно, это место памяти.

Ответ 15

HashTable не отображает один ключ на множество значений, он отображает один ключ на одно значение. Второй и третий numbers.put("один",...); вызовы не добавляют свои аргументы в какой-то скрытый список, они перезаписывают значение, связанное с ключом "один".

Я предлагаю прочитать больше о цепочке хеш-таблиц. Цепочка - это не способ хранить несколько элементов на ключ; его цель - предотвратить столкновения разных ключей, у которых хеш-коды имеют одинаковый остаток при делении на некоторое значение.

Если вам нужен список целых чисел, связанных с каждым ключом, вы можете сделать это. Вы просто должны сказать Java, что это то, что вы хотите, например,

Hashtable> numbers = new Hashtable>();