powered by simpleCommunicator - 2.0.36     © 2025 Programmizd 02
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Порядок ключей в Dictionary<TKey, TValue>
8 сообщений из 8, страница 1 из 1
Порядок ключей в Dictionary<TKey, TValue>
    #40038026
Сон Веры Павловны
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Казалось бы тема старая, давно разобранная, и ответ здесь только один - в общем случае порядок ключей недетерминирован. Однако на днях выяснилось, что некоторые разработчики считают иначе.
Предыстория. На днях понадобилось порыться в исходниках EPPlus для уяснения некоторых нюансов формирования разметки в потрохах xslx. В процессе наткнулся на следующее.
В составе пакета xslx есть т.н. shared strings table - просто словарик со строками, на которые даются ссылки. Сделано это для предотвращения распухания размера xlsx.
Сам словарик живет в файле sharedStrings.xml в составе пакета, имеет вид
Код: xml
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
<sst xmlns="http://schemas.openxmlformats.org/spreadsheetml/2006/main" count="5853" uniqueCount="5853">
  <si>
    <t>Мама</t>
  </si>
  <si>
    <t>мыла</t>
  </si>
  <si>
    <t>раму</t>
  </si>
  ................
</sst>


Ссылки на строки делаются в файлах содержимого worksheets (sheet1.xml .. sheetN.xml), имеющих вид (в части описания ячеек)
Код: xml
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
<sheetData>
  <row r="1">
    <c r="A1" s="3" t="s">
      <v>0</v>
    </c>
    <c r="B1" s="3" t="s">
      <v>1</v>
    </c>
    <c r="C1" s="3" t="s">
      <v>2</v>
    </c>
  </row>
</sheetData>


Ссылка на строку из словаря - значение тэга v, zero-based индекс узла si в файле sharedStrings.xml. Т.е. порядок следования строк в sharedStrings.xml имеет значение.
Далее. В EPPLus словарь со строками заполняется при сохранении пакета в тот момент, когда формируются файлы листов (sheet1.xml .. sheetN.xml). Делается это вот здесь . Строки сохраняется в обычный Dictionary<>, у которого ключ - сама строка, а значение - internal-класс со служебной информацией (в т.ч. порядковым номером строки в словаре).
После того, как все файлы листов сформированы, словарик считается заполненным, и сериализуется в xml вот здесь . И сериализуется он простым проходом по итератору коллекции ключей словаря, без каких-либо упорядочиваний и сортировок. Т.е. автор библиотеки уверен, что ключи в итераторе следуют в той последовательности, в которой они были добавлены (а эта последовательность важна - см. выше).
Поскольку EPPlus - достаточно серьёзная разработка, за которую сейчас люди платят деньги, то, я думаю, если бы препдположение о следовании ключей в порядке добавления было бы неверным, это где-нибудь уже вылезло, и было пофиксено. Сижу вот, роюсь в документации-форумах, и нигде пока ничего не нахожу в подтверждение, кроме всё того же постулата о недетерминированности порядка.
...
Рейтинг: 0 / 0
Порядок ключей в Dictionary<TKey, TValue>
    #40038035
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну по факту хэш int-ключа будет сам int, поэтому сортировка случайно совпадает, видимо, поэтому глюк нигде не всплыл.
Но это глюк, да, никто не обещал детерминированность. Я и сам иной раз забывал по ключу отсортировать, но вовремя спохватывался.
...
Рейтинг: 0 / 0
Порядок ключей в Dictionary<TKey, TValue>
    #40038064
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
из этого словаря могут строки удаляться? если нет, то строка попав хоть раз в эту коллекцию получает индекс и её порядок не меняется
вообще не сталкивался с такой проблемой, если честно, хоть и с табличкой строк приходилось работать.
...
Рейтинг: 0 / 0
Порядок ключей в Dictionary<TKey, TValue>
    #40038067
Сон Веры Павловны
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Shocker.Pro,

Тем более что там ключ string, а не int. И, тем не менее:
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
const string loremIpsum = "Lorem ipsum dolor sit amet consectetur adipiscing elit sed do eiusmod tempor incididunt ut labore et dolore magna aliqua";
var dic = new Dictionary<string, int>();
var n = 0;
foreach(var s in loremIpsum.Split(' '))
  dic.Add(s, n++);
var sb = new StringBuilder();
foreach (var s in dic.Keys)
  sb.Append(s).Append(" ");
Console.WriteLine(sb.ToString());
Console.WriteLine(loremIpsum.Equals(sb.ToString().Trim(), StringComparison.Ordinal));


Код: plaintext
1.
Lorem ipsum dolor sit amet consectetur adipiscing elit sed do eiusmod tempor incididunt ut labore et dolore magna aliqua
True
...
Рейтинг: 0 / 0
Порядок ключей в Dictionary<TKey, TValue>
    #40038069
Сон Веры Павловны
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Roman Mejtes
из этого словаря могут строки удаляться? если нет, то строка попав хоть раз в эту коллекцию получает индекс и её порядок не меняется

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

Это не проблема, это просто вопрос, почему так.
...
Рейтинг: 0 / 0
Порядок ключей в Dictionary<TKey, TValue>
    #40038072
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сон Веры Павловны
Код: plaintext
Lorem ipsum dolor sit amet consectetur adipiscing elit sed do eiusmod tempor incididunt ut labore et dolore magna aliqua
Насколько я помню, в каком-то из словарей до определенного количества ключей не используется хэш... только не помню, есть ли так в обычном словаре
...
Рейтинг: 0 / 0
Порядок ключей в Dictionary<TKey, TValue>
    #40038073
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сон Веры Павловны
Только это нигде не документировано.
если это будет документировано, но это не позволит менять реализацию, так что всё правильно
...
Рейтинг: 0 / 0
Порядок ключей в Dictionary<TKey, TValue>
    #40038085
Сон Веры Павловны
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Shocker.Pro
Насколько я помню, в каком-то из словарей до определенного количества ключей не используется хэш...

Не тот случай - здесь ключей может быть очень много. Сейчас вот под рукой не особенно большой документ, sharedStrings.xml из него в распакованном виде весит 13 Мб. А если в документе несколько листов (sharedStrings.xml всегда один на весь документ), много колонок, значения строк редко повторяются, то легко может быть и в 5 раз больше.

Shocker.Pro
если это будет документировано, но это не позволит менять реализацию, так что всё правильно

Ну, т.е. автор не особенно правильно делает, используя вот такое недокументированное поведение словаря.
...
Рейтинг: 0 / 0
8 сообщений из 8, страница 1 из 1
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Порядок ключей в Dictionary<TKey, TValue>
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]