In practice, what is the best choice: hash table, base tree, red ebony or ...?

Question

Have you done the experience with these structures mentioned above? If insertion and search are important, then what is best in practice?

If the hash table has many collisions, you will get a list of the bucket you need to go through, so you may end up in O (n) if performance matters. So far I have not done any experience with the radix tree, and I know that red ebony is superior to the AVL tree in terms of searches.

What is your experience?

thanks Dan

Answer 1

, - , -, .

, - , , .

. Python -/, . ++ 03 set map, unordered_set unordered_map, . /, , , , -, () , () -. , -, , , - .

, , . , - . , , , .

Radix , . , URL- -, - " " "" http:// https://, , , , , "" . , , "" , , .

Answer 2

, . . .

, , - O (1) / . , , (, ). , -, .

, (Red-black AVL) O (log n), , , ( , min, max, k- , , , ..), , -. , . - AVL- , O (log n) .

, , ( AKA Fenwick) Radix, . , ( CLRS) , , , , , , , .

, , , . , , .

Answer 3

, : " ". . - , , . . x y, . , a la a BK-. ... , ?

, , . , , , ..

Answer 4

R-B AVL /. AVL , , , / . , , , , , .

-. , - . . , - - . , , , (, , - , , ).

, . , . , , . (, ), , . OTOH, , , .

Answer 5

I did quite a few experiments this year, and to my surprise, it was very difficult to defeat 234 trees (AVL trees are essentially 23 trees). Each data structure had its own sweet spot, but before you surpassed these 234 trees, you had to have quite a lot of data in your collection. And the implementation of these 234 trees was non-destructive, for download.

However, for large amounts of data, use a hash table.