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

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

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

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

Answer 2

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

Answer 3

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

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

Is it faster to search for a large string in a DB by its hashcode?

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

Answer 4

Я бы сказал, вариант 1.

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

, что об использовании KeyObj.GetHashCode()?

Answer 7

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

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

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

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

Answer 8

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

Answer 9

Вы можете использовать вариант 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 10

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

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 strkey стоимости (тик): 12 strkey стоимости (мс): 0 intkey стоимости (тик): 66 intkey cost (ms): 0