What are the most useful data structures to know inside out?
data-structures
Solution
One of the data structures I use the most (beyond vectors, of course) is the Hashtable. Its about the only choise if you need to be able to search large quantities of data in O(1) time, that means the time to search does not grow as the size of the collection grows.
The catch is that the insertion and deletion times are larger than in other data strutures, and you need to have some sort of key with which to search the collection. Every element must have a key. The algorithm takes the key of each element and computes an hash code that indicates the slot in the hash table in which to search. Then depending on the implementation it either follows a list of items that fell on that bucket to find your item or it searches nearby buckets. The size of the hastable is determinant to the efficiency of the hash that is quite affected by the ammount of collisions of hash codes between keys.
Use it whenever you need a map and the expected number of elements of the map exceed about 10. Its a bit more more memory intensive than other structures since it needs lots of unused slots in the table to be efficient.
C# has a great implementation of it with `Dictionary<keytype, valuetype>` and even has a HybridDictionary that decides internally when to use a hashtable or a vector. Any good programming book describes it but you will be well served by wikipedia: http://en.wikipedia.org/wiki/Hashtable
Problem
I'm interested in finding out what people would consider the most useful data structures to know in programming. What data structure do you find yourself using all the time? Answers to this post should help new programmers interested in finding a useful data structure for their problem. Answers should probably include the data structure, information about it or a relevant link, the situation it is being used in and why it is a good choice for this problem (e.g ideal computation complexities, simplicity and understanding etc.) Each answer should be about one data structure only. Thanks for any pearls of wisdom and experience people can share.