Почему массив Ruby из 1000 пар ключей и значений хэшей всегда находится в определенном порядке?

Question

Скажите, если существует массив из 1000 хэшей, с такими парами, как {:id => 1, :name => 'something', :created_at => '2010-08-18'}

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

(я думал о сопоставлении :id to 10, and :name to 20, and :create_at to 30, а затем сортировать ключи по этим сопоставленным значениям так, чтобы: id был before: name,и предшествует: create_at)

(хеш распечатывается a_hash.each_pair do |k, v| ...)

Answer 1

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

Answer 2

Документация на ruby-doc.org для ruby ​​1.9 (не уверен, что это 1.9.0 или 1.9.1) неверно говорит

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

Но 1.9.1 news говорит

Хэш сохраняет порядок.Он перечисляет свои элементы в порядке, в котором вставлены ключи.

Я посмотрел на ствол рубина (то, что разрабатывается), и он говорит:

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

Изменения в документации произошли в 25 сентября 2009 г. коммит , который исправлял некорректную документацию.

Я не уверен на 100%, что упорядоченное перечисление является частью спецификации ruby ​​1.9.1.Rubyspec будет одним из способов проверки.Но если основная реализация предоставляет контракт, то можно ожидать, что любая другая реализация будет выполнять этот контракт, если в ней явно не указано иное.

Answer 3

Ruby hashmaps (и hashmaps в целом) не имеют подразумеваемого порядка ключей. Однако они реализованы таким образом, что делает получение значения по заданному ключу эффективным (время амортизации O (1)).

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

Answer 4

Почему и на что можно рассчитывать?

Любой хеш будет иметь "естественную сортировку".

«Естественная сортировка» поддерживается либо при вставке каждого элемента, либо перед первым поиском.

Если нет естественной сортировки, возвращающей значение, соответствующее определенному ключу, потребуется исчерпывающий поиск.

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

С другой стороны, если хеш отсортирован в алфавитном порядке по KEY, то двоичный поиск может найти совпадение в сравнении LOG2 (n). (например, 65536 элементов, найденных в 16 сравнениях.)

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

например. В следующей частичной реализации пары ключ / значение сохраняются как объекты в базовом массиве.

myArray[0] = {"b", "Skies"}
myArray[1] = {"c", "dog"}
myArray[2] = {"a", "Jax"}
myArray[3] = {"d", "gone"}
myArray[4] = {"r", "run"}
myArray[5] = {"q", "quit"}

второй массив, к которому разработчик Ruby не имеет доступа , содержит сортировку.

sortArray[0] = 2
sortArray[1] = 0
sortArray[2] = 1
sortArray[3] = 3
sortArray[4] = 4 
sortArray[5] = 5 

Таким образом, внутренне к хеш-объекту

for(i=0 to 5) 
    print myArray[sortArray[i]]

напечатает отсортированный массив.

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

Answer 5

Ruby не гарантирует порядок ключей Hash, хотя Ruby 1.9 сохраняет порядок вставки.

Если вы хотите обрабатывать ключи Hash в определенном, но произвольном порядке, лучше всего создать массивуказав порядок.Таким образом, вы можете иметь массив типа [:id, :name, :create_at].Если вы хотите обработать хэш в, скажем, алфавитном порядке, вы можете просто использовать sort, и он даст вам массив пар ключ-значение в порядке.