Я пытаюсь понять хеш-таблицы - кто-то может объяснить это мне - ясно?

Я хочу понять правильное использование и реализацию хеш-таблиц в php (извините).

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

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

Обзор простой хеш-таблицы

В качестве обновления хеш-таблица - это способ хранения значения под определенным ключом в структуре данных. Например, я могу сохранить значение "a"под ключом 1, а затем получить его, просмотрев ключ1 в хэш-таблице.

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

---------------------------------
|   |   |   |   |   |   |   |   |
---------------------------------
  0   1   2   3   4   5   6   7  

Хэш-функция

Хэш-функции дают вам указатель того, где хранить ваши значения. Довольно простой хеш-функцией для этой таблицы было бы добавить 1 к значению, которое вы хотите сохранить, а затем изменить его на 8 (размер таблицы). Другими словами, ваша хеш-функция(n+1)%8 , где nесть целое число вы хотите сохранить.

Вставки

Если вы хотите вставить значение в эту хеш-таблицу, вы вызываете свою хеш-функцию (в данном случае (n+1)%8) для значения, которое вы хотите вставить, чтобы получить индекс. Например, если мы хотим вставить 14, мы бы вызвали (14 + 1) % 8и получили индекс 7, поэтому мы вставили бы его значение в индекс 7.

---------------------------------
|   |   |   |   |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Аналогично, мы можем вставить 33, 82 и 191 так:

---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Столкновения

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

Итак, логика такова:

1. (2 + 1)% 8 = 3
2. Индекс 3 полон
3. Подключите 3 обратно в нашу хэш-функцию. ( 3 + 1)% 8 = 4 , что пусто.
4. Поместите наше значение в индекс 4 .

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

---------------------------------
|191|   |33 |82 |2  |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

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

---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Если вы помните, (2+1)%8дает нам индекс 3, который взят. Если вы не хотите, чтобы ваша хеш-таблица заполнялась, вы можете использовать каждый индекс таблицы как связанный список и добавлять к списку этот индекс. Поэтому вместо повторного вызова хеш-функции мы просто добавим в список индекс 3:

            -----
            | 2 |
---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Этот список может увеличиться настолько, насколько позволит память. Я могу вставить 18, и он будет просто добавлен к 2:

            -----
            |18 |
            -----
            | 2 |
---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Lookups

Поиск значений в вашей хеш-таблице выполняется быстро, учитывая, что ваша хеш-таблица имеет довольно большой размер. Вы просто вызываете свою хэш-функцию и получаете индекс. Допустим, вы хотите увидеть, есть ли 82 в вашей таблице. Функция поиска вызовет (82+1)%8= 3, и посмотрит на элемент в индексе 3, и вернет его для вас. Если вы посмотрели 16, функция поиска будет выглядеть в индексе1 и увидела, что она не существует.

Поиски тоже должны обрабатывать коллизии!

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

Резюме

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

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

Один (общий) способ сделать это - отсортировать книги по алфавиту. Если ваш заголовок начинается с «G», вы находите область «G», затем ищите вторую букву, например «ö», затем «d», «e», «l», сужая область поиска и т. Д. До тех пор, пока вы не найдете книгу. Однако это может занять много времени, и, кроме того, когда приходят новые книги, иногда требуется реорганизовать макет, чтобы освободить место для новых поступлений.

Это бинарный поиск. Хорошо.

Есть, однако, более быстрый способ сделать это. Допустим, вы перечислили все книжные шкафы и полки, а затем для каждой книги вычислили специальное, мы надеемся, уникальное число, которое сопоставляется с книжным шкафом / полкой, где должна быть найдена книга. Способ вычисления «ключа» не имеет большого значения, поскольку он дает случайное число. Например, вы можете добавить коды символов всех букв в заголовке, а затем разделить их на некоторое простое число (возможно, это не лучший метод, но в любом случае работает).

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

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

PS Извините, что не ответил на ваш вопрос напрямую (напишите хеш-таблицу на PHP), но это детали, и это называется "программирование";)

Насколько мне известно, хеш-таблица в PHP просто реализуется через:

$my_hash = array(
    1 => "Bob",
    2 => "Alice",
    3 => "Jack"
);

Затем вы получаете доступ к данным с помощью вызовов, таких как:

echo $my_hash[2]; // Will echo "Alice"

Вы используете функцию foreach () для перебора содержимого массива.

Лучший способ понять хеш-таблицы - это прочитать что-то вроде http://en.wikipedia.org/wiki/Hash_table , но примерно это сводится к следующему: левой стороной каждой строки внутри этого вызова array () являются ключи , Эти ключи будут проверены на хеш, и в результате получится хеш. Возможно, вы уже видели хэши MD5 или SHA, это выглядит примерно так. Определенная часть этого хеша, обычно первые X символов, но иногда полный хеш, будет использоваться для идентификации так называемых «сегментов», которые являются областями хранения значений (правая часть).

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

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