[DSA] Домашно Dictionaries, Hash Tables аnd Sets - 5 Задача


2

Условие:

5.Implement the data structure "set" in a class HashedSet<T> using your class HashTable<K,T> to hold the elements. Implement all standard set operations like Add(T), Find(T), Remove(T), Count, Clear(), union and intersect.
 
Решение - цък
 
При въвеждането на всяка стойност в множеството използвам ToString() GetHashCode() метода, за да подавам винаги ключове с еднакъв тип в хеш таблицата. За Intersect и Union използвам LINQ, което връща колекция и от нея създавам ново множество, което връщам. Другите методи са същите като в хеш таблицата.



Отговори



1
Да хешираш по ToString не е смислено, защото за всеки клас, чийто ToString не е предефиниран се използва базовата имплементация, която връща името на класа => всички обекти от такъв клас ще имат един и същи ToString <=> всички обекти от такъв клас ще имат един и същи хеш.

P.S. Не си commit-нал, репозиторито има само почти празни файлове.



0
И аз мислих върху този въпрос, но се спрях на ToString(), понеже всички примитивни типове го имат. GetHashCode е същото нещо. Дай предложение за нещо друго?
ПП: Гит нещо ми се бъгна, къмитнал съм, но не отчита в сайта.

от georgi.ivanov (3261 точки)

0
GetHashCode далеч не е същото нещо. Дори, когато не е предефиниран връща различни стойности за различни елементи. Тествай долния код и се увери сам:
http://pastebin.com/Kq2xPcMW




1

Не съм сигурен, че е необходимо да се имплементира Find(T element), защото какво реално трябва да връща този Find? Може вместо това да се сложи едно bool Contains(T element), което има повече логика. 

А специално за твоята имплементация - не е коректно да използваш HashTable<string, T>, защото някои типове данни, които има default-ен ToString() метод ще ти гърмят. Ако се опиташ например да добавиш 2 различни List<int>-а ще ти каже, че използваш един и същ ключ: "System.Collections.Generic.List`1[System.Int32]". По-добра идея е като ключ да си пазиш самият елемент, а като стойност да зададеш един int например (така или иначе не се сещам за какво може да ти трябва стойноста, след като HashedSet работи само с един тип данни). Имам предвид данните да ти се пазят в HashTable<T, int> например.


от gallumbits (2371 точки)


0
Обсъдихме този въпрос с колегата по-горе.
Направил съм промените, но нещо репо-то се е бъгнало и не ги отчита. В момента вътрешната хеш-таблица изглежда така - HashTable

от georgi.ivanov (3261 точки)

0
Освен, че си чекирал дал ли си sync/push? А защо ползваш HashTable

от gallumbits (2371 точки)



3

И аз по сходен начин го направих, но имплементирах UnionWith и IntersectWith, предполагам не е грешно. Но пък сложих и foreach за всеки случай.

Задачка.


от tankovski (2828 точки)


0

И в двете постнати решение методите IntersectWith и UnionWith приемат HashedSet<T> като параметър и вътрешно го използват като IEnumerable<T>. Логично е да приемат каквато и да е колекция IEnumerable<T>.
Малка оптимизация в моето решение в метода UnionWith е използването на bool TryAdd(K, T) метода на вътрешната структура HashTable от четвърта задача, който вътрешно само веднъж изчислява хеш код и проверява дали вече нямаме такъв елемент. Варианта първо с проверка дали се съдържа новият елемент и след това добавяне прави тези операции два пъти.
Не ми е ясно и защо трябва да се ползва структурата от предната задача - няма нужда да пазим стойност, която поне в моето решение е 0 винаги.
Съгласен съм с Vasil Dininski, че не е добра идея да се ползва HashTable<int, T> като int-а е хеш кода на T. Когато имаш два различни обекта с еднакви хеш кодове няма да може да се добави втория обект. По-добро решение е HashTable<T, int>...


от pirin (1101 точки)


2

Решение

Генерирам на всеки елемент ключ, който е хеш кода. Става малко GetHashCode на GetHashCode на елемента (което е hash на int което е самия int), но мисля че така е най-подходящо. Всички методи викат методите на предната задача, така че няма да ги обяснявам подробно.

Union добавя в един нов set всички елементи от конкретния и подадения set. Няма да има повторения на елементи, защото hash table от миналата задача не позволява наличието на елементи с еднакъв ключ - при опит за добавяне на такъв се променя стойността.

Intersect го реализирах с два вложени foreach и един break, но си мисля че може да има и по-бърз начин.


от dzhenko (3893 точки)


0
Дженко ако добавиш два различни елемента (Е1 и Е2), които имат еднакъв HashCode те би трябвало да се добавят в един от съврзаните списъци. След това ако се опиташ да махнеш втория елемент (Е2) ще му се сметне HashCode-а, ще намери в кой списък е и ще махне първият елемент от този списък, т.е. елемент Е1. И аз го пробвах в началото така, но след това добавих проверка по Value за HashedSet

от wnvko (3123 точки)


0
Тази задача е доста по-лека от предната (където създаваме HashTable<K,T>). Целия клас излезе 100 реда. Вътрешно сета пази HashTable<T, bool>, където T е типа на елементите в сета. Тъй като нямаме никаква нужда от полето за стойност, за най-просто съм избрал да е bool, и там няма значение дали пишем true или false. На практика, когато към сета добавяме елемент от тип T, в хеш таблицата се добавя двойка с ключ равен на елемента (ако вече няма такъв ключ). Когато търсим елемент в сета, в таблицата търсим двойка с такъв ключ. Малко по-интересен е метода Intersect - там си взимам списък с всички елементи от сета, и тези които не се намират в другата колекция ги махам. Така остава само сечението. Метода Find работи като Contains.
 

от neutrino (3376 точки)