Выбор хорошего словарного ключа

Question

У меня есть объект, который я хочу использовать для поиска других объектов. Я буду использовать Dictionary<TKey, TValue>().

Ключевой объект имеет две строки, которые однозначно идентифицируют его, скажем KeyObj.Str1 и KeyObj.Str2.

Что вы рекомендуете использовать в качестве ключа для словаря?

1: конкатенация строк.

Dictionary<String, TValue>();
Key = KeyObj.Str1:KeyObj.Str2; ("somestring:anotherstring")

2: уникальное целое число для каждого объекта, чтобы идентифицировать его?

Dictionary<int, TValue>();
KeyObj.ID = _nextID++;
Key = KeyObj.ID;

3: ссылка на объект.

Dictionary<KeyObj, TValue>();
Key = KeyObj;

Вариант 3 будет самым простым, но, похоже, будет неэффективно индексировать словарь на основе ссылочных значений.

Если бы ключевой объект содержал одну уникальную строку, очевидным выбором было бы использовать ее, но наличие двух уникальных по комбинации строк усложняет задачу.

Answer 1

Вы можете использовать опцию 3, если вы можете переопределить GetHashCode () и Equals () соответственно, то есть что-то вроде этого:

    public override int GetHashCode()
    {
        return str1.GetHashCode() ^ str2.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if (!obj is KeyObj)
        {
            return false;
        }

        KeyObj key = (KeyObj)obj;
        return this.str1.Equals(key.str1) && this.str2.Equals(key.str2);
    }

Answer 2

Объединенные строки должны работать лучше всего.

Если вы знаете, что их комбинация уникальна, то это то, что вы должны выбрать - помните, что хэш-код обычно уникален, но не всегда.

Answer 3

Любое из них допустимо, но я предполагаю, что вы захотите быстро найти эти объекты на основе одной из двух строк, поэтому использование int в качестве ключа будет означать, что вам все равно придется сканировать значения, чтобы найти нужный объект.

Являются ли строки одновременно уникальными или только в сочетании? Если они оба уникальны, и вы готовы торговать немного места, вы можете сделать:

dict.Add(KeyObj.Str1, KeyObj);
dict.Add(KeyObj.Str2, KeyObj);

и имеют две ссылки на объект в словаре, используя каждую уникальную строку в качестве ключа. Или вы всегда можете просто объединить строки, если они уникальны, и использовать внутренний хеш-код для их поиска.

Answer 4

как насчет использования KeyObj.GetHashCode ()?

Answer 5

Объединение их, вероятно, лучшая идея. Вы можете предоставить свойство в объекте KeyObj, который выполняет конкатенацию, поэтому вам не придется выполнять его каждый раз, когда вы получаете доступ к значению словаря.

Edit:

Я явно неправильно понял вопрос. Я думаю, что вы действительно хотите сделать это сочетание 1 и 3, вы можете переопределить Equals() и GetHashCode(), чтобы использовать string s, которые уникально идентифицируют объект (просто убедитесь, что они неизменны!)

public override Equals(object obj) 
{
   if (obj == null || !(obj is KeyObj))
      return false;
   KeyObj other = (KeyObj)obj;
   if (this.Key1 == other.Key1 && this.Key2 == other.Key2)
     return true;
   return false;
}

public override GetHashCode()
{
    return (this.Key1 + this.Key2).GetHashCode();
}

Тогда вы можете использовать 3-й вариант, который вы предложили:

Dictionary<KeyObj, ValueObj>...

Answer 6

строка в качестве ключа является лучшим, см. Мой тестовый код:

var tupleKeyDict = новый словарь, строка> ();

        for (int i = 0; i < 1000000; i++)
        {
            tupleKeyDict.Add(new Tuple<int, int>(i,0),i.ToString() );
        }

        System.Diagnostics.Stopwatch stopWatch = new Stopwatch();
        stopWatch.Start();
        string e1 = tupleKeyDict[new Tuple<int, int>(0, 0)];
        string e2 = tupleKeyDict[new Tuple<int, int>(500000, 0)];
        string e3 = tupleKeyDict[new Tuple<int, int>(999999, 0)];
        stopWatch.Stop();
        Console.WriteLine("Tuplekey cost(tick): " + stopWatch.ElapsedTicks.ToString());
        Console.WriteLine("Tuplekey cost(ms): " + stopWatch.ElapsedMilliseconds.ToString());





        var strKeyDict = new Dictionary<string, string>();

        for (int i = 0; i < 1000000; i++)
        {
            strKeyDict.Add(i.ToString() + ":0", i.ToString());
        }

        System.Diagnostics.Stopwatch stopWatch2 = new Stopwatch();
        stopWatch2.Start();
        string se1 = strKeyDict["0:0"];
        string se2 = strKeyDict["500000:0"];
        string se3 = strKeyDict["999999:0"];
        stopWatch2.Stop();
        Console.WriteLine("strkey cost(tick): " + stopWatch2.ElapsedTicks.ToString());
        Console.WriteLine("strkey cost(ms): " + stopWatch2.ElapsedMilliseconds.ToString());




        var intKeyDict = new Dictionary<int, string>();

        for (int i = 0; i < 1000000; i++)
        {
            intKeyDict.Add(i, i.ToString());
        }

        System.Diagnostics.Stopwatch stopWatch3 = new Stopwatch();
        stopWatch3.Start();
        string ie1 = intKeyDict[0];
        string ie2 = intKeyDict[500000];
        string ie3 = intKeyDict[999999];
        stopWatch3.Stop();
        Console.WriteLine("intkey cost(tick): " + stopWatch3.ElapsedTicks.ToString());
        Console.WriteLine("intkey cost(ms): " + stopWatch3.ElapsedMilliseconds.ToString());

Выход: Стоимость Tuplekey (галочка): 104 Стоимость Tuplekey (мс): 0 стоимость (тик): 12 стоимость ключа (мс): 0 стоимость intkey (галочка): 66 Стоимость intkey (мс): 0

Answer 7

Помните, что словарь - это прославленная хеш-таблица, поэтому ключ (без каламбура) состоит в том, чтобы использовать ключ, который приведет к очень небольшому количеству (если таковые имеются) столкновений с другим ключом. Я бы склонился к # 3, но это при условии, что тип KeyObj имеет хороший генератор хеш-значений.

Answer 8

Если производительность является основным фактором, вы можете использовать хеш-значение двух строк. Но тогда ваше поле 'value' должно будет содержать и ключи, и значение.

У меня есть ссылка на другой ТАК вопрос, я просто должен найти его.

Можно ли быстрее искать большую строку в БД по ее хэш-коду?

Но этот вопрос больше ориентирован на БД. И производительность считается за тысячи итераций.

Answer 9

Вам не нужно использовать новый класс в качестве ключа словаря. Вместо этого используйте новую структуру, так как она будет намного более легкой ... И она, очевидно, будет состоять из этих двух строковых значений.