2

I have a class that only uses the keyCollection of a Dictionary<long, object>, and I would like to pass to other class only the keys.

I know that the dictionary has a theorical O(1) access-by-index (as a HashTable) but if I convert the keyCollection to a List, the access would change to O(n).

How could I pass the keyCollection to my class maintaining the O(1) access?

EDIT: I'm using .NET 2.0.

Thanks in advance.

Daniel Peñalba
  • 30,507
  • 32
  • 137
  • 219
  • Define "access"... if you mean "read by index", the access remains O(1), and indeed is a must *faster* O(1) than a hash-table. Indeed, the O(1) only applies to access-the-value-by-key, which makes no sense in a list **of the keys** - what is it you want to do with the list? – Marc Gravell Jan 11 '12 at 09:56
  • @MarcGravell: Yes, I mean acces by index (.Contains()) – Daniel Peñalba Jan 11 '12 at 09:58
  • @MarcGravell: I need the key collection only to know if the dictionary CONTAINS certain key values, so I only need the keys. – Daniel Peñalba Jan 11 '12 at 10:01
  • Related: https://stackoverflow.com/questions/8235840/dictionary-keys-contains-vs-containskey-are-they-functionally-equivalent – nawfal May 18 '18 at 05:26

1 Answers1

6

In a comment, you mention that your intent here is .Contains(). In that case, what you are looking for is HashSet<T>, which does exactly that - it just holds keys (no values), and provides fast Contains checks. So; for your Dictionary<long,object> you could do something like:

var set = new HashSet<long>(dictionary.Keys);

and pass that over. For convenience, HashSet<T> implements ICollection<T> (if you want to scope it to an interface, rather than the concrete type) - this has a Contains too.

Actually, it may be more efficient to use (which also works on .NET 2.0):

ICollection<long> = dictionary.Keys;

and pass that; the implementation of Contains(key) on this is O(1), since it is implemented via:

bool ICollection<TKey>.Contains(TKey item)
{
    return this.dictionary.ContainsKey(item);
}
Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900
  • And, assuming you have control over the class, it should really accept `ISet` rather than `HashSet`. (To avoid having to copy the keys from the dictionary to a set you could create a wrapper class which takes a dictionary and implement the `ISet` methods.) – porges Jan 11 '12 at 10:02
  • Thanks, that was exactly I was asking. Thanks. – Daniel Peñalba Jan 11 '12 at 10:03
  • @Porges `ISet` doesn't provide many useful methods for this case, actually - it is the `ICollection` (which `ISet` demands) which is useful. – Marc Gravell Jan 11 '12 at 10:05
  • This is true... just substitute `ICollection` into what I said, then. ;) – porges Jan 11 '12 at 10:06
  • @MarcGravell: Arrg, It's new on .NET 4.0. I'm using .NET 2.0. What about the Contains() performance of the KeyCollection? – Daniel Peñalba Jan 11 '12 at 10:07
  • @DanielPeñalba it is in 3.5, actually; and KeyCollection has no Contains() method. Edit: oops, the `KeysCollection` implements `ICollection` - should work fine – Marc Gravell Jan 11 '12 at 10:10
  • @Daniel: Please remember next time to add details like framework version to your question, so that people don't invest too much time into an answer that won't work for you. – Tim Schmelter Jan 11 '12 at 10:11
  • Actually, the `KeyCollection` returned by `Keys` has `O(1)` lookup. It just calls the underlying dictionary's `ContainsKey`. So, you don't need to do any extra work apart from accepting an `ICollection`. – porges Jan 11 '12 at 10:12
  • @MarcGravell: KeyCollection does have Contains, it's just that it's an explicit interface implementation. – porges Jan 11 '12 at 10:13
  • @Porges: Wow, I thought that KeyCollection was O(n), perfect, so, please, could you post your answer, converting to ICollection. I will mark as answered. – Daniel Peñalba Jan 11 '12 at 10:15
  • @DanielPeñalba actually, it looks like just using the `ICollection` aspect of `KeyCollection<,>` will work fine; I've checked it in reflector - it is `bool ICollection.Contains(TKey item) { return this.dictionary.ContainsKey(item); } ` – Marc Gravell Jan 11 '12 at 10:16
  • @DanielPeñalba also; an *interface* **does not have** a defined O(?) - it is only specific implementations where that makes sense. In this case, `KeyCollection<,>` implements `ICollection.Contains` in an O(1) way. – Marc Gravell Jan 11 '12 at 10:18
  • @MarcGravell: Good point, I meant KeyCollection is O(1) not ICollection (sorry). – Daniel Peñalba Jan 11 '12 at 10:20
  • Someone wants to post the answer? – Daniel Peñalba Jan 11 '12 at 10:21