搜索哈希集的最佳方式

本文关键字：方式 最佳 哈希集 搜索 | 更新日期: 2023-09-27 18:24:23

我有一个Obj的HashSet，其中Obj定义如下：

public class Obj 
{
    private int _id;
    private string _desc;
    private int _sum;
    public int Id
    {
        get { return _id; }
        set { _id = value; }
    }
    public string Description
    {
        get { return _desc; }
        set { _desc = value; }
    }
    public int Sum
    {
        get { return _sum; }
        set { _sum = value; }
    }
    public Obj(int id, string desc, int sum)
    {
        _id = id;
        _sum = sum;
        _desc = desc;
    }
    public override bool Equals(Obj other)
    {
        return this._sum == other._sum 
            && this._desc == other._desc;
    }
    public override int GetHashCode()
    {
        int hash = 13;
        hash = (hash * 7) + _sum.GetHashCode();
        hash = (hash * 7) + _desc.GetHashCode();
        return hash;
    }
}

这很好，但当HashSet.Add(obj)返回false时，我在从HashSet检索时遇到了问题。在这种情况下，检索已经包含在HashSet中的Obj的_id的最佳方式是什么？

搜索哈希集的最佳方式

我的看法是：sum+description（用于hashcode，equals）=key，_id（您想要检索的内容）=value。

这个场景显然指向一个字典，而不是一个哈希集。。。。集合不适用于任意查找/检索。

myHashSet.First(x => x.Equals(myItemToRetrieve)).Id;

另一种方法是使用字典（键值相等）：

（假设您已将其转换）：

Obj temp;
if (theDictionary.TryGetValue(myItemToRetrieve, out temp))
{
    int ID = temp.Id;
}
else
{
    theDictionary[myItemToRetrieve] = myItemToRetrieve;
}

您可以定义自己的集合类型，该类型构建在Dictionary<TKey, TValue>上并提供GetOrAdd方法（类似于ConcurrentDictionary<TKey, TValue>的GetOrAdd）：

public partial class HashDictionary<T> : Dictionary<T, T>
{
    public T GetOrAdd(T newItem)
    {
        T oldItem;
        if (this.TryGetValue(newItem, out oldItem))
            return oldItem;
        this.Add(newItem, newItem);
        return newItem;
    }
}

要使用此功能，您可以调用：

Obj presentO = myHashDictionary.GetOrAdd(newO);
if (presentO == newO)
{
    // The item was not already present, and has been added.
}
else
{
    // A collision occurred, and presentO points to the existent item.
    int alreadyContainedID = presentO.ID;
}

为了保持与当前代码的兼容性，您可以扩展此类来实现ICollection<T>（或者，最好是ISet<T>）：

public partial class HashDictionary<T> : ICollection<T>
{        
    public void Add(T item)
    {
        this.GetOrAdd(item);
    }
    public bool Contains(T item)
    {
        return this.ContainsKey(item);
    }
    public void CopyTo(T[] array, int arrayIndex)
    {
        this.Keys.CopyTo(array, arrayIndex);
    }
    public bool IsReadOnly
    {
        get { return false; }
    }
    public new IEnumerator<T> GetEnumerator()
    {
        return this.Keys.GetEnumerator();
    }
}

我以前遇到过这种情况。当然，我使用的是字典<TKey、TValue>，这使得更容易基于密钥来获得对象。当您重写哈希代码时，一个问题是哈希表等根据INITIAL值存储记录。因此，如果你稍微篡改一下对象，你将无法再恢复对象，因为哈希代码已经更改。因此，我使用的技巧是用一个单独的方法（如）生成一个整数哈希代码

private hashcode;
public void UpdateHashCode(){
   hashcode = // your original logic here.
}

这样，您就可以控制哈希代码何时更新，这样您仍然可以找到旧对象。从字典中删除它，然后更新对象，然后存储修改后的对象。

但纯粹主义者不会喜欢这样，因为这意味着严格的等式测试和哈希测试无法在未更新哈希的修改对象上正确工作。因此，您可以将旧的哈希代码作为一个单独的属性来跟踪，该属性只有在您将其添加到字典中时才会更新。

private int oldHashcode;
public int OldHashcode{
   get{
       return oldHashCode;
   }
   set {
       oldHashCode = value;
   }
}

当你添加到字典中时：

item.OldHashCode = item.GetHashCode();

并检索

item = myDictionary[item.OldHashCode];

或者其他什么。

相关文章：