Classical Applied Data Structure
Double hashing with open addressing is a classical data structure on a table . Let be the number of elements stored in then 's load factor is .
Double hashing approximates uniform open address hashing. That is, start by randomly, uniformly and independently selecting two universal hash functions and to build a double hashing table .
All elements are put in by double hashing using and . Given a key, determining the -st hash location is computed by:
Let have fixed load factor . Bradford and Katehakis showed the expected number of probes for an unsuccessful search in, still using these initially chosen hash functions, is regardless of the distribution of the inputs.
Previous results include: Guibas and Szemerédi showed holds for unsuccessful search for load factors . Also, Lueker and Molodowitch showed this held assuming ideal randomized functions. Schmidt and Siegel showed this with more realistic -wise independent and uniform functions (for, and suitable constant ).
Like linear probing, it uses one hash value as a starting point and then repeatedly steps forward an interval until the desired value is located, an empty location is reached, or the entire table has been searched; but this interval is decided using a second, independent hash function (hence the name double hashing). Unlike linear probing and quadratic probing, the interval depends on the data, so that even values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering. In other words, given independent hash functions and, the jth location in the bucket sequence for value k in a hash table is:
Read more about this topic: Double Hashing
Famous quotes containing the words classical, applied, data and/or structure:
“Et in Arcadia ego.
[I too am in Arcadia.]”
—Anonymous, Anonymous.
Tomb inscription, appearing in classical paintings by Guercino and Poussin, among others. The words probably mean that even the most ideal earthly lives are mortal. Arcadia, a mountainous region in the central Peloponnese, Greece, was the rustic abode of Pan, depicted in literature and art as a land of innocence and ease, and was the title of Sir Philip Sidney’s pastoral romance (1590)
“Those who dare to interpret God’s will must never claim Him as an asset for one nation or group rather than another. War springs from the love and loyalty which should be offered to God being applied to some God substitute, one of the most dangerous being nationalism.”
—Robert Runcie (b. 1921)
“Mental health data from the 1950’s on middle-aged women showed them to be a particularly distressed group, vulnerable to depression and feelings of uselessness. This isn’t surprising. If society tells you that your main role is to be attractive to men and you are getting crow’s feet, and to be a mother to children and yours are leaving home, no wonder you are distressed.”
—Grace Baruch (20th century)
“There is no such thing as a language, not if a language is anything like what many philosophers and linguists have supposed. There is therefore no such thing to be learned, mastered, or born with. We must give up the idea of a clearly defined shared structure which language-users acquire and then apply to cases.”
—Donald Davidson (b. 1917)