Which dictionary to choose in C# and which one is dangerous

Subscribe: bit.ly/ChapsasSub
Check out my courses: dometrain.com
Become a Patreon and get source code access: / nickchapsas
Hello everybody I'm Nick and in this video I will talk about the different dictionary types in C# and also the hashtable and how we can use them in different scenarios. I will also talk about one of the most common pitfalls that I've personally have fallen into unknowingly.
Don't forget to comment, like and subscribe :)
Social Media:
Follow me on GitHub: bit.ly/ChapsasGitHub
Follow me on Twitter: bit.ly/ChapsasTwitter
Connect on LinkedIn: bit.ly/ChapsasLinkedIn
Keep coding merch: keepcoding.shop
#csharp #dotnet

[@nickchapsas]

For the record, whether the ImmutableDictionary is smart about allocations during its Add/Update/Remove operations doesn't really matter to me since I haven't met a single person that was aware of its underlying data structure. I personally used to choose an ImmutableDictionary because all I want is to return a dictionary that you can't change its values in any way, so I can't get behind a data structure that is smart about how it can be changed into a new datastructure efficiently when that's not the usecase I wanted anyway. Getting a value is O(log n) and that's all that matters to me. Of course this is just me and it's just one usecase but it looks like I much rather go with a ReadOnlyDictionary for that specific usercase. This also has to do with C# not being an immutability first language. When ImmutableDictionary is an AVL tree and ReadOnlyDictionary is a hash table, but then the "readonly" keyword is used to create immutable elements in your code, then you know that naming is kinda inconcistent and it leaves a lot room for assumptions.

[@LinusSwanberg]

Thank you for creating great content, as always. How does the ReadOnlyDictionary perform?

[@talwald1680]

The idea of immutable dictionary is to allow creating versions without a full copy. If you just want to return a readonly dictionary then you should just do that. But aside from that great episode!

[@notmeprobably_]

@@LinusSwanberg The Readonlydictionary performance depends on the performance of the IDictionary implementation passed to its constructor. Normally this is just Dictionary, so it's O(1), but someone could make a worse implementation if they wanted to and it would make the corresponding Readonlydictionary worse.

[@Andrei15193]

I have similar issues where I want to return a read-only instance of a collection from a method, but I would like that instance to be mutable inside the method that is generating it. I ended up using one of the read-only interfaces that most collections implement (Dictionary implements IReadOnlyDictionary so I can return an instance directly without using any sort of wrapper, same with List and Arrays which implement IReadOnlyList which in turn extends IReadOnlyCollection). The only wrapper I use is the ReadOnlyObservableCollection, but that is only in WPF applications.

[@urbanelemental3308]

So I ran my own BenchmarkDotNet results and just to be sure, a few home cooked ones. I'm baffled that ImmutableDictionary reads are so slow. Why would they chose to design/engineer it this way? If it means anything, the results are slightly better than a SortedDictionary.

[@pawetarsaa9904]

Topic for the next video: "When you should use structs in C#"

[@clashclan4739]

In my 4+ years of experience never used

[@StephenOwen]

Also would be good to cover, when an abstract type makes sense instead of an interface.

[@Andrew90046zero]

@@clashclan4739 Best usage of structs are for small simple types that you know arent going to be arbitrarily grow over time. Vectors, Color Values, Matrices, Quaternion (rotations). And you can make copies of them easily without allocating more memory.

[@peteruelimaa4973]

The clickbait titles always make my eyes roll but then the content is mostly informative at least.

[@alejandroguardiola9085]

@@clashclan4739 As a quick guideline use structs when the size does not exceeds 16 bytes, take into account that a reference is 8 bytes in most systems so 2 strings are already 16 bytes in pointers. Structs can be good because if used correctly with no boxing/unboxing the GC does not need to clean them up because they are stack allocated.

[@ArtemPyatkovsky]

2 words of caution about ConcurrentDictionary: one is more obvious - Linq with ConcurrentDictionary is not thread safe, use built-in methods like .ToArray() first/instead; TryAdd overload with func which creates instance - the factory funk is not thread protected and can be entered more than once for the same key!

[@vertxxyz]

"in which case... ...sorry." Fantastic delivery hahaha

[@realkompot3904]

SortedDictionary should be here too. The word "dictionary" and the hash table data structure were synonyms to me for a long time too until I learned that "dictionary" is just an abstract type that supports storing and getting value by key with many possible implementations e.g. hash tables and BSTs (I learned it from Skiena's book). It's also interesting how the naming is done in other languages. In c++ standard library, for example, dictionaries are named "maps", and the type name doesn't specify the underlying data structure, but rather the fact if it's ordered or not, just like in .NET: Dictionary std::unordered_map (hash table). SortedDictionary std::map (red-black tree). While in java they decided to make it more explicit: TreeMap and HashMap (both implement Map interface though). Also, in .NET there's also OrderedDictionary (not to be confused with SortedDictionary :=) ).

[@SlackwareNVM]

Thank you for the book recommendation.

[@LiveErrors]

A map is what we also call an associative Array, it's a data structure that's more of a toolbox than a specific structure See Lua Tables for an easy overview

[@user-fp6cr1wi2q]

Teacher: kids, what is result 2 + 2? Nick: 69 to the power of 420

[@leathakkor]

I send these videos to my co-workers because they are informative, but sometimes I forget how terrible/terrific his number choices are

[@brianm1864]

Your title scared me. I was sure you were going to say Dictionary was the dangerous one, and I was like "well I'll watch the video and see what I need to refactor"!

[@orterves]

I was worried he was gonna say concurrent dictionary - luckily not, it's too useful in certain situations

[@gami195]

Hi Nick Thanks for this great video. I like that they are to the point, not tiring and teaching us something. Keep up with great work you doing.

[@wobuntu]

Well, what about HashSet?

[@WillEhrendreich]

nick, you're fantastic, thank you so much for these types of videos. they really do help.

[@MrAndrei4777]

The last part with performance result is very interesting. Thank's Nick! This adds a clearer picture to the subject and proves some statements are right/wrong.

[@peterdeshazer2986]

AVL Tree time complexity is o(lgn) for searching, insert and delete. Hash table have constant average time complex but with o(n) worst case caused by the hash collision.

[@twiksify]

ImmutableDictionary actually had better performance than I expected. Great video and thanks for the insight in it's internal datastructure!

[@casperhansen826]

Some years ago I had issues finding the bottleneck in my code, the problem was that I used an object with two values as the key in a dictionary, I also found that a custom comparer class would hurt the performance of the dictionary. Just a warning to everyone.

[@oleksandr.tomashchuk]

Thank you Nick, as always very nice explained!

[@crikey4336]

A common use case for concurrency is a desire to have a lock-free data structure that supports single-writer, multiple readers in a thread-safe way and that is does not require any locks. Long ago I created such a data structure by tweaking the built-in Dictionary class. In fact the tweak was quite minimal - the main problem with the built-in dictionary class that causes a problem for concurrent reading and writing is that the resize operation (needed sometimes when adding an item to the dictionary) does not take concurrency into account and ends up updating the backing array reference before copying the elements from the old array to the new array. This creates a race-condition whereby readers will temporarily see a version of the dictionary where elements are missing. Tweaking this one piece of the dictionary array expansion makes it thread-safe for single-writer/multiple-readers. I combined this with a read-only interface that is given to readers to prevent them from attempting to modify then completes the picture. Oh, and for some reason I also had to remove the ability to remove items from the dictionary...

I am amateur developer - with no professional skills - but I was thinking that knowing some patterns, syntax and object thinking is enough... but your channel shows to me, that there is much more!!! Thanks a lot for you work - you help (not only me - I am pretty sure) a lot with understanding the background and answering important questions to the question: "But why?" :)

[@ryan-heath]

Great to see they fixed the api from hashtable & synchronized.hashtable to dictionary & concurrentDictionary. In the former the underlying hashtable could still be altered apart from the synchronized.hashtable.

[@queenstownswords]

Very insightful. Thank you Sir.

Great video! I learned a lot again!

[@hemant-sathe]

If you haven’t already, would you please create a video about thread safety? It is something one doesn’t need to care about most of the times but a very critical topic.

[@neociber24]

Aren't SortedList, SortedDictionary and PriorityQueue considered dictionaries as well?

[@Sebazzz1991]

Yes, as there are addressed by key and return a value.

[@Erlisch1337]

Came here to ask about those...

[@lalithmahadev5027]

69 for a random number great choice nick!!!

[@pog8599]

Looking at the previous video, there's certainly something Nick is trying to tell us

[@bl1tz229]

Spotted 420 as well O.o

[@expansivegymnast1020]

Good video. Thanks!

[@Saltxwater]

Thanks Nick, that was really interesting and good to know about the drawbacks of the ImmutableDictionary! When writing my own internal code I will often use IReadOnlyDictionary (interface) as the return/argument type but pass through my normal (mutable) dictionary anyway. I know there's nothing stopping my code from examining the type / casting this and mutating it anyway, but since it's my code and I'm respecting the input type then it feels safe to me (Looking back on it I don't think I ever cast anything anyway)! What are your thoughts on this?

[@mastermati773]

I think that one thing wasn't specified. The 'GetElement' benchmark should be split into one-by-one (where keys are stored next to each other in the memory) and completely randomly. I believe that AVL Tree would significantly change the score due to the memory locality on CPU caches. Exactly the same reason why Unity is developing DOTS.

[@nickchapsas]

It shouldn't matter that's why I didn't do that. Because the implementation behind the scenes should be irrelevant to your choice. You care about an "Immutable Dictionary" which implies that is an immutable verison of the Dictionary which is known to be a hashtable. The only difference between the two is implied to be the immutability factor.

[@cabriolex]

SortedDictionary (missing in this video) has a nice bonus feature - it never fragments the LOH, what hashtable/Dictionary very well do on large amount of data.

[@alejandroguardiola9085]

that is very interesting, I guess because the ImmutableDictionary have to make copies of itself using an AVLTree is better with the memory because in a hash Table you have to allocate space even for the items that has not been added to the Dictionary I mean is not that much considering it is a pointer space so basically 64 bits in 64 systems for every item between the last computed hash and the new computed hash, so Immutable may be more memory efficient(I mean one instance will take less space than the equivalent instance of a dictionary)

[@user-hu4dp5io7b]

Hello, Nick! Thank you so much for such interesting videos! I want to ask you about using ContinueWith for async tasks: when I want to fill a dictionary with keys and values (counters) from different sources I use Task.WhenAll with async queries that continue with adding results to a dictionary. Is it a suitable case for ContinueWith using or can you suggest a better solution for my case? Thank you in advance! Have a nice day!

[@Deemo_codes]

Are immutable dictionaries backed by an AVL tree to store the data densely? Presumably the hashtable dictionaries have a sparse array to enable adding without collisions whereas the AVL tree shouldnt get added to? Thanks for the video!

[@nickchapsas]

I don't know if it's just about storage but also about being efficient with the Add/Update/Remove operations and memory. That being said there is a proposal to move from AVL trees to B+-trees here: github.com/dotnet/runtime/issues/14477

[@erikthysell]

Thanks for great videos... do you have any comments or measurements for SortedConcurrentDictionary?

[@fernandovictor3092]

Hi, I love your videos. Why only some videos allow translation automatically?

[@upgradeplans777]

Nick, after some quick research (and reading the comments), I think this video isn't correct. 1. I suspect that the benchmark results shown are consistent with O(1): Add runs in 0.95us then 1.143us then 1.0136us. The numbers are not good, but at the same time, if they are only a constant factor of 3 slower than the HashMap implementation, then this is not an important difference. 2. If the ImmutableDictionary uses structural sharing, then it does NOT allocate the entire dictionary for each add. The clue is in the name: both the old and new dicts share the majority of their internal structure, only allocating the differences. 3. Common dictionary implementations that utilize structural sharing are, depending on who you ask, "O(1) amortized", "O(log32 n)" or "O(log n) for n's larger than the number of atoms in the visible universe". All of these terms refer to the fact that it is theoretically O(log n), but indistinguishable from O(1) using any benchmark performed on hardware that can exist in our universe. 4. Structural sharing does require a generational garbage collector in order be efficient with memory allocations. If properly implemented and used, almost all "allocations" do not survive generation 0. And generation 0 should be implemented as a fixed allocation anyway, so that "real" allocations are not needed. I don't know the internals of dotnet garbage collection, but my quick look at the documentation does suggest some kind of generational garbage collector. But I'm not sure how much it is optimized for structural sharing datatypes.

[@nickchapsas]

Get on ImmutableDictionary is definately not O(1) in terms of speed and Add isn't either. The reason why Add makes it harder to notice is because the benchmark result is within margin of error but consistent with how you would see an O(log n) operation look over time especally in those sizes of collection. Add will not allocate the whole collection but since you will be allocating to the new object, because the function is pure, you just lost the old reference to the old immutable array which needs to be GCed now. I have not tested this last bit so I could be wrong though but in any case, Add isn't really a concern to me because I would never mutate and immutable dictionary. Get is the only operation I would ever run on it and I would do that assuming it is O(1) which it is not.

[@upgradeplans777]

@@nickchapsas Perhaps the naming convention is a bit confusing, but structural sharing was definitely invented for the purpose that you say you are not willing to use it for. (The purpose of managing changing data with immutable datatypes.) "Immutable" refers to the fact that the object does not mutate, and structural sharing is merely one technique that exists within that category. Another common name for structural sharing datatypes is "Persistent" datatypes. However, the category of persistent datatypes is also much larger and not even always immutable. I'm not a regular .NET user, so I cannot say whether this ImmutableDictionary is implemented sensibly, but I looked up its documentation, and it is meant to be a structural sharing datatype. I also cannot say whether the .NET garbage collection is any good. But again, the documentation tells me it is a generational GC. (Generational GC is the correct GC type to use with structural sharing.) As for whether it is O(1) or not: Normally these datatypes have a branching factor of 32. This means that Adds and Gets use 1 indirection for dictionaries with 1..32 entries, 2 indirections for dicts with 32..1024 entries, 3 indirections for dicts with 1024..1048576 entries, and 4 indirections for dicts with 1048576..33554432 entries. With 8 indirections, you can have 1 terra-entry. There is no computer in existence today that can reasonably store that in RAM. So yes, the algorithm very much is a O(log n) algorithm. But if your code is written to be run on actual hardware, this maximum of 8 indirections is an insignificant factor.

[@nickchapsas]

@@upgradeplans777 Here is the thing that you're mainly missing. I shouldn't know or care about any of this. It should all be abstracted from me. All I care about is having an immutable hashtable. Hashtable is obsolete so the instruction for a modern hashtable (with an average O(1) time complexity in operations) is to use Dicitonary. Then I use ConcurrentDictionary for its thread safety and the assumption of pretty much everyone who looks at the name is that when I want an immutable dictionary I go for ImmutableDictionary. The problem here is that I no longer have a Hashtable anymore. This is all there is to it.

[@upgradeplans777]

@@nickchapsas The usage of the word immutable in the name "ImmutableDictionary" is the conventional way it is used. Perhaps this is an unfortunate artifact, I don't have an opinion about that. But when I read ImmutableDictionary in this video, I did expect a structural sharing datatype with "O(1) amortized" performance, and it is my opinion that it should not use that name if it is not implementing a structural sharing datatype with O(1) amortized performance. (So, in that sense, I am saying the opposite of what you are saying when you say that the name is misleading.) A proper implementation of a structural sharing hashmap/hashtable will have "O(1) amortized" performance. Which is also the most that normal hashmaps give by the way, because they do not maintain theoretical O(1) performance when there are collisions. I will also note that a structural sharing hashmap/hashtable still is a hashmap/hashtable. It just also includes the structural sharing implementation. Which is apparently the part that is leading to this confusion. If the ImmutableDictionary is slow, then that is a performance issue with its implementation. But as I explained, the largest structure that fits in RAM will at most be 8 times as slow as an empty one. You yourself often enough point out that it isn't enough to strictly look at the theoretical performance, but to also take the real-world implications into account. I do think that, if you were to look at this type of datastructure in more detail, that you will agree that it has a sensible and modern design that can be tuned for high performance with large amounts of in-memory data. (If you don't trust this C# implementation, perhaps another immutable hashmap.) Still, it is true that most languages are not tuned for structural sharing, and therefore it can be a constant factor slower than using a mutable hashmap. I will caveat that again by saying that all of this depends on the datastructure being properly implemented with a branch factor of 32, ofcourse.

[@sergeymigel4680]

Thanks bro

[@jan5310]

Thanks for clearing up any doubts about your age at 2:20

[@fedormorozov8255]

For add operations benchmark was initial capacity set to itemCount? Was strings used? I really wonder if dictionary be free memory alloc.

[@claudiopedalino337]

Nick, do you try to implement api versioning into a minimal api?

[@DummyFace123]

Since get is the only valid usecase on immutable dictionary I think the extra time it takes is fine. I’m thinking a valid performance comparison on immutable dictionary would be time it takes to create an immutable dictionary from an existing (sizable) dictionary, compared to creating a new read only dictionary. I can only imagine these things are hydrated in one method as a dictionary and returned or passed in as an immutable

[@pqsk]

I remember when .net 1 came out. That was ages ago. But I've only worked professionally with .net 2 and above. Anyways I never heard of this immutable dictionary. Now I know that it has a very specific use case...when you need an avl tree.

[@SynthacticSugar]

I didn't see the same degradation with ImmutableDict at all. New snapshots of the dict seem to be just a few copied nodes but mostly all the same nodes in the new dict as well. It's a tree for a good reason, otherwise it would be much easier to just clone a normal dict wouldn't it? Even if making a bunch of new snapshots (on an already very large dict) and keeping them in memory there was only a slight increase in the total number of nodes when I tried mem-profiling in VS. Strange...

[@nickchapsas]

The problem is that you allocate the new dictionary and completely lose the old one since the Add method is pure so even tho the operation is not bad, since it is O(log n), the memory impact is big. That being said, mutation discussions on an immutable dictionary shouldn't be part of the discussion since the whole point is that you don't want it to be mutated, so the only thing that matters is read. And read speeds, because it is AVL, are O(log n) which is worse than O(1) and the difference is clearly observable.

[@sodiboo]

@@nickchapsas Isn't the point more to have value semantics? You can never have a shared reference to a mutable ImmutableDictionary, because any mutation returns a copy, and not the original instance, right? The tree is chosen to ensure mutation is still reasonably fast while requiring a copy (of the mutated nodes), and reading takes a hit but isn't horrible If you want an immutable dictionary with O(1) read times, you'd use ReadOnlyDictionary, and not ImmutableDictionary i think the name is kinda misleading to what a programmer expects of it (the point isn't to be immutable, it's to be mutable without allowing sharing a reference), but it accurately describes any individual instance as they are completely immutable after instantiating and you are *guaranteed* that if you store it, it will not be mutated unless you reassign the location you stored it to (whereas if you give someone a IReadOnlyDictionary it guarantees a consumer can't modify your dictionary, it will not be mutated when you pass it around, but if you receive one, it may be mutated between reads you perform)

[@nickchapsas]

@@sodiboo My whole point is that the name is misleading and it doesn't convey how the implementation details change, which in return change the performance.

[@sodiboo]

@@nickchapsas Yeah, i can agree with that. It doesn't convey the implementation details and performance disadvantages, but it does convey the guarantee it makes (ReadOnly is something you only have read access to, but Immutable also says nobody else has mutating write access). I think for a lot of cases performance isn't *that* important and the semantics are more important, but yeah, it shouldn't be *that easy* to completely miss the differences internally as it is because it does matter

[@DanteDeRuwe]

Is there any reason why ConcurrentDictionary wouldn't just be the default (and hence be just called "Dictionary") if the performance is nearly identical to that of the existing Dictionary?

[@nickchapsas]

The reason is performance. It is allocating more memory and operations take quite a bit longer (in the context of microseconds ofc) so if every little counts and thread safery isn't a concern, you would use Dictionary.

[@PrometheusMMIV]

What about SortedList? Which I always thought was a terrible and confusing name for a Dictionary class. And there's also SortedDictionary, but I'm not sure what the difference is.

[@RateTheQuad]

Immutability isn't free. Also, good luck implementing ImmutableDictionary functionality using Dictionary and IReadOnlyDictionary. I'm pretty sure you will get terrible performance.

[@petermanger9047]

Goes and updates a few local caches using Dictionary to ConcurrentDictionary....

[@efrenb5]

When I saw all those immutable classes I was so happy I started to use them everywhere. Then I found out about the implementation and got soooo sad. Now I don't use them anywhere and simply use the good IReadOnly interfaces. Done. If the caller dares to cast those instances, that's their problem. LOL

[@ricardopieper11]

Interesting that your benchmarks showsDictionary with lock faster than a ConcurrentDictionary.... I wonder why.

[@SirBenJamin_]

Do you think it would be possible to add weak events to the C# language? so instead of subscribing with the += operator, you could subscribe with some other operator that would indicate to the language you wanted a weak subscription? be interesting to hear your thoughts on this. I'm guessing that it's not possible, else they would have already added it to the language. and thats why we have to use something else, like the the WPF weak event system? or maybe its to do with efficiency?

[@tobyjacobs1310]

Believe it or not the wpf weak event system isn't intended for wpf per se... Have a look at which assemblies those classes actually live in; iirc they aren't wpf related

[@tobyjacobs1310]

To be honest, actually, Rx is a better solution. Especially since you can make observers self-disposing.

[@alexandruchirita5780]

Almost offtopic related to a small mistake related to "natively" word being used: You said that "Hashtable.Synchronized existed natively", maybe it's just a small mistake with a word "natively" chosen poorly, but I'm stating my opinion anyway: I consider everything in C# not native because of it's virtual machine running IL being later JIT-ed into native code, it is not directly working with native code but indirectly working with it because of the JIT. As a reference: "Native code provides instructions to the processor that describe what tasks to carry out.", but nothing in C# is directly using native code, but it is using IL instead, degrading performance because of the Just In Time compilation required in order to convert the IL to native code.

[@bokkeman123]

Thanks but to be honest I don't think you did the title justice - I was expecting a discussion of real world use cases and the correct choice of dictionary for each, with the tradeoffs of each choice.

[@nickchapsas]

Everything in the video can be adapted to real use cases. This is the reason why I show generic examples. Because if I show specific use cases you will think that this is the only problem. Showing a generic example allows each viewer to think how they can adapt it to their use cases

[@junaid9781]

Caption not available in your videos plz add

[@evanboltsis]

420 viewers while I was watching... Interesting random number there

[@JayBlackthorne]

How do you make it so that you can access the source of .NET libraries straight from your IDE?

[@nickchapsas]

it's a feature of my IDE, Rider

[@fr3ddyfr3sh]

What about SortedDictionary?

[@KjetilValoy]

Interesting. Earlier we had a performance problem with ConcurrentDictionary that was solved with a regular Dictionary with locks. Your benchmark data showes the same

[@intoverflow1106]

Do you know why it is like that?I always thought that ConcurrentDictionary is faster than a "lock dictionary". I like to use ConcurrentDictionaries for caching data and I have been thinking that this is the best way to do it. But in this case you should write your own dictionary class with locked or what do you think?

[@Grimlock1979]

Was it used on multiple threads? ConcurrentDictionary is tailored for usage with multiple threads. It will have more overhead than a regular dictionary on a single thread. It uses multiple locks internally so different parts can be accessed at the same time. It should be faster in a multi-threaded environment. If it's not, that would be weird indeed.

[@lost-prototype]

I would love to see code a code analyzer that's just a configurable "ban" on certain types in a project. Then you could get compile time reminders to not use certain things, accompanied by alternative suggestions. Would really help with sticking to best practices and avoiding accidentally consuming footgun types.

[@doc8527]

No, you will end up killing your own project. Please always take grain of salts on those video tutorials or blog posts. Pre-performance tuning by memorizing these kinds of language structures/features in mind, without any real experiences on large projects, could be extremely dangerous. Especially blindly listening to this video. Just take the video as an example of that language offers some cool features that I might want to use at some point. Stick to simple dictionary, quickly iterate your logic first without knowing any of others. At some point if you hit some perf issues you can update your basic dictionary easily, start to check those fancy Dicts from *official Doc* carefully, exanimate the *trade-off* because your basic structure is simple enough and has tons of flexibilities. If you are thinking too much and pre-perf tunes too much, it's hard to change. The worst case is that your pre-perf is the key perf issue and it's even faster without using any of fancy stuffs, because you has completely no idea about the trade-off behinds the languages/tools itself. All those performance checks in examples are mostly garbage because true performance issues is generally a result of combination of multiple choices/trade-off. As long as you don't write some random stupid codes cause O(n^2) that can be done by O(n), you are good to go. Real world projects sometimes can be complex that you might want to mix up different types of Dicts regardless languages/frameworks.

[@lordicemaniac]

so the hashtable is completely pointless at this this time? How is it compared to Dictionary?

[@nickchapsas]

Yeah don't use HashTable there is no point. Dictioanry is practically the same as HashTable since both keys and values will suffer from the same boxing problems

[@Grimlock1979]

HashTable is a leftover from C# 1.0. Generics were introduced in C# 2.0. Dictionary is just the generic version of HashTable. Just consider HashTable deprecated. The same goes for ArrayList. There are also non-generic versions of Queue, Stack and SortedList. Use the generic versions instead.

[@haxi52]

Dictionary has an O(n) for the add, and O(1) for the other operations.

[@nickchapsas]

No it’s not. Both add, search and delete are O(1) on average and O(n) for worst case

[@germanpaskovskij776]

@@nickchapsas well your benchmark data at 7:45 shows that: for 100 items it is 34.49us, for 1000 = 311.44us, for 10000 = 3214.10us. So looks like in reality it is still almost O(n), no?

[@wizardofboz76]

I've recently discovered the HybridDictionary

[@addyrocking86]

Hey Nick, Which extension you are using to see the built in class code file and complete structure using F12 or Go to Definition.

[@nickchapsas]

It's the same thing. Rider just does that on F12/Go to Definition.

[@DuRoehre90210]

Oh, be careful with this expectations about Big-O complexity estimations. Yes, something with O(n) complexity sounds great in theory. But this hides the actual cost of the static factors in the algorithm. I mean, what good is your great O(n) or O(n*log n) algorithm if there is some static cost for the calculation which is not expressed in the powers? Not so long time ago, I worked on an application with kinda HUGE in-memory database. Consisting of many data lookup tables, typically having quite long strings as keys. In the end, for most cases SortedDictionary was used for performance reasons. Why? Because Dictionary or HashTable always need to run a hash function on the entire string. Lots of CPU cycles every time in order to do just that, please the collision handling afterwards within the hash table storage. On the other hand, if the typical pattern for the contents of your keys indicates that they are very dispersed, then a tree-based structure (AVL or RedBlack or whatever is used by SortedDictionary ATM) can make the decision to navigate in the tree after reading only the first bytes of the string contents.

[@tomwimmenhove4652]

I wish C# supported the 'const' keyword the way C++ does. This would make all these weird "...AsReadOnly...()" methods and excess code required to make things readonly. Don't want something to be mutable outside of a class? Declare it const.

[@MsKpg]

So there is no performance benefit to using ImmutableDictionary? I did not expect that. Would using int keys instead of strings have any sort of perf difference at least?

[@nickchapsas]

No you actually lose performance. You are better of using a normal Dictionary and just agree to treat it as immutable or even better to use a ReadOnlyDictionary. Value types in general are a bit faster as keys in hashtables than reference types but it's not something you should be really thinking. Ofc this is only relevant if what you are after is a read only dictionary.

[@kylewascher2130]

@@nickchapsas Have you looked at the differences in performance with ImmutableSortedDictionary? Its implementation is different than the non-sorted version.

[@aremes]

:D i've never used ImmutableDictionary right until *yesterday*, actually when i had a use case for it and figured "it _must_ be faster, right?" Thanks! Need to revert that again

[@richardrisner921]

Wait, so I shouldn't be using Hashmap?

[@yarondavid]

The brackets operator on concurrentDictionary is actually not thread safe

[@nickchapsas]

Do you mean upon initialization?

[@masslooo2003]

please add subtitle

[@raztubes]

I have to remember to never use the dictionary type I never knew existed. Done

[@SilentTremor]

Did you thanked David Fowler for the inspiration?

[@nickchapsas]

Literally in the first 30 seconds of the video

[@sepbla178]

How did you drill down to the concurrent dictionary code?

[@jr.BoarOfGold]

5:56 Mmmmmmmm??!

[@mcdev6868]

So never use ImmutableDictionary, what would be there use case if it performs worse all the time? What about ReadOnlyDictionary? Say I pre-initialize a Dictionary that from then will never change. What might be the best option to use? I am surprised that the Get operation (dict[key]?) is so slow for it, I thought it would be faster. Or was that something else? I have to to join the Discord...

[@mathboy8188]

"420 is always a random number" heh

[@b0rkes]

You look great for your 69 😀 great stuff, didn't know about immutable dictionaries behavior

[@deandre1988]

“Hello, *mumble mumble intro*, today..”

[@nickchapsas]

Classic intro on brand

[@SuperBadGPT]

A LIKE for using RIDER :)

[@anonimxwz]

Then basically all are almost the same in performance in add, get and update, except inmmutable that sux

[@fat-freeoliveoil6553]

So really there's only two Dictionary types. Dictionary and ConcurrentDictionary. Hashtable is obsolete. Dictionary does the exact same thing. ImmutableDictionary is very niche. The chances are that you are better off either: - Using const/readonly fields/properties. - Initialise a ReadOnlyDictionary from a JSON (or similar) file.

[@AlanDarkworld]

@nick Since we're talking about collections here, can we talk about how List, Set etc. in C# do *NOT* override GetHashCode() and Equals()? I could hardly believe my eyes when I first saw that. But indeed, new List { "a" }.Equals(new List {"a"} ) ... WILL return false in C#. Just what on earth were they thinking?

[@nickchapsas]

It makes sense since they are different objects with different references.

[@AlanDarkworld]

@@nickchapsas true, they're different memory addresses. But isn't it the very purpose of Equals to determine equality based on content and semantics, rather than memory addresses? I know for a fact that the same code on the JVM will return true.

[@filiecs3]

@@AlanDarkworld no, that is a feature of higher level languages like JavaScript or python. You compare value types by value and reference types by reference/pointer. That's the way it is in C/C++. Changing the rules arbitrarily just makes it harder to understand how it's actually working under hood. Without the difference, it would be easy to have unexpected situations where two references are comparing as equal but changing a value on a reference in one location does not change it in the other. The new record class in C# has the type of behavior you are thinking of.

[@kmcdo]

69. Just a random age. Mmhmm.

[@Maric18]

never understood immutable objects. If you dont want things to change, dont change them if anything gets reused and distributed over such a large space that you cannot guarantee it, you need to modularize better in the end all you should offer are some safe objects or an api that cannot be "messed up" easily from the outside many languages have ways to "hack" immutable objects and change them anyway and at that point a mere "this property is not meant to be changed" warning is enough

[@henson2k]

So why ImmutableDictionary exists at all if it worse than normal dictionary?

[@djgiel4life]

420 was here first.

[@samuelgrahame3617]

69 random age haha

[@TheMainManNorthOfEquator]

Just use java

[@nickchapsas]

lol no

[@ether626]

More "var"... it's not js

[@Eryklok]

Sounds like you got the issue narrowed down from A-Z

[@giszTube]

I thought that the ConcurrentDictionary.AddOrUpate did not grab a lock.