Virtual hashing?

Question

Algorithms

Please help me figure out the virtual hashing algorithm. Unfortunately, no matter how much I googled clear information on this topic, I could not find it. In Russian, nothing could be found at all. There is a document in English, but with the help of a translator, I could not catch the meaning of it. Please help me figure it out or give an algorithm in Russian.
I am also looking for an implementation of this algorithm in C / C ++.

Answer 1

English is easy. Even too simple (which is not surprising, given that it was written by the French) - and as a result of this simplification, essential details were hidden or lost.
The general idea is clear: we calculate the number of the basket when hashing as K=C%N (where C is the value of the hash key), and when the basket overflows, we increase N by 2 times for it, and transfer some of the elements (for which C%(2* N)!=K) to the basket with the number K+N. At the basket, we somehow remember the actual value for it N=N0*2^j (more precisely, we remember j).
The devils, as usual, hide in the details, and I did not understand these details at the first reading:
- more than one item can be stored in the basket before overflow. Where are they stored? Is there a place reserved for them right away, or is there somewhere to store the list?
- What do they do when N increases? Really double the size of all table? Or do they somehow make space only for new baskets - the descendants of overflowing ones?
I don't know what your goal is, but at this moment I would come up with some scheme that solves these issues (probably represent the baskets as a binary tree, where the left-right paths are determined by bits in the sequence of residuals C% (N * 2 ^j)), without trying to understand the article further. But if you need to understand exactly this algorithm, you will have to read it.
By the way, what year is the article? According to the general impression (and according to the dates of the cited works), this is somewhere around 1979-1985. Don't forget that back then "640 KB was enough for everyone"!

Answer 2

Read about hash tables in Russian. When you understand what is at stake, it will be easier to translate.

Answer 3

Great way to figure it out - goo.gl/2q3nyK

Answer 4

I highly doubt that you will be able to find any information on this hashing method in Russian.
As far as I understand, this is a variant of dynamic hashing with recalculation of hashes when a collision occurs. Exactly how - it is necessary to read and understand. And just try to read using a dictionary. It's not that hard in terms of language.