Как работает хеш-таблица?

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

Вот объяснение с точки зрения непрофессионала.

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

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

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

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

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

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

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

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

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

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

Хорошо, вот как работает хеш-таблица.

Далее следует технический материал.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

вместо использования возраста.

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

вместо использования возраста.

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

All of the answers so far are good, and get at different aspects of how a hashtable works. Here is a simple example that might be helpful. Lets say we want to store some items with lower case alphabetic strings as a keys.

As simon explained, the hash function is used to map from a large space to a small space. A simple, naive implementation of a hash function for our example could take the first letter of the string, and map it to an integer, so "alligator" has a hash code of 0, "bee" has a hash code of 1, "zebra" would be 25, etc.

Next we have an array of 26 buckets (could be ArrayLists in Java), and we put the item in the bucket that matches the hash code of our key. If we have more than one item that has a key that begins with the same letter, they will have the same hash code, so would all go in the bucket for that hash code so a linear search would have to be made in the bucket to find a particular item.

In our example, if we just had a few dozen items with keys spanning the alphabet, it would work very well. However, if we had a million items or all the keys all started with 'a' or 'b', then our hash table would not be ideal. To get better performance, we would need a different hash function and/or more buckets.

Это даже проще, чем это.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Когда ваше хеширование работает хорошо, а массив достаточно большой,

Коротко и приятно:

Хеш-таблица оборачивает массив, назовем его 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).

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

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

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

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

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

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

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

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

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

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

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

Есть много схем и приемов, чтобы сделать эту работу лучше, но это основы.

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

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

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

Есть много схем и приемов, чтобы сделать эту работу лучше, но это основы.

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

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

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

Есть много схем и приемов, чтобы сделать эту работу лучше, но это основы.

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

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

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

Есть много схем и приемов, чтобы сделать эту работу лучше, но это основы.

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

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

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

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

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

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

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

Есть много схем и приемов, чтобы сделать эту работу лучше, но это основы.

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

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

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

Есть много схем и приемов, чтобы сделать эту работу лучше, но это основы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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

---

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

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

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

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

uint slotIndex = hashValue % hashTableSize;

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

slotIndex = (remainder + 1) % hashTableSize;

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

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

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

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