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