How to become an author
Search
Write a publication
Pull to refresh

Comments 29

каждый поток имеет свой собственный генератор для хэш-кодов, так что мы не можем попасть в ситуацию, где два потока последовательно генерируют одинаковый хэш-код.
Таки в коде по-английски написано иное: «… ситуацию, где два потока устойчиво генерируют одинаковые хэш-коды». Ещё точнее было бы сказать – ситуация, когда совпадут две последовательности хэш-кодов, генерируемые двумя разными потоками (не обязательно в одно и то же время).

А однократное совпадение хэш-кодов в двух потоках, очевидно, возможно. Причём эти два события могут произойти и «последовательно» (с точки зрения физического времени).
This comment wasn’t rated yet0
CLR выбирает первое поле структуры, на основание которого и создает хеш-код. Это поле по возможности должно быть неизменяемым, например, иметь тип string, иначе при его изменении хеш-код будет так же меняться, и мы не сможем уже найти нашу структуру в хеш-таблице, если она использовалась в качестве ключа. Получается, если первое поле структуры будет изменяемым, то это ломает стандартную логику метода GetHashCode.
Когда изменяем содержимое структуры, её хэш-код как правило должен измениться, неправда ли.

Абзац в коде по-видимому утверждает, что нельзя пользоваться каким-либо полем из объекта‑типа (объекта типа System.Type), поскольку поле может оказаться изменяемым. И тогда хэш-значение изменялось бы из-за каких-то процессов в объекте‑типе, а не из-за изменения содержимого структуры.

структуры должны быть неизменяемыми.
Поржал
Total votes 3: ↑2 and ↓1+1
>>Когда изменяем содержимое структуры, её хэш-код как правило должен измениться, неправда ли.
Так в том то и дело, что хэш не изменится при изменении остальных полей.
This comment wasn’t rated yet0
Это конечно плохо. Но по-моему автор здесь хочет сказать нечто обратное: что первое поле (а лучше все поля) в структуре должно быть объявлено как readonly. Чтобы хэш-код структуры не мог измениться. Якобы изменяемая структура может иметь проблемы с хэш-таблицами.
This comment wasn’t rated yet0
Автор ничего не говорил о полях только для чтения (readonly). Я сказал, чтобы по возможности первое поле имело неизменяемый тип.
Total votes 1: ↑1 and ↓0+1
Коллега, что такое неизменяемый тип? Тип, в котором все поля объявлены как readonly (а также тип System.String) или что?
Total votes 4: ↑1 and ↓3-2
Тип DateTime неизменяем это не значит, что его поля помечены ключевым словом readonly. Если поле помечено ключевым словом readonly это не значит, что нельзя поменять его свойства, это значит просто ссылку на него нельзя поменять.
Неизменяемый тип в моем понимание это тип который не предоставляет возможности менять свои свойства как DateTime, например.
Total votes 4: ↑3 and ↓1+2
class Program
{
    struct Test
    {
        public DateTime  Field;
    }

    static void Main()
    {
        Test v = new Test(){ Field = DateTime.Now};

        Console.WriteLine( "{0}", v.GetHashCode());  // Одно значение

        v.Field = DateTime.Today;

        Console.WriteLine( "{0}", v.GetHashCode());  // Другое значение
    }
}

Неизменяемый тип не помог.
Total votes 5: ↑0 and ↓5-5
Почитайте про immutable структуры
Total votes 6: ↑5 and ↓1+4
Да, неизменяемая структура – известный приём. Но в этой ветке речь о другом.

В своей статье timyrik20 сказал, что, если структуру используем в качестве ключа, то хэш‑код структуры должен быть неизменяемым. Это, очевидно, не так. Вот ниже пояснение.

Кроме того, в пылу полемики timyrik20 сказал совсем странное: для неизменяемости хэш‑кода нужно, чтоб тип первого поля в структуре был неизменяемым, но объявлять поле как readonly не требуется.

Поэтому я и попросил его пояснить, что вообще такое неизменяемый тип в его понимании.

Пример кода демонстрирует, что хэш-код структуры изменяем, хотя тип поля таков, как предлагал timyrik20.
This comment wasn’t rated yet0
В общем случае хэш-код как раз должен быть неизменяемым после инициализации ключа, т. к. реализации таблиц могут быть всякие. В частном же — опять у себя увидел неточность, спасибо — почти всегда все хорошо для стандартных коллекций. А вот оно почти:
void Main()
{    
	var key1 = new Key{
                             RefField = new Reference {InnerField = 5},
                             ValueField = 3
              };
	SetKey(key1);
	"Before change".Dump();
	ShowSetKeyHashCode();
	key1.ValueField = 3;
	"After value field change".Dump();
	ShowSetKeyHashCode();
	key1.RefField.InnerField = 8;
	"After reference field change".Dump();
	ShowSetKeyHashCode();	
}

private Key _setKey;

void SetKey(Key key)
{
   _setKey = key;
}

void ShowSetKeyHashCode()
{
   ShowKeyHashCode(_setKey);
}

void ShowKeyHashCode(Key key)
{
   string.Format("Val:{0}, ref: {1}, hash: {2}",key.ValueField,key.RefField.InnerField,key.GetHashCode()).Dump();   
}

class Reference
{
   public int InnerField;
   public override int GetHashCode()
   {
      return InnerField;
   }
}

struct Key
{
   public Reference RefField;
   public int ValueField; 
}

Мы инициализируем у структуры Key поле RefField и отдаем эту структуру в качестве ключа. Несмотря на то, что в стандартных реализациях коллекций мы не сможем достучаться до непосредственно значения ключа типа Key (всегда будем получать копию), поменять значение поля Field у известного нам объекта типа Reference мы можем. Соответственно, сохраненный нами в коллекции ключ будет иметь не тот хэш-код, что при занесении в коллекцию, что приведет к невозможности корректного поиска этого ключа.
И это именно та ситуация, где поле типа Reference должно быть либо immutable (readonly не спасет), либо value-type.
В нашем случае спасает, например, если поменять поля в структуре Key местами. Попробуйте.
This comment wasn’t rated yet0
В общем случае хэш-код как раз должен быть неизменяемым после инициализации ключа, т. к. реализации таблиц могут быть всякие
Пожалуйста, обоснуйте как-нибудь. Какой такой должна быть хэш-таблица, чтобы стала проблемой изменяемая структура в качестве ключа?

у структуры Key поле RefField
Хорошо, пусть так. А как в этом случае мы относимся к такому коду:
Key key2 = key1;
key1.RefField.InnerField = 8;

Вариант 1. Нельзя изменять содержимое Reference сразу в двух объектах типа Key. Код компилироваться не должен бы.

Тогда действительно тип Reference должен быть неизменяемым. Но это никак не связано с хэш-кодами. Неизменяемость Reference требуется и без применения хэш‑таблиц.

Вариант 2. Код приемлемый. Да, несколько Key ссылаются на один Reference и этот Reference изменяем (живёт какой‑то своей жизнью).

Но такой объект (типа Reference) не должен бы переопределять метод GetHashCode. Лучше использовать базовый GetHashCode.

И даже если переопределяет, выход есть: переопределить Key.GetHashCode, так чтобы он вовсе не использовал Reference или использовал только его неизменяемые поля, а если таковых нет, то добавить, например, неизменяемое поле Reference.Id.
This comment wasn’t rated yet0
Какой такой должна быть хэш-таблица, чтобы стала проблемой изменяемая структура в качестве ключа?

Например, предоставляющей исходный массив этих ключей (не спрашивайте зачем, случае разные бывают).
Вариант 1.

Я не очень понял, зачем эти варианты. Речь идет о минимализации возможностей прострелить себе ногу. С точки зрения .NET ситуация со структурами, ссылающимися на классы, а тем более реализация своего хэш-кода для класса — вполне возможные вещи.
И чтобы другие разработчики, не знакомые с тонкостями реализации и не знающие, что «нельзя переопределять у этого класса хэш-код, а то в другом месте коллекция упадет», не стреляли по ногам, предлагается политика, позволяющая обезопаситься в этом и других случаях.
Легко ответить на вопросы, зачем переопределять хэш-код и зачем передавать структуру как ключ, но на вопрос зачем передавать как ключ изменяемую структуру — гораздо сложнее.
This comment wasn’t rated yet0
Например, предоставляющей исходный массив этих ключей
Тогда появляется возможность присвоить значение целиком элементу массива. Неизменяемость типа ключа не спасает.

предлагается политика, позволяющая обезопаситься
А вот есть политика лучше: структура должна переопределить GetHashCode. Тем более что умолчательный GetHashCode неказист – чреват плохим распределением хэш-кодов. А написать переопределение просто (ниже).

на вопрос зачем передавать как ключ изменяемую структуру — гораздо сложнее.
Без проблем.

Векторные изображения. Отрезок в составе изображения:
struct Segment
{
    Image  OwningImage;  // Ссылочный тип.
    int  X1, Y1;
    int  X2, Y2;

    ... // Конструктор копирования.
}

Хотим отрезок seg2 такой же как seg1, но первый конец сдвинуть на 10 точек.
Segment seg2 = new Segment( seg1){ X1 = seg1.X1 + 10,};

А если сделать структуру неизменяемой, придётся так:
Segment seg2 = new Segment( seg1.OwningImage, seg1.X1 + 10, seg1.Y1, seg1.X2, seg1.Y2);
Читабельность хуже плюс шанс ошибиться в порядке аргументов. Либо добавлять вспомогательный метод CloneWithMovedEdge1.
This comment wasn’t rated yet0
Поправка: пропустил public в определениях полей в структуре Segment.
This comment wasn’t rated yet0
Тогда появляется возможность присвоить значение целиком элементу массива. Неизменяемость типа ключа не спасает.

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

Касаемо примера — он, конечно, весьма химерический, но он пример вреда обычной измеямой структуры, но я говорил о неизменяемости хэш-кода ключа, а не о изменямости структуры.
А вот есть политика лучше: структура должна переопределить GetHashCode.

И хэш определить и неизменяемой сделать.
Хэш могут потом и поменять, включив по ошибке потенциально изменяемое поле.

Вопрос не в том, зачем изменять структуру (хотя и в этом случае сразу вопрос — а почему не класс?), а зачем передавать изменяемую структуру как ключ.
Либо добавлять вспомогательный метод CloneWithMovedEdge1.

Либо делать для удобного редактирования класс, а для привязки его к таблице — неизменяемый структурный ключ этого отрезка.
Total votes 1: ↑0 and ↓1-1
Имеется в виду, что если мы используем хэш-код по прямому назначению — т.е. для оптимизации поиска, то изменение объекта, который мы ищем, может привести к невозможности его повторного поиска — сохраненный алгоритмом хэш автоматически не поменяется (в стандартных реализациях). Соответственно, если уж мы хотим менять объект, то менять его надо так, чтобы хэш оставался неизменным, а именно (в данном случае) все, кроме первого поля.

Хотя ситуация с изменением объекта после его помещения в хэш таблицу сама по себе не очень хорошая.

И это, вместе с остальным, является аргументом, почему структуры, которые чаще всего используют как ключи, надо стараться делать неизменяемыми. Об этом «остальном» можно почитать тут: stackoverflow.com/questions/441309/why-are-mutable-structs-evil. Ну и у Липперта в блоге.
This comment wasn’t rated yet0
Хотя ситуация с изменением объекта после его помещения в хэш таблицу...
Пожалуйста, поподробнее про это изменение после помещения. Как такое вообще могло бы выглядеть? Пример кода бы.
This comment wasn’t rated yet0
Например так
using System;
using System.Collections.Generic;

namespace HashTest
{
    public struct MutableStruct
    {
        private static readonly Random _rnd = new Random();

        public readonly int Id;
        public string Title;

        public MutableStruct(string title)
        {
            Id = _rnd.Next();
            Title = title;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var tree = new Dictionary<MutableStruct, object>();
            var key = new MutableStruct("Nice title");

            tree[key] = new object();
            
            Console.WriteLine("Struct is in tree: " + tree.ContainsKey(key)); // True

            key.Title = "Even better title";

            Console.WriteLine("Struct is in tree: " + tree.ContainsKey(key)); // False

            Console.ReadLine();
        }
    }
}

Total votes 2: ↑0 and ↓2-2
Поскольку MutableStruct — это value-тип, то при использовании его в качестве ключа таблица получит свою отдельную копию. И изменение оригинальной структуры, как в вашем примере, на этой копии никаким образом не отразится.

Собственно, об этом и речь — изменить поля у value typed ключа в хеш-таблице можно только в том случае, если он явно предоставит API для такого изменения.
Total votes 2: ↑2 and ↓0+2
Да, я немножко смешал в кучу общий случай, с возможно ссылочным объектом и некоторой абстрактной хэш-таблицей. Для стандартных .NET коллекций такая проблема со структурами не возникнет — потому структуры и используют в качестве ключей.
Но комментарий разработчиков (и сам автор), как мне кажется, описывает именно общую возможную ситуацию с хэш-кодом структуры.
This comment wasn’t rated yet0
Простите за глупый вопрос, а в практике как используют GetHashCode? Т.е. для чего он (кроме внутренней организации у обьектов) нужен?
Вроде сравнение обьекта и без него есть Eval(). Т.е. не понятен смысл зачем его public сделали.
This comment wasn’t rated yet0
Он используется например в Dictionary. То есть для любого кастомного типа ключей, если встроенный хэш не устраивает можно написать свой, более эффективный.
Ну и с другой стороны, если реализуется своя имплементация того же Dictionary или чего-то еще, где нужен хэш, то удобно знать, что его поддерживают все объекты.
Total votes 1: ↑1 and ↓0+1
разработчики CLR говорят, чтобы все пользовательские значимые типы данных (да и не только значимые, а все вообще) переопределяли метод GetHashCode.
А сами не переопределили для KeyValuePair, как мы теперь видим.
This comment wasn’t rated yet0
Кстати, автоматически генерируемый Equals и GetHashCode для анонимных типов очень удобно использовать, определяя свои, если нужен value equality по всем или нескольким полям. Например:

struct Point {
  public int X { get; private set; }
  public int Y { get; private set; }
  ...
  public override int GetHashCode() {
    return new { X, Y }.GetHashCode();
  }
}

Total votes 1: ↑1 and ↓0+1
Не согласен с расположением полей в объекте. Поля следует расположить как на картинкеimage
This comment wasn’t rated yet0
В условиях статьи особого значение не имело их расположение, поэтому я допустил эту вольность. А так MethodTablePointer располагается после SyncBlockIndex-a.
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr