What are the best data structure for mapping strings to values?

Question

I'm interested in an answer that explain the best in each situation.

In particular which is best for:

• few values
• lots of values
• many values with only few extensively used
• read only or nearly read only map
• write-a-lot map
• fast membership without retrieval
• memory footprint with large value
• others

Answer 1

A red-black tree would be the most natural choice.

A hash table will get you speed at the cost of memory.

You can also reach a balance between the two by creating a red-black tree of the string's hash value, as it's safe to assume the hash numbers can be compared faster than the actual strings. This would be particularly useful when the strings (and therefore the hashes) can be calculated in advance.

Answer 2

Map/Dictionary object should be used if store less then 100 values and do not store values with more then 100 signs. If you need more, you would better use database storage.

Number of Read/Write operations doesn't matter.

Answer 3

Maybe you'll find this question interesting.