Хэш-таблица vs. дерево поиска
От: adontz Грузия http://adontz.wordpress.com/
Дата: 24.12.05 11:28
Оценка:
Здравствуйте, Mab, Вы писали:

Mab>Очень странная идея. Зачем сортировать хеши?

A>>Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net
Mab>Это не верно. Есть принципально два способа огранизации коллекций, поддерживающих быстрый поиск.

Ты внимательно почитай о чём речь. Мы говорили не о коллекциях, а об операторе switch по любым объектам. Чтобы это было реализовано не абы как, а качественно, из констант после case надо построить двочное дерево поиска. А для этого надо сами эти константы упорядочить. Иначе switch ничем не будет отличаться от последовательности if, а нам такой switch не нужен!

02.01.06 16:47: Ветка выделена из темы Чего не хватает в C#?
Автор: Кирилл Осенков
Дата: 07.12.05
— VladD2
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[9]: Хэш-таблица vs. дерево поиска
От: WolfHound  
Дата: 24.12.05 11:34
Оценка:
Здравствуйте, adontz, Вы писали:

A>Ты внимательно почитай о чём речь. Мы говорили не о коллекциях, а об операторе switch по любым объектам. Чтобы это было реализовано не абы как, а качественно, из констант после case надо построить двочное дерево поиска. А для этого надо сами эти константы упорядочить. Иначе switch ничем не будет отличаться от последовательности if, а нам такой switch не нужен!

Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[9]: Хэш-таблица vs. дерево поиска
От: Mab Россия http://shade.msu.ru/~mab
Дата: 24.12.05 11:34
Оценка: +1
Здравствуйте, adontz, Вы писали:

A>Здравствуйте, Mab, Вы писали:


Mab>>Очень странная идея. Зачем сортировать хеши?

A>>>Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net
Mab>>Это не верно. Есть принципально два способа огранизации коллекций, поддерживающих быстрый поиск.

A>Ты внимательно почитай о чём речь. Мы говорили не о коллекциях, а об операторе switch по любым объектам.

Ух ты Как далеко дискуссия зашла...

A>Чтобы это было реализовано не абы как, а качественно, из констант после case надо построить двочное дерево поиска. А для этого надо сами эти константы упорядочить.

Совершенно не обязательно. В switch стоит задача идентификации объекта, а не введения линейного порядка.

A>Иначе switch ничем не будет отличаться от последовательности if, а нам такой switch не нужен!

Почему же? Насколько понимаю, при большом количестве вариантов сейчас switch создает хештаблицу, после чего выбор нужного варианта делается запросом к ней. Этот подход эффективнее, чем бинарный поиск.
Re[10]: Хэш-таблица vs. дерево поиска
От: adontz Грузия http://adontz.wordpress.com/
Дата: 24.12.05 11:37
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице?


Ну предложи что-то своё. Только так, чтобы работало
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[11]: Хэш-таблица vs. дерево поиска
От: WolfHound  
Дата: 24.12.05 11:50
Оценка: +1 :)
Здравствуйте, adontz, Вы писали:

WH>>Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице?

A>Ну предложи что-то своё. Только так, чтобы работало
А что хеш таблица уже не работает?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[12]: Хэш-таблица vs. дерево поиска
От: adontz Грузия http://adontz.wordpress.com/
Дата: 24.12.05 13:18
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, adontz, Вы писали:


WH>>>Почему такой стериотип что switch должен быть построен на дереве, а не на хеш таблице?

A>>Ну предложи что-то своё. Только так, чтобы работало
WH>А что хеш таблица уже не работает?

Хеш ключа это индекс в хеш-таблице (обычный массив), значения которой это списки пар (ключ, значение). А что у нас возвращает замечательная функция GetHashCode()? А она у нас возвращает int, 32битное число. Размер массива который бы индексировался таким числом просто огромен, значительно превышает не только средний, но и максимальный объём памяти (который обычно 4Гб, но даже в 64 это всё не влезет).
Поэтому, ради экономии памяти, применяются разного рода компромиссные решения. В частности в MS реализации hash_map используется массив пар key-value размера 2^N, а сам хеш маскируется до младших N бит. Как результат хеш-функция не просто должна по возможности возвращать разные значения для разных аргументов, но и для случайных аргументов значения всех бит должны быть равновероятными и независимыми. Влад же (и судя по всему ты тоже) мне доказывает, что написание такой функции, это пара пустяков, а оператора < большая проблема.
Теперь вопрос — насколько хороша завязаная на хеш реализация? Правильный ответ — если хеш функция не удовлетворяет требованиям выше, то просто ужасна. Скорее всего после равенства хешей будет несколько проверок на равенство объектов и про average O(1) можно забыть, а про worsest O(N) вспомнить. И спомнить насильно.
А теперь домашнее задание
class Path
{
    public char Drive;
    public string Directory;
    public string Filename;
    public int Attributes;

    public override int GetHashCode()
    {
        return
        /* Что тут надо написать, чтобы значения всех битов были равновероятны и независимы?
           Причём не в теории, где Drive от 0 до 255, а на практике. */;
    }
}
Подумай и над тем сколько вообще программистов знают в теории как писать такие функции, не говоря уже о практике. А вот оператор < это просто и понятно. Таким образом switch для произвольных объектов на основе хешей на практике не имеет никаких шансов быть сколько-нибудь оптимальным.
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[10]: Хэш-таблица vs. дерево поиска
От: adontz Грузия http://adontz.wordpress.com/
Дата: 24.12.05 13:23
Оценка:
Здравствуйте, Mab, Вы писали:

Mab>Почему же? Насколько понимаю, при большом количестве вариантов сейчас switch создает хештаблицу, после чего выбор нужного варианта делается запросом к ней. Этот подход эффективнее, чем бинарный поиск.


Да, но только при условии, что хеш-функция нормальная (как я уже говорил, для случайного аргумента значения бит независимы и равновероятны). А для произвольных объектов написанных неизвестно кем это далеко не так
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[11]: Хэш-таблица vs. дерево поиска
От: Mab Россия http://shade.msu.ru/~mab
Дата: 24.12.05 13:29
Оценка: +2
Здравствуйте, adontz, Вы писали:
A>Да, но только при условии, что хеш-функция нормальная (как я уже говорил, для случайного аргумента значения бит независимы и равновероятны). А для произвольных объектов написанных неизвестно кем это далеко не так
Роман, а ты пробовал сам на практике хешфункции? Потому что я -- да, и опыт их использования положительный (по сравнению с деревьями поиска достигалось ускорение) Тот факт, что написав return 0; в GetHashCode можно убить производительность, ни у кого сомнений не вызывает. Только я бы поостерегся делать столь сильные выводы из этого.
Re[12]: Хэш-таблица vs. дерево поиска
От: adontz Грузия http://adontz.wordpress.com/
Дата: 24.12.05 13:40
Оценка:
Здравствуйте, Mab, Вы писали:

Mab>Роман, а ты пробовал сам на практике хешфункции? Потому что я -- да, и опыт их использования положительный (по сравнению с деревьями поиска достигалось ускорение)


С первой попытки? Иил всё таки игрался с хеш функцией? А может написал с первого раза, но до того прочёл кучу умных книжек?

Mab>Тот факт, что написав return 0; в GetHashCode можно убить производительность, ни у кого сомнений не вызывает. Только я бы поостерегся делать столь сильные выводы из этого.


Я говорю о другом. Есть множество программистов, которые пишут классы, которые потенциально могут использоваться в операторе switch.
Какой процент из них напишет сколько-нибудь разумную хеш-функцию? ИМХО если 10% то это будет уже просто замечательно. Речь ведь не о тебе или мне, а о решении, которое выйдет боком. Я напишу switch, а он будет жутко медленный из-за какого-то #$@%.
А вот в VC++ switch занимает от силы log(N) операций. И это гарантированно, а тут зависит от направления ветра во вторник.
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[13]: Хэш-таблица vs. дерево поиска
От: Mab Россия http://shade.msu.ru/~mab
Дата: 24.12.05 14:07
Оценка: 22 (1) +2
Здравствуйте, adontz, Вы писали:

A>С первой попытки? Иил всё таки игрался с хеш функцией?

Честно говоря не знаю, с какой попытки, т.к. занимаюсь алгоритмами уже больше десяти лет. И ошибок за это время в них успал сделать кучу Конечно, почти наверняка сначала была книжка Но не могу припомнить, чтобы хоть раз возникал bottleneck в производительности именно из-за хештаблицы (а ничего сложнее, чем полином по модулю, циклические сдвиги и xor-ы я не использовал).

A>Я говорю о другом. Есть множество программистов, которые пишут классы, которые потенциально могут использоваться в операторе switch.

A>Какой процент из них напишет сколько-нибудь разумную хеш-функцию?
В случае, если класс не определяет deep-семантики для равенства (т.е. равенство -- это равенство ссылок), то соответвующий GetHashCode из object обеспечивает замечательное распределение, т.к. вычисляется на основе sync block index, который чуть ли не уникален в пределах домена.

Если deep-семантика есть, то простой xor хешей компонент с циклическим сдвигом меня всегда выручал.

A>А вот в VC++ switch занимает от силы log(N) операций. И это гарантированно, а тут зависит от направления ветра во вторник.

Все-таки не нужно выдавать желаемое за действительно. VC++ свитч не может быть применен к произвольным классам. И в C# тоже не может, так что ничья.

Спору нет -- если хочешь гарантий производительности, то хеширование -- не твой метод. Но тогда придется вводить линейный порядок, а это тоже код, который нужно написать. И, кстати, что неприятно: ошибка в таком коде может обернуться кошмарной отладкой. Тот же std::set ничего не гарантирует, если предикат сравенения неправильный.

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

Так что бесплатный сыр...

Кстати, вот еще одно наблюдение на эту тему. В managed-средах вроде .NET и Java нет способа установить линейный порядок на объектах (в отличие от C++, где адрес служит уникальным идентификатором). Так что без хеширования ты вряд ли сможешь написать тот же Set<object>. Соответственно, нельзя будет организовать коллекцию объектов, если они первоначально не предназначались для этого (скажем, не реализуют IComparable<T>).
Re[13]: Хэш-таблица vs. дерево поиска
От: WolfHound  
Дата: 24.12.05 14:56
Оценка: +1
Здравствуйте, adontz, Вы писали:

A>Поэтому, ради экономии памяти, применяются разного рода компромиссные решения. В частности в MS реализации hash_map используется массив пар key-value размера 2^N, а сам хеш маскируется до младших N бит. Как результат хеш-функция не просто должна по возможности возвращать разные значения для разных аргументов, но и для случайных аргументов значения всех бит должны быть равновероятными и независимыми. Влад же (и судя по всему ты тоже) мне доказывает, что написание такой функции, это пара пустяков, а оператора < большая проблема.

Я не знаю что там в STL от MS он как извесно отстой. Но в .NET используются простые числа.
А написать хеш так чтобы он плохо работал на простых числах это не просто.
Ну разве что так
    public override int GetHashCode()
    {
        return 0;
    }

Других идей что-то в голову не приходит
A>Теперь вопрос — насколько хороша завязаная на хеш реализация? Правильный ответ — если хеш функция не удовлетворяет требованиям выше, то просто ужасна.
А если в оператор < какойнибудь индус вставит Sleep(1000)?
A>Скорее всего после равенства хешей будет несколько проверок на равенство объектов и про average O(1) можно забыть, а про worsest O(N) вспомнить. И спомнить насильно.
A>А теперь домашнее задание
Вот только не надо мне тут экзамины устраивать.
А вобще обычно както так
class Path
{
    public char Drive;
    public string Directory;
    public string Filename;
    public int Attributes;

    public override int GetHashCode()
    {
        int hash = 0;
        hash ^= Drive.GetHashCode();
        if (Directory != null)
            hash ^= Directory.GetHashCode();
        if (Filename != null)
            hash ^= Filename.GetHashCode();
        hash ^= Attributes.GetHashCode();
        return hash;
    }

    public override bool Equals(object obj)
    {
        Path path = obj as Path;
        if (path == null)
            return false;
        if (Drive != path.Drive)
            return false;
        if (Directory != path.Directory)
            return false;
        if (Filename != path.Filename)
            return false;
        if (Attributes != path.Attributes)
            return false;
        return true;
    }
}

Если не хватает производительности (что в моей практике было только один раз когда я писал бинарный diff для файлов болие 4Г) можно и поизвращаться.
И вобще вот тебе домашние задание напиши оператор < для класса StateSet
Автор: WolfHound
Дата: 05.08.05
.
A>Подумай и над тем сколько вообще программистов знают в теории как писать такие функции, не говоря уже о практике.
А сколько программистов могут написать корректный Less?
A>А вот оператор < это просто и понятно.
    public bool Less(Path path)
    {
        if (path == null)
            return false;
        if (Drive < path.Drive)
            return true;
        if (Drive > path.Drive)
            return false;
        if (Directory < path.Directory)
            return true;
        if (Directory > path.Directory)
            return false;
        if (Filename < path.Filename)
            return true;
        if (Filename > path.Filename)
            return false;
        if (Attributes < path.Attributes)
            return true;
        if (Attributes > path.Attributes)
            return false;
        return false;
    }

ЭТО просто и понятно?
A>Таким образом switch для произвольных объектов на основе хешей на практике не имеет никаких шансов быть сколько-нибудь оптимальным.
Каким таким образом? Я что-то не понял.
Ты вобще на практике использовал хеш-таблици?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[13]: Хэш-таблица vs. дерево поиска
От: WolfHound  
Дата: 24.12.05 15:01
Оценка: +1
Здравствуйте, adontz, Вы писали:

Кстати чуть не забыл... а как при помощи оператора < хранить в коллекции объекты разных типов. Я конечно понимаю что это попахивает извращением но всеже?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[14]: Хэш-таблица vs. дерево поиска
От: Cyberax Марс  
Дата: 24.12.05 15:08
Оценка:
WolfHound wrote:
> Кстати чуть не забыл... а как при помощи оператора < хранить в коллекции
> объекты разных типов. Я конечно понимаю что это попахивает извращением
> но всеже?
Сначала сравнивать типы объектов (можно тупо сравнивать имена классов),
при совпадении типов — использовать оператор < для нужного типа.

--
С уважением,
Alex Besogonov (alexy@izh.com)
Posted via RSDN NNTP Server 2.0
Sapienti sat!
Re[14]: Хэш-таблица vs. дерево поиска
От: adontz Грузия http://adontz.wordpress.com/
Дата: 24.12.05 17:08
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Я не знаю что там в STL от MS он как извесно отстой.


Давай без огульных оскорблений. Тот STL что идёт с VS к MS не имеет прямого отношения. Кроме того, раз уж в этом hash_map отстой, ты уж покажи другой, тот который не отстой Надо же с чем-либо сравнивать.

WH>Но в .NET используются простые числа.


Откуда они берутся? Как назначаются? Кроме того проблема-то, если ты не заметил, в вычислении хеша от пользовательских классов, а не библиотечных.

WH>Других идей что-то в голову не приходит


Запросто
class A
{
 private string _s1;
 private string _s2;

 public override int GetHashCode()
 {
  return _s1.GetHashCode() ^ _s2.GetHashCode();
 }
}

А по логике работы _s1 и _s2 часто равны. Этого конечно не будет каждый раз, но когда случится, причины тормозов найти будет очень трудно.

A>>Теперь вопрос — насколько хороша завязаная на хеш реализация? Правильный ответ — если хеш функция не удовлетворяет требованиям выше, то просто ужасна.

WH>А если в оператор < какойнибудь индус вставит Sleep(1000)?

А почему бы не вставить Sleep(1000) в вычисление GetHashCode()? Какие-то ну очень неубедительные аргументы. Я бы вставил 17 смайликов со своей стороны, но я не такой.

WH>И вобще вот тебе домашние задание напиши оператор < для класса StateSet
Автор: WolfHound
Дата: 05.08.05
.


Hashtable помешает и правильно. Классы реализующие IDictionary нельзя и сериализовать. В том, что StateSet нельзя будет использовать в операторе switch для меня нет ничего удивительного.

WH>
WH>    public bool Less(Path path)
WH>    {
WH>        if (path == null)
WH>            return false;
WH>        if (Drive < path.Drive)
WH>            return true;
WH>        if (Drive > path.Drive)
WH>            return false;
WH>        if (Directory < path.Directory)
WH>            return true;
WH>        if (Directory > path.Directory)
WH>            return false;
WH>        if (Filename < path.Filename)
WH>            return true;
WH>        if (Filename > path.Filename)
WH>            return false;
WH>        if (Attributes < path.Attributes)
WH>            return true;
WH>        if (Attributes > path.Attributes)
WH>            return false;
WH>        return false;
WH>    }
WH>

WH>ЭТО просто и понятно?

Мне вполне понятно. По крайней мере я точно знаю что делать если какое-либо поле добавится или убавится. Это легко поддерживаемый код. Есть опасность, что после вставки нового поля оно не будет учтено, но такая же опасность есть и с GetHashCode().

A>>Таким образом switch для произвольных объектов на основе хешей на практике не имеет никаких шансов быть сколько-нибудь оптимальным.

WH>Каким таким образом? Я что-то не понял.

В теории всё замечательно, но на практике написание хороших хеш-функций это проблема.

WH>Ты вобще на практике использовал хеш-таблици?


Ну вообще улётный аргумент. И в каждую вставлял Sleep(1000)
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[15]: Хэш-таблица vs. дерево поиска
От: adontz Грузия http://adontz.wordpress.com/
Дата: 24.12.05 17:09
Оценка: +2
Здравствуйте, Cyberax, Вы писали:

C>Сначала сравнивать типы объектов (можно тупо сравнивать имена классов),

C>при совпадении типов — использовать оператор < для нужного типа.

Сравнивать типы, если равны, то значения.
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[15]: Хэш-таблица vs. дерево поиска
От: WolfHound  
Дата: 24.12.05 17:30
Оценка:
Здравствуйте, adontz, Вы писали:

WH>>И вобще вот тебе домашние задание напиши оператор < для класса StateSet
Автор: WolfHound
Дата: 05.08.05
.

A>Hashtable помешает и правильно. Классы реализующие IDictionary нельзя и сериализовать. В том, что StateSet нельзя будет использовать в операторе switch для меня нет ничего удивительного.
1)Причем тут сериализация?
2)Hashtable прекрасно сериализуется. Учи матчасть.
3)Может ты всетки определишь отношение порядка для StateSet? Или слабо?
А если слабо то больше не делай заявлений типа

Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net

... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[13]: Хэш-таблица vs. дерево поиска
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 24.12.05 18:00
Оценка:
Здравствуйте, adontz, Вы писали:

A>
A>class Path
A>{
A>    public char Drive;
A>    public string Directory;
A>    public string Filename;
A>    public int Attributes;

A>    public override int GetHashCode()
A>    {
A>        return
A>        /* Что тут надо написать, чтобы значения всех битов были равновероятны и независимы?
A>           Причём не в теории, где Drive от 0 до 255, а на практике. */;
A>    }
A>}
A>
Подумай и над тем сколько вообще программистов знают в теории как писать такие функции, не говоря уже о практике.


На практике все очень просто — дефолтная реализация GetHashCode() прекрасно для switch подходит.
... << RSDN@Home 1.2.0 alpha rev. 624 on Windows XP 5.1.2600.131072>>
AVK Blog
Re[16]: Хэш-таблица vs. дерево поиска
От: adontz Грузия http://adontz.wordpress.com/
Дата: 24.12.05 19:26
Оценка: -1 :)
Здравствуйте, WolfHound, Вы писали:

WH>1)Причем тут сериализация?


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

WH>2)Hashtable прекрасно сериализуется. Учи матчасть.


Я рыдаю.
Друг, ты хоть с документацией сверяйся, а потом говори, если так не помнишь

public class A
{
    [XmlElement("ht")]
    public Hashtable _ht = new Hashtable();
    
    public A()
    {
        _ht.Add(1, "a");
        _ht.Add(2, "b");
        _ht.Add(3, "c");
    }
}

class Program
{
    static void Main(string[] args)
    {
        /*
        В этой строке получаем исключение.
        Cannot serialize member A._ht of type System.Collections.Hashtable, because it implements IDictionary.
        При использовании Dictionary<int, string> ситуация аналогичная.
        */
        XmlSerializer xs = new XmlSerializer(typeof(A));


        /* Сюда уже не доходит, я просто для полноты картины написал этот код */
        A a = new A();
        
        using (TextWriter tw = File.CreateText("test.xml"))
        {
            xs.Serialize(tw, a);
            tw.Close();
        }
    }
}


WH>3)Может ты всетки определишь отношение порядка для StateSet? Или слабо?


Что значит слабо? Есть инструмент — оператор switch и есть множество классов которые в нём можно использовать. Классы реализующие интерфейс IDictionary в это множество не входят. Не надо доводить до маразма. И уж точно аргументация "слабо", "не слабо" не привносит в дискуссию элементы интеллекта.

WH>А если слабо то больше не делай заявлений типа

WH>

Вобщем "operator <" это проверенное временем решение, а GetHashCode() приблуда .Net


Вобщем все аргументы против "operator <" свелись к тому что
  1. Индусы пишут в "operator <" вызов Sleep(1000); и поэтому он медленный
  2. Роме слабо реализовать этот оператор для класса StateSet. Правда он в операторе switch представляется с трудом, но это не важно.
Очень интересно, но совершенно не убедительно.
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[14]: Хэш-таблица vs. дерево поиска
От: adontz Грузия http://adontz.wordpress.com/
Дата: 24.12.05 19:36
Оценка: +1
Здравствуйте, AndrewVK, Вы писали:

AVK>На практике все очень просто — дефолтная реализация GetHashCode() прекрасно для switch подходит.


Так ли уж?

public class A
{
    public int data = 3;
        
    public A()
    {
    }
}

A a1 = new A();
A a2 = new A();
            
int h1 = a1.GetHashCode();
int h2 = a2.GetHashCode();


Как нетрудно убедиться h1 != h2. А вот с моей точки зрения объекты равны, потому что у обоих поле data = 3, а других полей нет.
Так что дефолтная реализация вообще не подходит. Надо каждый раз писат свою. И как я уже показал, xor от хешей всех полей не лучшее решение.
A journey of a thousand miles must begin with a single step © Lau Tsu
Re[17]: Хэш-таблица vs. дерево поиска
От: Mab Россия http://shade.msu.ru/~mab
Дата: 24.12.05 19:38
Оценка:
Здравствуйте, adontz, Вы писали:

A>Друг, ты хоть с документацией сверяйся, а потом говори, если так не помнишь

XmlSerializer не умеет работать с IDictionary. Только непонятно, при чем тут это...? Возьми BinaryFormatter, он замечательно сериализует твой класс.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.