hi
which is better ( faster ) for game programming?
Go with hash tables if you don't need ordering.
edit:
The best way to find out is probably to just use each of them in your game, and see which one is better.
Theoretically, RB trees can have height that goes up to 2 * log(n), but it's still O(log(n)).
You can also look at AA trees, which are RB trees with the red nodes only on the right side (or left if you are left handed), so they have log(n) height on the left side and at most 2*log(n) height on the right side.
And also you can look into b-trees, a generalization of RB and AA trees.
Impossible to answer as the question stands. It depends on what you want. There is no single best data structure.
If you do considerably more modifications, then red-black tree will be faster. If you do more lookups, an AVL tree will be faster. But it's not like one is 100 times faster than the other.
Both have identical big-O on all operations and are more or less on the same order of speed.
A hash table, as suggested by ultramailman may very well be the best choice, too -- depending on what you are doing.
i think look-uping an item in a game is more often used than inserting or deleteing an item so with AVL trees we can get better results.
which is better ( faster ) for game programming?
A while ago, I was learning B-trees and implemented my own. Then I made a very simple performance test that involves inserting many random integers into a data structure, do many look ups, and then removing all items, and timed it to see which one was faster. The input is the same for every data structure, so I could test them more fairly. The results were something like this (I don't have the files any more so I can't check):
RB tree: 19-20 seconds
B-tree with 16 slots per node: 5-6 seconds
hash table with separate chaining and size == number of inputs: 2 seconds
These only apply to my own implementations however, but I still trusted enough to not bother with trees when I don't need them. If I had to guess why the results turned out like that, it was probably because RB had more cache misses than B-tree, and trees had require more exploring to find the target.
are you know any good article from implementing hash tables?
as i considred, hash function is most important thing in hash table, how can i implement a good hash function for unicode strings ( a good algortim or ... )
"Implementing hash tables" is, again, something you can write entire books about, and not something that you "get right" easily (it's easy to get something that works, though). You either need to define very exactly what you need first, or you should simply use whatever implementation the standard library offers to you. For the general case, that's probably as good as you can get.
Generally, a good hash function is better than a bad hash function, but in practice a good hash table (such as e.g. the one used in GCC's unordered_map) proves widely immune to bad input, surprising as it is. It is very hard to feed GCC's std::unordered_map with something that causes 2x slower lookup times (quite different story on at least one other popular compiler!).
Creating a bad hash function is easy, creating a good hash function is hard. Creating a hash function that looks good is easy. Usually std::hash works just fine, if that isn't applicable, simple good old DJB2 works wonders. There are much "better" functions, but in my experience they are only better in theory (or by their statistical properties), not in practice, when it comes to looking up values in a hash table fast.
Hash functions have several things to consider and what's best depends a lot on what you need:
If any or all of these causes a "Uh... I dunno..." inside your head, you're probably best with using the implementation offered by the standard library. It is maybe not perfect for every case, but it works and it works well for most cases.