Best structure for accessing an object knowing a unique property

Question

I have an array of elements that I need to access quite often, and quite fast. I know that a property from those elements is unique and I inject the array into a wrapper class, which builds a dictionary from this property. Since a dictionary access is way faster than a LINQ query on the array, I thought that'd be efficient.

But, despite it is working well, the solution looks a bit weird : I am storing the object as a value into the dictionary, and part of it as a key.

Is there any better suited structure/way of doing it?

 public class FooItem
{

    public string Id { get; set; } //UNIQUE

    public double Value1 { get; set; }
    public string Value2 { get; set; }

}

public class FoosManager
{
    private Dictionary<string, FooItem> _dic;

    public FooManager(IEnumerable<FooItem> items) {
        _dic = new Dictionary<string, FooItem>(
            items.ToDictionary(x => x.Id, x => x),
            StringComparer.OrdinalIgnoreCase);
    }

    public FooItem this[string id] => GetItem(id); //Indexer

    private FooItem GetItem(string id) {
        if (_dic.ContainsKey(id)) 
            return null;

        return _dic[id];
    }

}

It's perfectly normal to have a dictionary where the values are objects, and the keys are the IDs of those objects. — Jonas Høgh, Oct 03 '19 at 09:33
@JonasHøgh ok, good to know. So this is the most efficient way of doing it in terms of lookup speed? — XavierAM, Oct 03 '19 at 09:36
`private FooItem GetItem(string id) => _dic.TryGetValue(id, out var item) ? item : null;` — Dmitry Bychenko, Oct 03 '19 at 09:39
I think your FoosManager class is largely redundant. It doesn't really add anything that storing the dictionary as an IReadonlyDictionary wouldn't give you — Jonas Høgh, Oct 03 '19 at 09:39
@JonasHøgh point taken, I use it mostly for securing serialization/deserialization from JSON (especially the dictionary serialization) through methods not represented here. Does it induce a performance issue since 1- it is instantiated once for all 2- it is mostly transparent , forwarding the call to the dictionary — XavierAM, Oct 03 '19 at 09:42
If you used to live with a linear array search on every lookup, you can most likely live with an extra method call, assuming the JIT cannot inline it. — Jonas Høgh, Oct 03 '19 at 09:48
@JonasHøgh I never lived with a linear array search on every lookup, what do you mean? — XavierAM, Oct 03 '19 at 10:16
@XavierAM you implied that you were using Linq to search for the FooItems previously, that would probably have linear running time. Anyway, I wouldn't worry about the number of calls unless you're on an extremely hot code path. — Jonas Høgh, Oct 03 '19 at 10:38
@JonasHøgh ok my bad, this was an english mistake then. I actually never used LINQ to search for items, I was just explaining my thinking. Anyway, thanks for your help. — XavierAM, Oct 03 '19 at 10:43

Dmitry Bychenko · Accepted Answer · 2019-10-04T08:11:43.927

You can simplify your code into

public class FoosManager {
  private Dictionary<string, FooItem> _dic;

  public FooManager(IEnumerable<FooItem> items) {
    if (null == items)
      throw new ArgumentNullException(nameof(items));

    // Let's do it in one go:
    _dic = items.ToDictionary(
       item => item.Id, 
       item => item, 
       StringComparer.OrdinalIgnoreCase);
  }

  // No need in GetItem, ContainsKey etc.
  public FooItem this[string id] => 
    _dic.TryGetValue(id, out var value) ? value : null;
}

As for FooItem I'd make it immutable (at least, Id; otherwise one can put FooItem into FoosManager and then change the Id)

  public class FooItem {
    public FooItem(string id, double value1, string value2) {
      if (null == id)
        throw new ArgumentNullException(nameof(id)); 

      Id = id;
      Value1 = value1;
      Value2 = value2;
    } 

    public string Id { get; } 

    public double Value1 { get; }
    public string Value2 { get; }
  }

score 1 · Answer 2 · answered Oct 03 '19 at 22:51

Using strings as keys of the Dictionary, the same strings that are stored in the Id property, is OK because the strings are not copied. Only references to the string are copied (8 bytes per reference according to my tests). Unless of course you create explicitly copies like this:

var dictionary = items.ToDictionary(x => new String(x.Id.ToCharArray()));

In this case the memory allocated for the strings will be doubled, although the functionality of the Dictionary will remain unaffected.

Great! Thanks for this detailed answered. – XavierAM Oct 04 '19 at 06:05 — XavierAM, Oct 04 '19 at 06:05

Best structure for accessing an object knowing a unique property

2 Answers2