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

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

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

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

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

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


dictionary hashmap language-agnostic
person Simon Whitaker    schedule 08.01.2011    source источник
comment
Не обязательно плохая идея, но см. Часто задаваемые вопросы: также совершенно нормально задать свой вопрос и ответить на него, пока вы притворяетесь, что re on Jeopardy: сформулируйте это в форме вопроса.   -  person Cody Gray    schedule 08.01.2011
comment
А, спасибо, Коди, я перефразирую   -  person Simon Whitaker    schedule 08.01.2011

Ответы (2)


arrow_upward
13
arrow_downward

Короче говоря, вы не можете, потому что словари представляют собой неупорядоченные наборы пар ключ/значение. Порядок заполнения словаря не сохраняется в памяти. Вот простой пример на 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, при выводе значения словаря они отображаются в порядке a, c, b. Даже этот порядок не сохраняется в памяти; по мере того, как вы добавляете в словарь новые пары ключ/значение, порядок в приведенном выше выражении будет продолжать меняться.

Почему это?

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

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

arrow_upward
1
arrow_downward

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

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

  • sort(dict), а затем получить n-й элемент этого нового отсортированного словаря. Это будет создавать один и тот же n-й элемент словаря каждый раз, даже если базовый массив растет.
  • enumerate( dict ) и получить n-й ключ в словаре
person nsamuel    schedule 20.06.2014