双向哈希表

Itay Sagui

2.12/5 (7投票s)

2005 年 11 月 1 日

CPOL

2分钟阅读

23954

245

创建一个双向哈希表，在 O(1) 时间内访问键和项目，并在项目之间建立连接。

引言

虽然你不能否认 Hashtable 的优点，但有时它是不够的。有时你需要更好的二元性——从它的键访问对象，以及从对象访问键。这变得非常有用和重要，因为基本的 Hashtable 允许你使用几乎任何对象作为键。

一个很好的例子是在 TreeView 中显示复杂对象。从其匹配的 TreeNode 检索复杂对象，反之亦然，非常方便。这样，你可以轻松地获取选定的项目，或跳转到某个节点。

实现

这种双向哈希表的实现非常简单。所要做的就是保留两个简单的 Hashtable - 一个是键和对象扮演它们正常的部分。但是，在另一个 Hashtable 中，角色被交换 - 对象被用作键，而键被保存在 Hashtable 中作为值。

public void AddItem(object key, object item)
{
    if (keysToItems.ContainsKey(key) || itemsToKeys.ContainsKey(item))
    {
        keysToItems.Remove(key);
        itemsToKeys.Remove(item);
    }
    keysToItems[key] = item;
    itemsToKeys[item] = key;
}

private Hashtable keysToItems = new Hashtable();
private Hashtable itemsToKeys = new Hashtable();

一旦完成，你所要做的就是提供方法来轻松处理这样的类。当然，需要诸如 GetKey() 和 GetItem() 之类的方法，以及相应的 Remove 方法。

public object GetKey(object item)
{
    if (item == null)
        throw new ArgumentNullException("keitemy");

    return itemsToKeys[item];
}

public object GetItem(object key)
{
    if (key == null)
        throw new ArgumentNullException("key");

    return keysToItems[key];
}

public void RemoveByKey(object key)
{
    if (key == null)
        throw new ArgumentNullException("key");

    object item = keysToItems[key];
    keysToItems.Remove(key);
    itemsToKeys.Remove(item);
}

public void RemoveByItem(object item)
{
    if (item == null)
        throw new ArgumentNullException("item");

    object key = itemsToKeys[item];
    keysToItems.Remove(key);
    itemsToKeys.Remove(item);
}

你还可以提供一个索引器，但我只推荐在实现强类型双向哈希表时使用它，因为使用弱类型索引会将索引是键还是对象的决定留给类。仅当你可以确保同一对象不能同时用作键和值时，这才能奏效。

摘要

虽然这是一个非常基本的问题，但它的用途很多，它肯定会 облегчить 程序员的生活，并使代码更清晰，更易于维护。当然，在 VS2005 中使用泛型使一切变得更加简单和清晰。

历史

2005 年 4 月 11 日 - 根据 tonyt 和 leppie 的评论，现在添加项目时会检查之前项目的存在并删除它们。