Warum kann ich ohne Aufzählung kein Element aus einem HashSet abrufen?
https://stackoverflow.com/questions/1494812
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich suche Einblicke in die Köpfe der HashSet-Designer.Soweit mir bekannt ist, bezieht sich meine Frage sowohl auf Java- als auch auf C#-HashSets, weshalb ich denke, dass es dafür einen guten Grund geben muss, obwohl mir selbst keiner einfällt.
Warum ist es nach dem Einfügen eines Elements in ein HashSet nicht möglich, dieses Element ohne Aufzählung abzurufen, was kaum eine effiziente Operation ist?Vor allem, weil ein HashSet explizit so aufgebaut ist, dass es einen effizienten Abruf unterstützt.
Für mich wäre es oft nützlich, wenn Remove(x) und Contains(x) das tatsächliche Element zurückgeben würden, das entfernt oder enthalten wird.Dies ist nicht unbedingt das Element, das ich an die Funktion „Remove(x)“ oder „Contains(x)“ übergebe.Sicher, ich schätze, ich könnte den gleichen Effekt mit einer HashMap erzielen, aber warum sollte man so viel Platz und Aufwand verschwenden, wenn es durchaus möglich sein sollte, dies mit einem Set zu erreichen?
Ich kann mir vorstellen, dass es einige Designbedenken geben könnte, dass das Hinzufügen dieser Funktionalität die Verwendung von HashSet ermöglichen würde, die nicht mit ihrer Rolle oder zukünftigen Rolle im Framework übereinstimmt. Wenn dies jedoch der Fall ist, welche Designbedenken bestehen dann?
Bearbeiten
Um weitere Fragen zu beantworten, finden Sie hier weitere Details:
Ich verwende einen unveränderlichen Referenztyp mit überschriebenem Hashcode, Gleichheiten usw., um einen Werttyp in C# zu emulieren.Nehmen wir an, der Typ hat die Mitglieder A, B und C.Hashcode, Gleichheit usw. hängen nur von A und B ab.Angesichts einiger A und B möchte ich in der Lage sein, das entsprechende Element aus einem Hashset abzurufen und C zu erhalten.Es scheint, dass ich dafür HashSet nicht verwenden kann, aber ich würde zumindest gerne wissen, ob es dafür einen guten Grund gibt.Es folgt Pseudocode:
public sealed class X{
object A;
object B;
object extra;
public int HashCode(){
return A.hashCode() + B.hashCode();
}
public bool Equals(X obj){
return obj.A == A && obj.B == B;
}
}
hashset.insert(new X(1,2, extra1));
hashset.contains(new X(1,2)); //returns true, but I can't retrieve extra
Lösung
Wie vorschlugen Sie das Element aus dem Hash-Set abzurufen? Ein Satz ist per Definition nicht in irgendeiner Weise bestellt und daher gibt es keinen Index, mit dem das betreffenden Objekt zu verwenden, abgerufen werden.
Sets, als ein Konzept, werden verwendet Aufnahme zu testen, das heißt, ob das betreffende Element in der Hash-Datensatz ist. Wenn Sie suchen einen Wert aus einer Datenquelle abrufen einen Schlüsselwert oder einen Index verwenden, würde ich vorschlagen, in der Suche entweder ein Karte oder ein Liste .
EDIT: Zusätzliche Antwort basierend auf dem Bearbeiten auf die ursprüngliche Frage
Soonil, basierend auf neuen Informationen, es sieht aus wie Sie interessiert sein könnten Ihre Daten als Java-Enum, etwas Ähnliches wie dies bei der Umsetzung:
public enum SoonilsDataType {
A, B, C;
// Just an example of what's possible
public static SoonilsDataType getCompositeValue(SoonilsDataType item1,
SoonilsDataType item2) {
if (item1.equals(A) &&
item2.equals(B)) {
return C;
}
}
}
Enum die Werte automatisch erben (), die gibt die Liste aller Werte in der Enumeration der „Set“, die Sie Aufnahme testen gegen in der gleichen Weise wie das Set verwenden können. Auch, weil seine eine volle Klasse, können Sie neue statische Methoden definieren die zusammengesetzte Logik zu tun (wie ich im Beispielcode zu anspielen versuchte). Das einzige, was über das Enum ist, dass Sie keine neuen Instanzen zur Laufzeit hinzufügen kann, was nicht sein kann, was Sie wollen (obwohl, wenn die Datengröße des Sets wird nicht zur Laufzeit wachsen, die Enum ist, was Sie wollen).
Andere Tipps
In .Net, was Sie wahrscheinlich für suchen, ist KeyedCollection http://msdn.microsoft.com/en-us/library/ms132438.aspx
Sie können mit etwas „generic“ Klugheit Neuimplementierung dieser abstrakten Klasse bekommen jedes Mal um die Bösartigkeit von. (Siehe IKeyedObject`1.)
Hinweis: Alle Datenübertragungsobjekt, das IKeyedObject`1 implementiert sollte eine überschriebene Methode GetHashCode einfach haben Rückkehr this.Key.GetHashCode (); und Gleiches gilt für equals ...
Meine Base Class Library endet in der Regel mit so etwas wie dies in it up:
public class KeyedCollection<TItem> : System.Collections.ObjectModel.KeyedCollection<TItem, TItem>
where TItem : class
{
public KeyedCollection() : base()
{
}
public KeyedCollection(IEqualityComparer<TItem> comparer) : base(comparer)
{
}
protected override TItem GetKeyForItem(TItem item)
{
return item;
}
}
public class KeyedObjectCollection<TKey, TItem> : System.Collections.ObjectModel.KeyedCollection<TKey, TItem>
where TItem : class, IKeyedObject<TKey>
where TKey : struct
{
public KeyedCollection() : base()
{
}
protected override TItem GetKeyForItem(TItem item)
{
return item.Key;
}
}
///<summary>
/// I almost always implement this explicitly so the only
/// classes that have access without some rigmarole
/// are generic collections built to be aware that an object
/// is keyed.
///</summary>
public interface IKeyedObject<TKey>
{
TKey Key { get; }
}
Wenn Sie ein Objekt ändern, nachdem sie eingeführt wurde, ist es der Hash verändert haben können (dies ist besonders wahrscheinlich, wenn hashCode () außer Kraft gesetzt wurde). Wenn die Hash ändert, wird ein Nachschlag davon in der Menge nicht, wie Sie ein Objekt versucht werden nachzuschlagen, die an einem anderen Ort gehasht wird, als es in gespeichert wird.
Außerdem müssen Sie sicherstellen, dass Sie hashCode und gleich in Ihrem Objekt außer Kraft gesetzt, wenn Sie gleich Objekte nachschlagen möchten, die verschiedenen Instanzen sind.
Beachten Sie, dass dies alles für Java ist. - Ich C # ähnlich etwas gehe davon aus, aber als es einige Jahre her, seit ich C # verwendet wird, lasse ich andere sprechen es ist Fähigkeiten
ich die Designer der Set Schnittstelle und HashSet Klasse vorstellen wollte, dass die remove(Object) Methode auf der Collection Schnittstelle definiert, um sicherzustellen, war auch für Set; Diese Methode gibt einen boolean angibt, ob das Objekt erfolgreich entfernt wurde. Wenn die Designer-Funktionalität zur Verfügung zu stellen wollte wobei remove (Object) zurückgegeben, die „gleich“ Objekt bereits in der Set dies eine andere Methode Signatur bedeuten würde.
Auch gegeben, dass das Objekt entfernt wird, auf das Objekt logisch gleich übergeben zu entfernen (Object) es das enthaltene Objekt über die Wertschöpfung bei der Rückkehr diskutierbar ist. Allerdings habe ich dieses Problem selbst vor hatte und haben eine Karte zu lösen das Problem verwendet.
Beachten Sie, dass in Java, ein HashSet ein HashMap intern verwendet, und so gibt es keine zusätzlichen Speicheraufwand eine HashMap stattdessen zu verwenden.
Warum nicht einfach ein HashMap<X,X> benutzen? Dies ist genau das, was Sie wollen. Genau das tut, jedes Mal .put(x,x) und dann können Sie einfach das gespeicherte Element gleich x mit .get(x) erhalten.
Das war ein Versehen aus der Bibliothek Designern. Wie ich unter eine andere Antwort wurde diese Methode auf NET Framework 4.7.2 (und NET Core 2.0 , bevor es). finden Sie unter HashSet<T>.TryGetValue . Unter Berufung auf der Quelle :
/// <summary>
/// Searches the set for a given value and returns the equal value it finds, if any.
/// </summary>
/// <param name="equalValue">The value to search for.
/// </param>
/// <param name="actualValue">
/// The value from the set that the search found, or the default value
/// of <typeparamref name="T"/> when the search yielded no match.</param>
/// <returns>A value indicating whether the search was successful.</returns>
/// <remarks>
/// This can be useful when you want to reuse a previously stored reference instead of
/// a newly constructed one (so that more sharing of references can occur) or to look up
/// a value that has more complete data than the value you currently have, although their
/// comparer functions indicate they are equal.
/// </remarks>
public bool TryGetValue(T equalValue, out T actualValue)
ich Sieht aus wie Sie tatsächlich für ein Map<X,Y> suchen, wo Y die Art der extra1 ist.
(rant unten)
Die equals und hashCode Methoden definieren sinnvolle Objektgleichheit. Die HashSet Klasse geht davon aus, dass, wenn zwei Objekte gleich sind, wie durch Object.equals(Object) definiert gibt es keinen Unterschied zwischen diesen beiden Objekten.
Ich würde so weit gehen zu sagen, dass, wenn die object extra sinnvoll ist, Ihr Entwurf nicht ideal ist.
GELÖST . Sie wünschen ein Element zu finden scheint völlig in Ordnung für mich, weil der Vertreter für die Suche verwendet wird, kann aus dem gefundenen Elemente unterscheiden. Dies gilt insbesondere, wenn Elemente Schlüssel und Wertinformationen enthalten, und ein benutzerdefinierten Gleichheitsvergleich vergleicht den Schlüsselteil nur. Siehe das Codebeispiel. Der Code enthält einen Vergleich, der eine benutzerdefinierte Suche implementiert und , die das Element fängt gefunden. Dies erfordert eine Instanz des Vergleichs. Deaktivieren Sie den Verweis auf das Element gefunden. Führen Sie eine Suche mittels Enthält. Besuchen Sie das gefunden Element. Seien Sie sich bewusst von Multi-Thread-Probleme, wenn die comparer Instanz teilen.
using System;
using System.Collections.Generic;
namespace ConsoleApplication1 {
class Box
{
public int Id;
public string Name;
public Box(int id, string name)
{
Id = id;
Name = name;
}
}
class BoxEq: IEqualityComparer<Box>
{
public Box Element;
public bool Equals(Box element, Box representative)
{
bool found = element.Id == representative.Id;
if (found)
{
Element = element;
}
return found;
}
public int GetHashCode(Box box)
{
return box.Id.GetHashCode();
}
}
class Program
{
static void Main()
{
var boxEq = new BoxEq();
var hashSet = new HashSet<Box>(boxEq);
hashSet.Add(new Box(3, "Element 3"));
var box5 = new Box(5, "Element 5");
hashSet.Add(box5);
var representative = new Box(5, "Representative 5");
boxEq.Element = null;
Console.WriteLine("Contains {0}: {1}", representative.Id, hashSet.Contains(representative));
Console.WriteLine("Found id: {0}, name: {1}", boxEq.Element.Id, boxEq.Element.Name);
Console.WriteLine("Press enter");
Console.ReadLine();
}
}
} // namespace
Set-Objekte in diesen Sprachen wurden meist als Satz von Wert entworfen, nicht für veränderbare Objekte. Sie überprüfen, dass das Objekt setzen in sie einzigartig sind durch Gleichen verwenden. Aus diesem Grund enthält und kehrt boolean entfernen, nicht das Objekt. Sie überprüfen oder entfernen Sie den Wert, den Sie an sie weitergeben
Und tatsächlich, wenn Sie das tun ein enthält (X) auf einem Satz, und erwarten ein anderes Objekt Y zu erhalten, wäre das Mittel X und Y gleich (dh x.equals (Y) => true), aber etwas unterschiedlich, was falsch zu sein scheint.
wurde mir einen interessanten Vorschlag, wie auf eine Art und Weise gegeben, eine Karte zu verwenden, um meine eigenen Objekte als KeyValuePairs definieren sie haben. Während ein gutes Konzept, leider ist KeyValuePair nicht eine Schnittstelle (warum nicht?) Und ist eine Struktur, die diesen Plan aus der Luft schießt. Am Ende werde ich mein eigenes Set rollen, wie meine Zwänge mir diese Option ermöglichen.
Kurze Antwort; weil die Einzelteile nicht sein unveränderlich gewährleistet werden können.
ich das genaue Problem getroffen haben Sie beschreiben, wo die HashCode auf festen Feldern innerhalb der Elementklasse basiert, aber die Klasse hält zusätzliche Informationen, die ohne Änderung des Hash aktualisiert werden kann.
war meine Lösung eine generische MyHashSet zu implementieren
Nachdem ich mich das Gleiche gefragt habe und mir den Quellcode genauer ansehen konnte:
Quelle: http://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs
Eine Menge ist eine Sammlung einzigartiger Elemente (Objekte oder Werte).In der .net-Implementierung ist ein Element dasselbe wie ein anderes Element (nicht eindeutig), wenn die Equals-Methode des Vergleichers für die beiden Elemente „true“ zurückgibt.Nicht, wenn die beiden Elemente denselben Hash-Code haben.Daher ist die Überprüfung der Existenz eines Artikels ein zweistufiger Prozess.Zuerst wird der Hashset verwendet, um die Anzahl der zu komprimierenden Elemente zu minimieren, dann erfolgt die Komprimierung selbst.
Wenn Sie einen Artikel abrufen möchten, müssen Sie in der Lage sein, der Abruffunktion eine eindeutige Kennung bereitzustellen.Möglicherweise kennen Sie den Hash-Code des gewünschten Artikels.aber das ist nicht genug.da mehr als ein Element denselben Hash haben kann.Sie müssen auch das Element selbst angeben, damit die Equal-Methode aufgerufen werden kann.Und wenn Sie den Artikel haben, gibt es offensichtlich keinen Grund, ihn zu kaufen.
Man könnte eine Datenstruktur erstellen, die verlangt, dass keine zwei eindeutigen Elemente jemals denselben Hash-Code zurückgeben.und dann könnte man einen Gegenstand daraus bekommen.Das Hinzufügen* geht schneller und das Abrufen ist möglich, wenn Sie den Hash kennen.Wenn zwei Elemente eingefügt werden, die nicht gleich sind, aber denselben Hash zurückgeben, wird das erste überschrieben.Soweit ich weiß, existiert dieser Typ in .net nicht, und nein, das ist nicht dasselbe wie ein Wörterbuch.
*vorausgesetzt, die GetHash-Methode ist dieselbe.
