Difference between BST , Hashing , Tries and map

I read some blog and tutorial on Tries , hashing, Map(stl) and BST. I am very confused in which one is better to use and where. I know that to make such difference between them开发者_如何学Go are nonsense because they are all implementation dependent. Would you please tell me more specific and please do not forgot to mention the complexity (worst , avg, and best case).

Thanks in advance...

BST is Binary Search Tree. It is used for a dictionary. BST has no limitations on structure, and thus a search/insertion/deletion is O(n) worst case.

Map [on stl] is also a dictionary, and is actually a red-black tree [on stl]. it is a special kind of BST, which has limitations on structures, because of it, worst case search/insert/delete is O(logn).

hashing hash table is a different type of dictionary, the advantage of a hash table [with good hash functions] is O(1) average time for search/delete/insert. however, the worst case is O(n), which happens if too much elements collide and/or when a rehash is needed [when Load Balance is too high, we allocate a bigger array, and rehash all the elements to is].

Tries are special for strings. all ops are O(S) where S is the string's length. it's advantage on the others [when dealing with strings] is you need to read the string anyway, so the complexity if a Map for instance, when dealing with strings, is actually O(S*n*logn).

when to use?
a Map [or any other balanced tree] should almost always be a better choice then a regular BST.
hash table is a good choice when you want average short time, but do not care that some times you will have performance loss due to rehash, and in some cases collisions may occur.
Trie is usually a good dictionary for strings.