Почему я не могу получить элемент из HashSet без перечисления?
https://stackoverflow.com/questions/1494812
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я ищу информацию о головах дизайнеров HashSet.Насколько мне известно, мой вопрос касается как Java, так и C# HashSets, что заставляет меня думать, что для этого должна быть какая-то веская причина, хотя я сам не могу придумать ни одной.
Почему после того, как я вставил элемент в HashSet, невозможно получить этот элемент без перечисления, что вряд ли является эффективной операцией?Тем более, что HashSet явно создан таким образом, чтобы поддерживать эффективный поиск.
Мне часто было бы полезно, чтобы функции Remove(x) и contains(x) возвращали фактический элемент, который удаляется или удерживается.Это не обязательно тот элемент, который я передаю в функцию Remove(x) или contains(x).Конечно, я думаю, что мог бы добиться того же эффекта с помощью HashMap, но зачем тратить все это пространство и усилия, если вполне возможно сделать это с помощью набора?
Я понимаю, что могут возникнуть некоторые проблемы с дизайном, связанные с тем, что добавление этой функциональности позволит использовать HashSet, что не соответствует их роли или будущей роли в структуре, но если это так, то каковы эти проблемы с дизайном?
Редактировать
Чтобы ответить на еще несколько вопросов, вот более подробная информация:
Я использую неизменяемый ссылочный тип с переопределенным хэш-кодом, равенствами и т. д. для эмуляции типа значения в C#.Допустим, у типа есть члены A, B и C.Хэш-код, равенства и т. д. зависят только от A и B.Учитывая некоторые A и B, я хочу иметь возможность получить этот эквивалентный элемент из хэш-набора и получить его C.Похоже, я не смогу использовать для этого HashSet, но мне бы хотелось хотя бы знать, есть ли для этого веская причина.Псевдокод следующий:
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
Решение
Как вы предлагали получить элемент из хеш-набора?Набор по определению никак не упорядочен, и поэтому не существует индекса, который можно было бы использовать для извлечения рассматриваемого объекта.
Наборы как концепция используются для проверки включения, т.е.находится ли рассматриваемый элемент в наборе хеш-данных.Если вы хотите получить значение из источника данных, используя ключевое значение или индекс, я бы предложил изучить либо карта или Список.
РЕДАКТИРОВАТЬ:Дополнительный ответ на основе редактирования исходного вопроса
Вскоре, судя по вашей новой информации, похоже, вас может заинтересовать реализация ваших данных в виде Java Enum, что-то вроде этого:
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 автоматически наследует значения(), которая возвращает список всех значений в «наборе» перечисления, который вы можете использовать для проверки включения так же, как и Set.Кроме того, поскольку это полный класс, вы можете определить новые статические методы для выполнения составной логики (как я пытался указать в примере кода).Единственное, что касается Enum, это то, что вы не можете добавлять новые экземпляры во время выполнения, что может быть не тем, что вам нужно (хотя, если размер данных набора не будет расти во время выполнения, Enum - это то, что вам нужно).
Другие советы
В .Net вы, вероятно, ищете KeyedCollection.http://msdn.microsoft.com/en-us/library/ms132438.aspx
Вы можете обойти неприятности повторной реализации этого абстрактного класса каждый раз, проявив некоторую «общую» хитрость.(См. IKeyedObject`1.)
Примечание:Любой объект передачи данных, реализующий IKeyedObject`1, должен иметь переопределенный метод GetHashCode, просто возвращающий this.Key.GetHashCode();и то же самое касается равных...
Моя библиотека базовых классов обычно имеет что-то вроде этого:
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; }
}
Если вы измените объект после того, как он был вставлен, его хэш мог измениться (это особенно вероятно, если hashCode() был переопределен).Если хэш изменится, поиск его в наборе завершится неудачно, поскольку вы будете пытаться найти объект, хешированный в другом месте, отличном от того, в котором он хранится.
Кроме того, вам необходимо убедиться, что вы переопределили hashCode и равенства в своем объекте, если вы хотите найти равные объекты, которые являются разными экземплярами.
Обратите внимание, что это все для Java — я предполагаю, что в C# есть что-то похожее, но, поскольку с тех пор, как я использовал C#, прошло уже несколько лет, я позволю другим рассказать о его возможностях.
Я представляю себе дизайнеров Set интерфейс и HashSet класс хотел гарантировать, что remove(Object) метод, определенный на Collection интерфейс также был применим к Set;этот метод возвращает логическое значение, указывающее, был ли объект успешно удален.Если дизайнеры хотели обеспечить функциональность, при которой метод remove(Object) возвращал «равный» объект, уже находящийся в Set это будет означать другую сигнатуру метода.
Кроме того, учитывая, что удаляемый объект логически равен объекту, переданному в команду remove(Object), возникают споры о значении, добавленном при возврате содержащегося объекта.Однако у меня раньше была эта проблема, и я использовал карту для ее решения.
Обратите внимание, что в Java HashSet использует HashMap внутренне, поэтому при использовании HashMap вместо.
Почему бы просто не использовать HashMap<X,X>?Это делает именно то, что вы хотите.Просто делать .put(x,x) каждый раз, а затем вы можете просто получить сохраненный элемент, равный x, с помощью .get(x).
Это была недосмотр со стороны проектировщиков библиотеки.Как я уже упоминал под другой ответ, этот метод был добавлен в .NET Framework 4.7.2 (и .NET Core 2.0 перед этим);видеть HashSet<T>.TryGetValue.Цитирование источник:
/// <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)
Мне кажется, ты действительно ищешь Map<X,Y>, где Y — тип extra1.
(разглагольствование ниже)
Методы Equals и hashCode определяют значимое равенство объектов.Класс HashSet предполагает, что если два объекта равны, как определено Object.equals(Object) между этими двумя объектами нет разницы.
Я бы даже сказал, что если object extra имеет смысл, ваш дизайн не идеален.
РЕШЕНО.Желание найти элемент кажется мне вполне обоснованным, поскольку представитель, используемый для поиска, может отличаться от найденного элемента.Это особенно верно, если элементы содержат информацию о ключах и значениях, а пользовательский компаратор равенства сравнивает только ключевую часть.См. пример кода.Код содержит компаратор, реализующий пользовательский поиск. и который фиксирует найденный элемент.Для этого требуется экземпляр компаратора.Очистите ссылку на найденный элемент.Выполните поиск с помощью Содержит.Доступ к найденному элементу.Помните о проблемах многопоточности при совместном использовании экземпляра компаратора.
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
Объекты-множества в этих языках в основном разрабатывались как наборы значений, а не для изменяемых объектов.Они проверяют уникальность помещенного в них объекта, используя равенство.Вот почему contains и delete возвращают логическое значение, а не объект:они проверяют или удаляют значение, которое вы им передаете.
И на самом деле, если вы выполняете contains(X) для набора и ожидаете получить другой объект Y, это будет означать, что X и Y равны (т.е. X.equals(Y) => true), но несколько различны, что кажется неправильным.
Мне было предложено интересное предложение относительно способа использования карты: заставить мои собственные объекты определять себя как KeyValuePairs.Хотя это хорошая концепция, к сожалению, KeyValuePair не является интерфейсом (почему бы и нет?), а представляет собой структуру, которая запускает этот план из воздуха.В конце концов я создам свой собственный набор, поскольку мои ограничения позволяют мне эту возможность.
Короткий ответ;потому что невозможно гарантировать, что элементы будут неизменяемыми.
Я столкнулся именно с той проблемой, которую вы описываете, когда HashCode основан на фиксированных полях внутри класса-члена, но класс содержит дополнительную информацию, которую можно обновить без изменения хеша.
Мое решение заключалось в реализации универсального MyHashSet<T> на основе ICollection<T>, но обернутого вокруг Dictionary<int, List<T>>, чтобы обеспечить требуемую эффективность поиска, где ключ int является HashCode T.Однако это показывает, что если HashCode объектов-членов может измениться, то поиск по словарю с последующим сравнением элементов в списке на равенство никогда не найдет измененные элементы.Не существует механизма, позволяющего сделать элементы неизменяемыми, поэтому единственное решение — перечислить лот.
Задумавшись о том же и имея возможность просмотреть исходный код:
источник: http://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs
Набор — это совокупность уникальных элементов (объектов или значений).В реализации .net элемент совпадает с другим элементом (не уникальным), если метод Equals компаратора возвращает true для двух элементов.Нет, если эти два элемента имеют одинаковый хэш-код.поэтому проверка существования элемента представляет собой двухэтапный процесс.сначала используется хеш-набор, чтобы минимизировать количество сравниваемых элементов, а затем само сжатие.
Если вы хотите получить элемент, вы должны иметь возможность предоставить функции извлечения уникальный идентификатор.возможно, вы знаете хеш-код нужного элемента.Но этого недостаточно.поскольку несколько элементов могут иметь один и тот же хэш.вам также потребуется предоставить сам элемент, чтобы можно было вызвать метод Equal.и очевидно, что если предмет у вас есть, то нет причин его приобретать.
Можно создать структуру данных, которая требует, чтобы никакие два уникальных элемента никогда не возвращали один и тот же хеш-код.и чем вы могли бы получить из него предмет.добавление* будет происходить быстрее, а извлечение будет возможно, если вы знаете хэш.если в него помещены два элемента, которые не равны, но возвращают один и тот же хэш, первый будет перезаписан.насколько я знаю, этот тип не существует в .net, и нет, это не то же самое, что словарь.
*при условии, что метод GetHash тот же.
