I'd like to know more about real performances of data structures, in particular two families attract my interests:

  • hash tables
  • cache oblivious

My researches didn't find any "comprehensive" (let me use this adjective) book or article that describes the advantages and disadvantages of these two families.

When is a hash table more performant than a cache oblivious data structure? What are the real use cases for a hash table, when is a cache oblivious B-tree (or simply binary) preferable?

The questions I'm asking are related not only on theoretical results, but also on real results on real computers.

I've read the book "Handbook of Data Structures and Applications", but it contains only theoretical limits, and it is not sufficient to me: I need to evaluate which data structures to implement on a real system.

Thanks for any pointers!

  • 1
    $\begingroup$ I'm voting to close this question as off-topic because this site is titled "Theoretical Computer Science", while the questioner goes out of his or her way to explain that they are not interested in the theory. $\endgroup$ – jbapple Mar 5 '16 at 17:16
  • $\begingroup$ When approaching theoretical results, IMO we must always see a real world result. A $O(\log n)$ complexity may be unsuitable to certain tasks, and an $O(1)$ for others, preferring a "worse" logarithmic approach. There are data structures that achieve fantastic theoretical limits, with exponential space, for instance. I'm asking to see the comparison between theory and practical results, some guidelines, computational complexity isn't sufficient. $\endgroup$ – senseiwa Mar 6 '16 at 8:22
  • $\begingroup$ You say "we must always see a real world result." I am not arguing that your value system is wrong, I am arguing that your question may be better suited for a different stackexchange site, like maybe cs.stackexchange.com. $\endgroup$ – jbapple Mar 6 '16 at 8:25
  • $\begingroup$ I don't know, maybe. It's a tricky question: here it's theoretical asking for real results, there maybe it would be too theoretical. Should I move it to cs.se.com? $\endgroup$ – senseiwa Mar 6 '16 at 15:21