Как получить доступ к n-му элементу в словаре или хэше?

Question

У меня есть словарь ключей и значений, например:

{
    fred: 1,
    dave: 2,
    lily: 3
}

Как получить 2-й элемент в словаре - {dave:2} в этом случае?

---

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

Эти вопросы и ответы применяются к словарям, поскольку они реализованы во многих языки. Разные языки используют разные имена для обозначения того, что по сути, та же структура данных - например, они называются хэши в Perl, словари на Python. В Objective-C они являются примерами NSDictionary или NSMutableDictionary классы.

Answer 1

В двух словах, вы не можете - потому что словари неупорядочены коллекции пар ключ / значение. Порядок, в котором вы заполняете словарь не сохраняется в памяти. Вот простой пример на Python:

>>> dict = { 'a': 1, 'b': 2, 'c': 3 }
>>> dict # show the value of dict in memory
{'a': 1, 'c': 3, 'b': 2}

Как видите, словарь инициализируется ключами в порядок a, b, c, печать значения словаря показывает их заказал а, с, б. Даже этот порядок не сохраняется в памяти; когда вы добавляете больше пар ключ / значение в словарь, порядок в Выше выражение будет продолжать меняться.

Почему это?

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

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

Answer 2

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

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