0

Relating to this: stack overflow question,

where I found out that .Net dictionaries resize to the next prime size that is at least twice the current size, I was wondering if there is any balanced tree-like data structure that can resize to prime sizes (similar to B-Trees or Binomial trees maybe).

What is the tree-like data structure behind .Net's dictionaries?

Thanks.

Community
  • 1
  • 1
costy.petrisor
  • 783
  • 7
  • 17

2 Answers2

2

The Dictionary uses a hash table algorithm, which stores the data in an array, it is this array that is sized/re-sized based on Prime numbers.

.NET SortedDictionary uses a Red-Black tree structure to maintain the Key/Value pairs. Since the red-black tree is not stored in a fixed array, but rather as a series on nodes with left/right child nodes, there is not really a concept of sizing anything, as nodes are added to the tree the tree is rotated to maintain the balance.

Chris Taylor
  • 52,623
  • 10
  • 78
  • 89
  • `Dictionary` != `SortedDictionary`. And I doubt `SortedDictionary` resizes to primes. – moinudin Jan 09 '11 at 12:52
  • @marcog, I do not believe I said either of those things? I say Dictionary uses Hashtable, Sorted dictionary uses Red-Black tree and that the tree is **not** stored in an array and there is **not** a concept of sizing anything. – Chris Taylor Jan 09 '11 at 12:54
  • well it is wise to not allocate memory for nodes that you do not use ... that's true – costy.petrisor Jan 09 '11 at 12:55
  • Not now that you edited your answer. Please don't hide behind edits. – moinudin Jan 09 '11 at 12:56
  • @marcog, I assure you that I am not that childish, I only editied the answer to add info on the hash table and the links. I believe you miss-read the initial answer. – Chris Taylor Jan 09 '11 at 12:59
2

.Net's dictionaries are implemented as hastables, which is not a tree-like data structure at all. The question you link to explains why hashtables are better resized to a prime number.

As for tree-like structures, I can't imagine a purpose for resizing to a prime. It doesn't make much sense. What does make sense though, is resizing a balanced tree structure to a complete tree, which for a binary tree would be 2n-1.

Community
  • 1
  • 1
moinudin
  • 134,091
  • 45
  • 190
  • 216
  • because you can eventually have to resize to huge numbers and keeping extra nodes is memory unefficent while keeping a tree unballanced can give non-linear search times, or even worse – costy.petrisor Jan 09 '11 at 12:50
  • and so is C++'s std::map implemented as a hastabled, but kept in a red-black tree for fast searching, adding and removall purposes – costy.petrisor Jan 09 '11 at 12:51
  • @costy It might make sense to resize, but there's no advantage of picking a prime size. `std::map` is implemented as a red-black tree, not a hashtable. – moinudin Jan 09 '11 at 12:53
  • @marcog, std::map is most typically implemented as a red-black tree and not an AVL tree. – Chris Taylor Jan 09 '11 at 12:55
  • there was this L9 lecture I saw online where a guy that worked for maintaining the STL for VS2010 said the std::map is implemented with a red-black tree, he also said about another compiler that used red-black trees for std::map but I forgot which one – costy.petrisor Jan 09 '11 at 12:56
  • @Chris @costy Okay, small mistake. Point was there's no hashtable. – moinudin Jan 09 '11 at 12:57
  • anyway the bottom line is that there is no need to allocate memory for nodes that you do not use, for for indexing a hashtable any balanced data structure (AVL, red-black, B-trees) will do fine – costy.petrisor Jan 09 '11 at 12:58