0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
1

Разрешение коллизий в dictionary

19.12.2019, 18:11. Показов 18770. Ответов 23
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем привет, у меня возник вопрос как разрешаются коллизии dictionary.
Я прекрасно понимаю что формируется односвязный и.д. все что указано здесь
У меня такой вопрос, как бороться против алгоритмической атаки?
как VM определяет как считать хеш?
Буду благодарен за информацию, статьи и литературу.
Всем спасибо
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.12.2019, 18:11
Ответы с готовыми решениями:

Проинициализировать значениями dictionary вложенный в dictionary
Народ, помогите, как проинициализировать значениями такую конструкцию: Dictionary...

Разрешение коллизий
Скажите пожалуйста, какими методами решаются коллизии в БД, Про оптимистичный/пессимистичный...

Разрешение коллизий
Здравствуйте, необходимо мнение и опыт бывалых разработчиков. Дано: Веб-приложение. Серверная...

(Хеширования) Разрешение коллизий при хешировании методом открытой адресации
Доброго времени суток! Программа реализует алгоритм решения коллизий методом открытой адресации....

23
Эксперт .NET
17751 / 12906 / 3374
Регистрация: 17.09.2011
Сообщений: 21,181
19.12.2019, 19:08 2
Цитата Сообщение от Sky53 Посмотреть сообщение
как бороться против алгоритмической атаки?
Что вы подразумеваете под алгоритмической атакой и как она связана со словарем?

Цитата Сообщение от Sky53 Посмотреть сообщение
как VM определяет как считать хеш?
VM никак не определяет — она тупо компилирует CIL в машинный код.
Как считать хэш определяет реализация словаря, которая вызывает GetHashCode на ключе. Как реализуется этот хэш-код зависит уже от типа, используемого в качестве ключа.
1
0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
19.12.2019, 20:40  [ТС] 3
Добрый.
Если предположить такую ситуацию, я генерирую строки с одинаковым хешкодом, по этим строкам добавляю значения. В результате этого, будет формироваться однонаправленный список, в теории, таким способом он может разрастися до огромных размеров, взятие объекта при таком сценарии имеет сложность О(n), могут быть серьезные просадки производительности.

В стать я прочитал следующее
" Если при добавлении элемента число коллизий велико (больше 100 в текущей версии), то при расширении коллекции происходит операция перехэширования, перед выполнением которой случайным образом выбирается новый генератор хэшкодов.
Сложность добавления O(1) или O(n) в случае коллизии."

Вот стало не понятно по какому прицепу будет меняться, а информации пока не нашел.

ел.
0
Эксперт .NET
17751 / 12906 / 3374
Регистрация: 17.09.2011
Сообщений: 21,181
19.12.2019, 21:07 4
Цитата Сообщение от Sky53 Посмотреть сообщение
Если предположить такую ситуацию, я генерирую строки с одинаковым хешкодом, по этим строкам добавляю значения. В результате этого, будет формироваться однонаправленный список, в теории, таким способом он может разрастися до огромных размеров, взятие объекта при таком сценарии имеет сложность О(n), могут быть серьезные просадки производительности.
Верно, при плохой реализации хэш-кода словарь мало чем отличается от массива.
То же самое касается плохого распределения хэш-кодов. В идеале два похожих значения должны генерировать два очень непохожих хэш-кода.

Цитата Сообщение от Sky53 Посмотреть сообщение
Вот стало не понятно по какому прицепу будет меняться, а информации пока не нашел.
Автор либо что-то путает, либо не полностью объяснил ситуацию. Ну или объяснил где-то в другом месте — я всю статью не читал.
То, о чем у него написано, применимо только в случае, когда в качестве ключа используются строки — тогда при достижении определенного количества коллизий словарь меняет генератор хэш-кодов на рандомизированный и пересчитывает хэши уже хранящихся значений.
Для других типов ничего подобного не делается, т.к. реализация словаря понятия не имеет по какому принципу генерировать хэш-коды для других классов — она расчитывает на реализацию GetHashCode. Ну или на передаваемый экземпляр IEqualityComparer.

Добавлено через 37 секунд
Если интересно, вот текущая реализация словаря в .NET Core 3.1: https://github.com/dotnet/runt... tionary.cs
3
0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
20.12.2019, 10:42  [ТС] 5
Цитата Сообщение от kolorotur Посмотреть сообщение
Для других типов ничего подобного не делается, т.к. реализация словаря понятия не имеет по какому принципу генерировать хэш-коды для других классов — она расчитывает на реализацию GetHashCode. Ну или на передаваемый экземпляр IEqualityComparer.
Т.Е. Если я в качестве ключа буду использовать какой-нибудь кастомный объект(MyClass[с тремя полями внутри и не переопределю GetHashCode]), то я смогу построить вложенный список в словаре длинной N?

Цитата Сообщение от kolorotur Посмотреть сообщение
Если интересно, вот текущая реализация словаря в .NET Core 3.1: https://github.com/dotnet/runt... tionary.cs
Спасибо, ознакомлюсь сейчас
0
Модератор
Эксперт .NET
15661 / 10843 / 2812
Регистрация: 21.04.2018
Сообщений: 31,845
Записей в блоге: 2
20.12.2019, 11:05 6
Sky53, это не так просто.
Сделайте такой класс, но не переопределяйте GetHashCode.
И попробуйте создавать разные экземпляры, но с одним значением GetHashCode.
0
0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
20.12.2019, 11:17  [ТС] 7
Цитата Сообщение от Элд Хасп Посмотреть сообщение
И попробуйте создавать разные экземпляры, но с одним значением GetHashCode.
Смотря, что поднимать под разными объектами:
C#
1
2
3
4
5
var obj = new MyObj("str", 100);
var obj2 = new MyObj("str", 100);
 
obj = obj2 // false т.к. ссылки разные
obj.Equals(obj2) //true по понятным причинам
0
Модератор
Эксперт .NET
15661 / 10843 / 2812
Регистрация: 21.04.2018
Сообщений: 31,845
Записей в блоге: 2
20.12.2019, 11:34 8
Sky53, а Sky53, в данной случае имеетются ввиду те экземпляры, которые словарь будет считать разными ключами.
Речь же идёт о таких коллизиях.
Ключи разные, но GetHashCode один.
0
0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
20.12.2019, 11:36  [ТС] 9
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using System;
using System.Collections.Generic;
using System.Text;
 
namespace Start
{
    class GenareteObj
    {
        public static PersonClass GetOneHash(int countGeneretion, PersonClass target)
        {
            int targetHash = target.GetHashCode();
            for (int i = 0; i < countGeneretion; i++)
            {
                PersonClass obj = new PersonClass(i,i * 1000);
 
                if (obj.GetHashCode() == targetHash)
                {
                    Console.WriteLine(i);
                    Console.WriteLine($"hashcode terget equals generete hashcode {target} , {targetHash}" +
                       $" = {obj}, {obj.GetHashCode()}");
                    return obj;
                   
                }
            }
            return null;
        }
    }
}

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
using System;
using System.Collections.Generic;
using System.Text;
 
namespace Start
{
    class PersonClass
    {
        private int value { get; set; }
 
        private long lValue { get; set; }
 
        public PersonClass()
        {
            this.value = 0;
            this.lValue = 0;
        }
 
        public PersonClass(int value, long lValue)
        {
            this.value = value;
            this.lValue = lValue;
        }
    }
 
 
}
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using System;
using System.Threading;
 
namespace Start
{
    class Program
    {
        static void Main(string[] args)
        {
            PersonClass personClass = new PersonClass(12,24);
 
            GenareteObj.GetOneHash(1000_000_000, personClass);
 
        }
 
  
 
       
    }
}

Два поля для быстроты примера
0
Эксперт .NET
17751 / 12906 / 3374
Регистрация: 17.09.2011
Сообщений: 21,181
20.12.2019, 13:25 10
Sky53, что этот пример должен продемонстрировать?
0
Модератор
Эксперт .NET
15661 / 10843 / 2812
Регистрация: 21.04.2018
Сообщений: 31,845
Записей в блоге: 2
20.12.2019, 14:31 11
Sky53, я тоже не понял...

Добавлено через 32 минуты
Sky53, класс с одним свойством из GetHashCode - зачем и ее применение?
C#
1
2
3
4
5
6
7
8
9
10
11
public class Custom : IEquatable<Custom>
{
     protected static Random rand = new Random();
     public int Value {get;}
     public Custom() => Value = rand.Next();
     public Custom(int value) => Value = value;
 
     public bool Equals(Custom other) => Value == other.Value;
     public override bool Equals(object obj) => (obj is Custom other) && Equals(other);
  //   public override int GetHashCode() => -738832489 ^ Value.GetHashCode();
}
Теперь создаём множество из 10млн экземпляров и проверяем сколько с одинаковыми хеш.
C#
1
2
3
4
5
6
7
HashSet<Custom> hashSet = new HashSet<Custom>();
while(hashSet.Count < 10_000_000)
   hashSet.Add(new Custom ());
var group = hashSet.GroupBy(x => x.GetHashCode()).OrderBy(x => x.Count());
Console.WriteLine("Минимальная группа " + group.First().Count());
Console.WriteLine("Максимальная группа " + group.Last().Count());
Console.WriteLine("Всего групп " + group.Count());
Запустите код - я в поездке и без компа. Пишу со Смарта.
И выложите какой будет результат.
1
0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
20.12.2019, 14:38  [ТС] 12
kolorotur, демонстрировал создание объектов с один хешом.
0
Эксперт .NET
17751 / 12906 / 3374
Регистрация: 17.09.2011
Сообщений: 21,181
20.12.2019, 14:54 13
Цитата Сообщение от Sky53 Посмотреть сообщение
демонстрировал создание объектов с один хешом.
Так а зачем?
Можно это показать намного проще:
C#
1
2
3
4
    class PersonClass
    {
        public override int GetHashCode() => 0;
    }
У всех экземпляров будет одинаковый хэш, использование этого типа в качестве ключа превращает словарь в массив.

Только я упорно не могу понять, что именно вас беспокоит.
2
0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
20.12.2019, 16:27  [ТС] 14
Элд Хасп,
Разрешение коллизий в dictionary
0
0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
20.12.2019, 16:30  [ТС] 15
Цитата Сообщение от kolorotur Посмотреть сообщение
Только я упорно не могу понять, что именно вас беспокоит.
Словари при формирование очень большего списка не перебраться в дерево или во что другое?
0
Модератор
Эксперт .NET
15661 / 10843 / 2812
Регистрация: 21.04.2018
Сообщений: 31,845
Записей в блоге: 2
20.12.2019, 16:31 16
Sky53, при 10 млн экземпляров максимальная группа - пять.
Какое-то виляние такие коллизии могут оказать?

Вот другое дело, если GetHashCode переопределен неверно (пример от kolorotur).
Но это проблема реализации типа, а не коллизий хеша.
1
0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
20.12.2019, 17:03  [ТС] 17
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Sky53, при 10 млн экземпляров максимальная группа - пять.
Какое-то виляние такие коллизии могут оказать?
Поэтому я спрашивал как разрешаются коллизии при алгоритмических атаках, и адаптируется ли список связанных элементов во что-то еще)
НО тем не менее больше спасибо за диалог)
0
Модератор
Эксперт .NET
15661 / 10843 / 2812
Регистрация: 21.04.2018
Сообщений: 31,845
Записей в блоге: 2
20.12.2019, 17:14 18
Sky53, я думаю сама по себе такая атака, трудно осуществима.
И привязана к какой-то конкретной ошибочной реализации
И в лучшем случае приведёт к замедлению работы - вместо поиска по хеш будет использоваться линейный поиск.
0
0 / 0 / 0
Регистрация: 10.05.2017
Сообщений: 11
20.12.2019, 17:59  [ТС] 19
Цитата Сообщение от Элд Хасп Посмотреть сообщение
И привязана к какой-то конкретной ошибочной реализации
Дело не в реализации в каком-то абстрактом проекте.
Цитата Сообщение от Элд Хасп Посмотреть сообщение
И в лучшем случае приведёт к замедлению работы - вместо поиска по хеш будет использоваться линейный поиск.
С 8 джавы в таких случаях список преобразуется в бинароное деререво, я вот и хотел узнать если что то такое в шарпе
0
3601 / 2522 / 707
Регистрация: 02.08.2011
Сообщений: 6,804
20.12.2019, 18:08 20
Цитата Сообщение от Sky53 Посмотреть сообщение
как бороться против алгоритмической атаки?
Я вот не пойму, на что нацелена ваша алгоритмическая атака?

GetHashCode был создан для ускорения поиска, чтобы потенциально равные объекты группировались в группы с одинаковым хэшем, с уже последующим точным сравнением.
Это не тот хэш, который используется в криптографии. Он не должен быть криптографически стойким. By design.

Добавлено через 1 минуту
MSDN:
The GetHashCode method provides this hash code for algorithms that need quick checks of object equality.
Добавлено через 2 минуты
И снова MSDN. Warning:
Do not use the hash code instead of a value returned by a cryptographic hashing function if you need a cryptographically strong hash. For cryptographic hashes, use a class derived from the System.Security.Cryptography.HashAlgorithm or System.Security.Cryptography.KeyedHashAlgorithm class.
0
20.12.2019, 18:08
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.12.2019, 18:08
Помогаю со студенческими работами здесь

Отбор из Dictionary вложенного в Dictionary
Здравствуйте, есть такой код: private Dictionary&lt;string, Dictionary&lt;int, string&gt;&gt; vt = new...

Как достать dictionary из dictionary?
Подскажите пожалуйста как получить значение dictionary который находится внутри другого dictionary?...

Создать запрос Dictionary в Dictionary
Только учусь программировать и поэтому не очень разобрался с LINQ. У меня есть ...

Сложный Dictionary<MyClass, Dictionary<List<MyClass2>, List<string>>> MyDictionary
Здравствуйте. Помогите plz реализовать обращения к словарю вида : Dictionary&lt;MyClass,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru