Por que não posso recuperar um item a partir de um HashSet sem enumeração?
https://stackoverflow.com/questions/1494812
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou olhando para esclarecimento sobre as cabeças de HashSet designers.Até onde eu sei, a minha pergunta se aplica para o Java e o C# HashSets, fazendo-me pensar que deve haver um bom motivo para isso, embora eu não possa pensar de mim.
Depois de ter inserido um item em um HashSet, por que é impossível recuperar esse item sem enumeração, dificilmente uma operação eficiente?Especialmente desde que um HashSet é explicitamente construído de uma forma que dá suporte eficiente recuperação.
Muitas vezes seria útil para mim para Remover(x) e Contém(x) devolver o item real que está sendo removida ou contido.Este não é necessariamente o item de eu passar em Remover(x) ou Contém(x) função.Com certeza, eu acho que eu poderia alcançar o mesmo efeito através de um HashMap, mas porquê desperdiçar todo esse espaço e esforço quando deveria ser perfeitamente possível fazer isso com um conjunto?
Eu posso compreender que pode haver alguns problemas de design preocupações que adicionar essa funcionalidade permite que usa de HashSet, que não são consistentes com a sua função ou papel futuro no quadro, mas se isto é assim, o que são essas as preocupações de design?
Editar
Para responder a mais algumas perguntas, aqui estão mais detalhes:
Eu estou usando uma imutável tipo de referência com substituída hashcode, igual, etc., para emular um valor de tipo do C#.Vamos dizer que o tipo tem membros de A, B e C.Hashcode, igual, etc dependem apenas A e B.Dado alguns A e B eu quero ser capaz de recuperar o equivalente item a partir de um hashset e obter é C.Eu não vou ser capaz de usar HashSet para isso, ele aparece, mas eu pelo menos gostaria de saber se há alguma boa razão para isso.Pseudo-código a seguir:
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
Solução
Como você propõe para recuperar o item a partir do hash conjunto?Um conjunto é, por definição, não é ordenado de forma alguma, e, portanto, não há nenhum índice com o que usar para recuperar o objeto em questão.
Define, como um conceito, são usados para testar a inclusão, i.é.se ou não o elemento em questão é o hash do conjunto de dados.Se você estiver olhando para obter um valor a partir de uma fonte de dados usando um valor de chave ou índice, gostaria de sugerir olhando para uma Mapa ou um Lista.
EDITAR:Adicional de resposta com base em Editar para a pergunta original
Soonil, com base na sua informação, parece que você poderia estar interessado na execução de seus dados, como Java Enum, algo semelhante a isto:
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 automaticamente herdam valores de() que retorna a lista de todos os valores do enum "set", que você pode usar para testar a inclusão contra, da mesma forma como o Conjunto.Também, porque é uma classe completa, você pode definir novos métodos estáticos para fazer o composto de lógica (como eu estava tentando fazer alusão a no código de exemplo).A única coisa sobre o Enum é que você não pode adicionar novas instâncias em tempo de execução, que pode não ser o que você quiser (no entanto, se o conjunto de dados de tamanho não vai crescer em tempo de execução, o Enum é o que você quer).
Outras dicas
No .NET, o que você provavelmente está procurando é KeyEdCollectionhttp://msdn.microsoft.com/en-us/library/ms132438.aspx
Você pode contornar a maldade de reimplementar essa classe abstrata cada vez com alguma inteligência "genérica". (Veja ikeyedObject`1.)
NOTA: Qualquer objeto de transferência de dados que implemente o iKeyEdObject`1 deve ter um método GethashCode substituído simplesmente retornando isso.Key.gethashCode (); E o mesmo vale para iguais ...
Minha biblioteca de classe base geralmente acaba com algo assim:
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; }
}
Se você alterar um objeto após o inserido, o hash poderá ter mudado (isso é especialmente provável se o hashCode () tiver sido substituído). Se o hash mudar, uma pesquisa no conjunto falhará, pois você tentará procurar um objeto que seja hashed em um local diferente do que está armazenado.
Além disso, você precisa ter certeza de que você substituiu o HashCode e é igual ao seu objeto se deseja procurar objetos iguais que sejam instâncias diferentes.
Observe que isso é tudo para o Java - estou assumindo que C# tem algo semelhante, mas, como já faz vários anos desde que usei C#, deixarei que outras pessoas falem com suas capacidades.
Eu imagino os designers do Set interface e HashSet aula queria garantir que o remove(Object) método definido no Collection A interface também foi aplicável a Set; Este método retorna um booleano denotando se o objeto foi removido com sucesso. Se os designers quisessem fornecer funcionalidade pela qual remova (objeto) retornou o objeto "igual" já no Set Isso significaria uma assinatura de método diferente.
Além disso, dado que o objeto removido é logicamente igual ao objeto passado para remover (objeto), é discutível sobre o valor agregado ao retornar o objeto contido. No entanto, eu mesmo tive esse problema antes e já usei um mapa para resolver o problema.
Observe que em Java, um HashSet usa a HashMap internamente e, portanto, não há sobrecarga adicional de armazenamento no uso de um HashMap em vez de.
Por que não usar apenas um HashMap<X,X>? Isso faz exatamente o que você deseja. Apenas faça .put(x,x) toda vez e então você pode apenas obter o elemento armazenado igual a x com .get(x).
Foi uma supervisão dos designers da biblioteca. Como mencionei em outra resposta, este método foi adicionado a .NET Framework 4.7.2 (e .NET Core 2.0 antes dele); Vejo HashSet<T>.TryGetValue. Citando a fonte:
/// <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)
Parece -me que você está realmente procurando por um Map<X,Y>, onde y é o tipo de extra1.
(Rant abaixo)
Os métodos iguais e hashcode definem igualdade de objeto significativo. A classe Hashset assume que se dois objetos são iguais como definidos por Object.equals(Object) Não há diferença entre esses dois objetos.
Eu iria tão longe quanto dizer que se o object extra é significativo, seu design não é o ideal.
Resolvido. Desejar encontrar um elemento parece perfeitamente válido para mim, porque o representante usado para a pesquisa pode diferir do elemento encontrado. Isso é especialmente verdadeiro se os elementos contiverem informações de chave e valor, e um comparador de igualdade personalizado compara apenas a parte principal. Veja o exemplo do código. O código contém uma comparadora que implementa uma pesquisa personalizada e Isso captura o elemento encontrado. Isso requer uma instância do comparador. Limpe a referência ao elemento encontrado. Executar uma pesquisa por meio de contém. Acesse o elemento encontrado. Esteja ciente dos problemas multithread ao compartilhar a instância do 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
Definir objetos nesses idiomas foram projetados principalmente como conjunto de valor, não para objetos mutáveis. Eles verificam que o objeto colocado neles são únicos usando iguais. É por isso que contém e remove os retornos booleanos, não o objeto: eles verificam ou removem o valor que você passa para eles.
E, na verdade, se você fizer um contém (x) em um conjunto e espere obter um objeto diferente, isso significa que x e y são iguais (ou seja, x.equals (y) => true), mas um pouco diferente, o que parece errado.
Recebi uma sugestão interessante sobre uma maneira de usar um mapa, fazendo com que meus próprios objetos se defina como keyvaluepairs. Embora um bom conceito, infelizmente, o KeyValuepair não é uma interface (por que não?) E é uma estrutura, que atira que o planejamento do ar. No final, rolarei meu próprio conjunto, pois minhas restrições me permitem essa opção.
Resposta curta; Porque os itens não podem ser garantidos como imutáveis.
Apoi o problema exato que você descreve, onde o HashCode é baseado em campos fixos na classe Membro, mas a classe possui informações adicionais que podem ser atualizadas sem alterar o hash.
Minha solução foi implementar um myhashset genéricou003CT> com base na icollectionu003CT> Mas envolveu um dicionário u003Cint, Listu003CT> > Para fornecer a eficiência de pesquisa necessária, onde a tecla INT é o código de hash de T. No entanto, isso mostra que, se o código de hash dos objetos membros puder mudar, a pesquisa do dicionário seguida pela comparação de itens da lista nunca encontrará a mudança alterada Itens. Não há mecanismo para forçar os membros a serem imutáveis, portanto a única solução é enumerar o lote.
Depois de se perguntar a mesma coisa, e ser capaz de olhar para o código -fonte:
fonte: http://referencesource.microsoft.com/#system.core/system/collections/generic/hashset.cs
Um conjunto é uma coleção de itens exclusivos (objetos ou valores). Na implementação do .NET, um item é o mesmo que outro item (não exclusivo) se o método igual do comparador retornar verdadeiro para os dois itens. Não se os dois itens tiverem o mesmo código de hash. Portanto, uma verificação da existência de um item é um processo de duas etapas. Primeiro, usando o hashset para minimizar o número de itens para cometer, depois a própria compactação.
Se você deseja recuperar um item, deve poder fornecer a função de recuperação com um identificador exclusivo. Você pode saber o código de hash do item que deseja. Mas isso não é suficiente. Como mais de um item pode ter o mesmo hash. Você também precisará fornecer o próprio item para que o método igual possa ser chamado. E claramente se você tiver o item, não há razão para obtê -lo.
Pode -se criar uma estrutura de dados que exige que dois itens exclusivos retornem o mesmo código de hash. E do que você poderia obter um item dele. Será mais rápido adicionar*, e a recuperação será possível se você souber o hash. Se dois itens que não forem iguais, mas retornarem, o mesmo hash for colocado nele, o primeiro será substituído. Até onde eu sei, esse tipo não existe no .NET, e não, isso não é o mesmo que um dicionário.
*Dado que o método Gethash é o mesmo.
