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

<ul>
<li>hash tables</li>
<li>cache oblivious</li>
</ul>

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

<p>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? </p>

<p>The questions I'm asking are related not only on theoretical results, but also on <strong>real results</strong> on real computers.</p>

<p>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.</p>

<p>Thanks for any pointers!</p>

CC BY-SA 3.0
2016-03-05T17:16:19.930Z
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.
jbapple
CC BY-SA 3.0
2016-03-06T08:22:16.403Z
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.
senseiwa
CC BY-SA 3.0
2016-03-06T08:25:54.623Z
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 http://cs.stackexchange.com.
jbapple
CC BY-SA 3.0
2016-03-06T15:21:37.307Z
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?
senseiwa
<reference-request><ds.data-structures><cache-oblivious>
Hashtable vs cache-oblivious
senseiwa
# Hashtable vs cache-oblivious

(Asked by: username_0 on 2016-02-29)

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!

**Tags:** reference-request, ds.data-structures, cache-oblivious

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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 http://cs.stackexchange.com.  
> **username_0**: 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?  

---

## 0 answers

