Pregunta ¿Por qué no puedo recuperar un elemento de un HashSet sin enumeración?


Estoy buscando información sobre las cabezas de los diseñadores de HashSet. Por lo que sé, mi pregunta se aplica tanto a Java como a C # HashSets, lo que me hace pensar que debe haber una buena razón para ello, aunque no puedo pensar en ninguno.

Después de haber insertado un elemento en un HashSet, ¿por qué es imposible recuperar ese elemento sin enumeración, apenas una operación eficiente? Especialmente porque un HashSet está construido explícitamente de una manera que admite una recuperación eficiente.

A menudo me sería útil tener Remove (x) y Contains (x) devolver el elemento real que se está eliminando o conteniendo. Este no es necesariamente el elemento que paso a la función Eliminar (x) o Contiene (x). Claro, supongo que podría lograr el mismo efecto a través de un HashMap, pero ¿por qué perder todo ese espacio y esfuerzo cuando debería ser perfectamente posible hacerlo con un set?

Puedo apreciar que puede haber algunas preocupaciones de diseño que agreguen esta funcionalidad permitiría usos de HashSet que no son consistentes con su rol o rol futuro en el marco, pero si esto es así, ¿cuáles son estas preocupaciones de diseño?

Editar

Para responder algunas preguntas más, aquí hay más detalles:

Estoy usando un tipo de referencia inmutable con hashcode reemplazado, iguales, etc. para emular un tipo de valor en C #. Digamos que el tipo tiene miembros A, B y C. Hashcode, equals, etc dependen solo de A y B. Dado que algunos A y BI quieren poder recuperar ese elemento equivalente de un hashset y obtener su C. I won ' Puedo usar HashSet para esto, pero al menos me gustaría saber si hay alguna buena razón para esto. El pseudo código sigue:

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

32
2017-09-29 20:41


origen


Respuestas:


¿Cómo propones recuperar el elemento del conjunto de hash? Por definición, un conjunto no está ordenado de ninguna manera y, por lo tanto, no hay un índice con el que usarlo para recuperar el objeto en cuestión.

Los conjuntos, como concepto, se utilizan para probar la inclusión, es decir, si el elemento en cuestión está o no en el conjunto de datos hash. Si está buscando recuperar un valor de una fuente de datos usando un valor clave o índice, le sugiero que busque una Mapa o una Lista.

EDITAR: respuesta adicional basada en la edición a la pregunta original

Pronto, en función de su nueva información, parece que podría estar interesado en implementar sus datos como Java Enum, algo similar a esto:

 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 hereda automáticamente valores () que devuelve la lista de todos los valores en el "conjunto" de la enumeración, que puede usar para probar la inclusión en contra de la misma manera que el Conjunto. Además, como es una clase completa, puede definir nuevos métodos estáticos para hacer la lógica compuesta (como traté de aludir en el código de ejemplo). Lo único sobre Enum es que no puede agregar instancias nuevas en el tiempo de ejecución, que pueden no ser las que desea (aunque si el tamaño de los datos del conjunto no va a crecer en el tiempo de ejecución, Enum es lo que desea).


9
2017-09-29 20:57



En .Net, lo que probablemente esté buscando es KeyedCollection http://msdn.microsoft.com/en-us/library/ms132438.aspx

Puede evitar la necedad de volver a implementar esta clase abstracta cada vez con cierta astucia "genérica". (Ver IKeyedObject`1).

Nota: Cualquier objeto de transferencia de datos que implemente IKeyedObject`1 debe tener un método GetHashCode anulado simplemente devolviendo this.Key.GetHashCode (); y lo mismo vale para los iguales ...

La biblioteca de mi clase base generalmente termina con algo como esto en ella:

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; }
}

10
2018-01-26 15:56



Si cambia un objeto después de haberlo insertado, es posible que el hash haya cambiado (esto es especialmente probable si hashCode () ha sido anulado). Si el hash cambia, su búsqueda en el conjunto fallará, ya que intentará buscar un objeto con hash en una ubicación diferente a la que está almacenada.

Además, debe asegurarse de haber reemplazado hashCode e igualar en su objeto si desea buscar objetos iguales que sean instancias diferentes.

Tenga en cuenta que esto es todo por Java, supongo que C # tiene algo similar, pero como han pasado varios años desde que utilicé C #, dejaré que otros hablen de sus capacidades.


4
2017-09-29 20:46



Me imagino a los diseñadores de la Set interfaz y HashSet clase quería asegurarse de que el remove(Object) método definido en el Collection la interfaz también era aplicable a Set; este método devuelve un valor booleano que indica si el objeto se eliminó correctamente. Si los diseñadores deseaban proporcionar una funcionalidad mediante la cual remove (Object) devolviera el objeto "igual" que ya estaba en el Set esto significaría una firma de método diferente.

Además, dado que el objeto que se elimina es lógicamente igual al objeto pasado para eliminar (Objeto), es discutible sobre el valor agregado al devolver el objeto contenido. Sin embargo, he tenido este problema antes y he usado un Mapa para resolver el problema.

Tenga en cuenta que en Java, un HashSet usa un HashMap internamente y por lo tanto no hay una sobrecarga de almacenamiento adicional al usar una HashMap en lugar.


3
2017-09-29 21:01



¿Por qué no solo usar un HashMap<X,X>? Esto hace exactamente lo que quieres. Solo haz .put(x,x) cada vez y luego puede obtener el elemento almacenado igual a x con .get(x).


3
2017-09-13 22:18



Me parece que en realidad estás buscando un Map<X,Y>, donde Y es el tipo de extra1.


(despotrica abajo)

Los métodos equals y hashCode definen la igualdad significativa de objetos. La clase HashSet supone que si dos objetos son iguales como se define por Object.equals(Object) no hay diferencia entre estos dos objetos.

Me atrevería a decir que si el object extra es significativo, tu diseño no es ideal.


1
2017-09-30 17:54



SOLUCIONADO. El deseo de encontrar un elemento me parece perfectamente válido, porque el representante utilizado para la búsqueda puede diferir del elemento encontrado. Esto es especialmente cierto si los elementos contienen información clave y de valor, y un comparador de igualdad personalizado compara solo la parte clave. Vea el ejemplo de código. El código contiene un comparador que implementa una búsqueda personalizada y que captura el elemento encontrado. Esto requiere una instancia del comparador. Borre la referencia al elemento encontrado. Realice una búsqueda por medio de Contiene. Acceda al elemento encontrado. Tenga en cuenta los problemas de múltiples hilos al compartir la instancia del comparador.

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

1
2018-03-11 07:30



Esto fue un descuido de los diseñadores de la biblioteca. Como mencioné debajo otra respuesta, este método se ha agregado a .NET Framework 4.7.2 (y .NET Core 2.0 antes de eso); ver HashSet<T>.TryGetValue. Citando la fuente:

/// <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)

1
2017-07-07 07:53



Los objetos establecidos en esos idiomas se diseñaron principalmente como conjunto de valores, no para objetos mutables. Ellos verifican que el objeto puesto en ellos sea único mediante el uso de iguales. Es por eso que contiene y elimina los retornos booleanos, no el objeto: verifican o eliminan el valor que les pasa.

Y en realidad, si haces un contiene (X) en un conjunto, y esperas obtener un objeto Y diferente, eso significa que X e Y son iguales (es decir, X.equals (Y) => verdadero), pero algo diferente, lo cual parece mal


0
2017-09-29 20:55