I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, foo2... so tree balance is an issue.
I considered balancing and auto-balancing algorithms, but then I realized that the hash for a key given a good hash function should have a 50% average chance for left/right. And I already had a hash function so that meant no additional code. So I would get a balanced tree for free(edit: at no point did I want to imply a perfectly balanced tree, this is emergent behavior).
I wanted to check if my theory was correct. When I search for BSTs, hashes, and hash trees, however, no relevant information turns up.
What is the term for a binary search tree that balances itself by using a hash?
edit: I am going to accept the answer because if something doesn't have a name it just doesn't, but I tested this because some comments and asides imply that it is worse than it actually is.
I tested a sorted list of 468685 words containing both English words and "elite" password cracking words.
balanced-tree: worst(19) average(18.84) edlin-tree: worst(47) average(22.72) edlin-tree(SHA2): worst(46) average(23.25) regular BST: worst(468685) average(234342.50)
So it's not going to replace your language library algorithms but, as stated in the accepted answer, it is obviously logarithmic.
As for the hash function(Which for reference is add+xorshift as in:
), I have also tested how bad it is by comparing collisions to the expected value.
8 bits: expected : 468428.99 axs : 468429 SHA2-256 : 468429 16 bits: expected : 403200.35 axs : 403189 SHA2-256 : 403198 24 bits: expected : 6485.99 axs : 6451 SHA2-256 : 6433 31 bits: expected : 51.14 axs : 59 SHA2-256 : 47 32 bits: expected : 25.57 axs : 30 SHA2-256 : 20 33 bits: expected : 12.79 axs : 14 SHA2-256 : 11 35 bits: expected : 3.19 axs : 7 SHA2-256 : 2 36 bits: expected : 1.59 axs : 1 SHA2-256 : 2 37 bits: expected : 0.80 axs : 0 SHA2-256 : 0
So, while it appears to lag for some bitnesses, it generally follows the expected values, both for tree depth and collisions. What would a hash which is not good for your input mean? That your input generates a sequence when passed to it? That would be ridiculously unlikely statistically speaking. Worst case is O(n) but you are not going to see it.
The algorithm is not good compared to AVL or red-black, even though insertion will probably be faster generally, however it beats a linked list or betting on input for a BST any day.