| FazBrowse Wikipedia Viewer | Main Page | | |
| Viewing: https://en.wikipedia.org/wiki/Hash_function#Trivial_hash_function |
Hash functions are used in conjunction with hash tables to store and retrieve data items or data records. The hash function translates the key associated with each datum or record into a hash code, which is used to index the hash table. When an item is to be added to the table, the hash code may index an empty slot (also called a bucket), in which case the item is added to the table there. If the hash code indexes a full slot, then some kind of collision resolution is required: the new item may be omitted (not added to the table), or replace the old item, or be added to the table in some other location by a specified procedure. That procedure depends on the structure of the hash table. In chained hashing, each slot is the head of a linked list or chain, and items that collide at the slot are added to the chain. Chains may be kept in random order and searched linearly, or in serial order, or as a self-ordering list by frequency to speed up access. In open address hashing, the table is probed starting from the occupied slot in a specified manner, usually by linear probing, quadratic probing, or double hashing until an open slot is located or the entire table is probed (overflow). Searching for the item follows the same procedure until the item is located, an open slot is found, or the entire table has been searched (item not in table).
Hash functions are also used to build caches for large data sets stored in slow media. A cache is generally simpler than a hashed search table, since any collision can be resolved by discarding or writing back the older of the two colliding items.
Hash functions are an essential ingredient of the Bloom filter, a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.
A special case of hashing is known as geometric hashing or the grid method. In these applications, the set of all inputs is some sort of metric space, and the hashing function can be interpreted as a partition of that space into a grid of cells. The table is often an array with two or more indices (called a grid file, grid index, bucket grid, and similar names), and the hash function returns an index tuple. This principle is widely used in computer graphics, computational geometry, and many other disciplines, to solve many proximity problems in the plane or in three-dimensional space, such as finding closest pairs in a set of points, similar shapes in a list of shapes, similar images in an image database, and so on.
Hash tables are also used to implement associative arrays and dynamic sets.
where bj is the number of items in bucket n be significantly less than ''b''</sup>"}},"i":0}}]}'>2. Consider a pseudorandom number generator function [0, n − 1] is ''b''</sup>"}},"i":0}}]}'>n P(key) / 2. We can replace the division by a (possibly faster) right bit shift: > ''b''"}},"i":0}}]}'>n P(key) >> b.
If keys are being hashed repeatedly, and the hash function is costly, then computing time can be saved by precomputing the hash codes and storing them with the keys. Matching hash codes almost certainly means that the keys are identical. This technique is used for the transposition table in game-playing programs, which stores a 64-bit hashed representation of the board position.
A hash function is applicable in a variety of situations. Particularly within cryptography, notable applications include:
A hash procedure must be deterministic—for a given input value, it must always generate the same hash value. In other words, it must be a function of the data to be hashed, in the mathematical sense of the term. This requirement excludes hash functions that depend on external variable parameters, such as pseudo-random number generators or the time of day. It also excludes functions that depend on the memory address of the object being hashed, because the address may change during execution (as may happen on systems that use certain methods of garbage collection), although sometimes rehashing of the item is possible.
The determinism is in the context of the reuse of the function. For example, Python adds the feature that hash functions make use of a randomized seed that is generated once when the Python process starts in addition to the input to be hashed. The Python hash (SipHash) is still a valid hash function when used within a single run, but if the values are persisted (for example, written to disk), they can no longer be treated as valid hash values, since in the next run the random value might differ.
It is often desirable that the output of a hash function have fixed size (but see below). If, for example, the output is constrained to 32-bit integer values, then the hash values can be used to index into an array. Such hashing is commonly used to accelerate data searches. Producing fixed-length output from variable-length input can be accomplished by breaking the input data into chunks of specific size. Hash functions used for data searches use some arithmetic expression that iteratively processes chunks of the input (such as the characters in a string) to produce the hash value.
In many applications, the range of hash values may be different for each run of the program or may change along the same run (for instance, when a hash table needs to be expanded). In those situations, one needs a hash function which takes two parameters—the input data 0 to 32</sup> − 1"}},"i":0}}]}'>2 − 1), divide the result by 2, this can be done by bit masking and bit shifting. When this approach is used, the hash function must be chosen so that the result has fairly uniform distribution between n that may occur in the application. Depending on the function, the remainder may be uniform only for certain values of z is the key being hashed and H(z,n + 1) = H(z,n) with probability close to n to compute the value of 1114112 entries.
The same technique can be used to map two-letter country codes like "us" or "za" to country names (26 = 676 table entries), 5-digit ZIP codes like 13083 to city names (2.
A mid-squares hash code is produced by squaring the input and extracting an appropriate number of middle digits or bits. For example, if the input is 15241578750190521, so the hash code is taken as the middle 4 digits of the 17-digit number (ignoring the high digit) 8750. The mid-squares method produces a reasonable hash code if there is not a lot of leading or trailing zeros in the key. This is a variant of multiplicative hashing, but not as good because an arbitrary key is not a good multiplier.
A standard technique is to use a modulo function on the key, by selecting a divisor {0, M − 1}. This gives good results over a large number of key sets. A significant drawback of division hashing is that division requires multiple cycles on most modern architectures (including x86) and can be 10 times slower than multiplication. A second drawback is that it will not break up clustered keys. For example, the keys 123000, 456000, 789000, etc. modulo 1000 all map to the same address. This technique works well in practice because many key sets are sufficiently random already, and the probability that a key set will be cyclical by a large prime number is small.
Algebraic coding is a variant of the division method of hashing which uses division by a polynomial modulo 2 instead of an integer to map M = 2, and we postulate an Z(x) = x + ζm−1x + ⋯ + ζ0. A key ''n''−1</sub>…''k''<sub>1</sub>''k''<sub>0</sub>)<sub>2</sub>"}},"i":0}}]}'>K = (kn−1…k1k0)2 can be regarded as the polynomial ''m''−1</sub>''x''<sup>''m''−1</sup> + ⋯ ''h''<sub>1</sub>''x'' + ''h''<sub>0</sub>"}},"i":0}}]}">K(x) mod Z(x) = hm−1x + ⋯ h1x + h0. Then Z(x) is constructed to have Z is a function of n (the last of which is a divisor of ''k''</sup> − 1"}},"i":0}}]}'>2 − 1) and is constructed from the finite field ''k''</sup>)"}},"i":0}}]}'>GF(2). Knuth gives an example: taking Z(x) = x + x + x + x + x + x + 1. The derivation is as follows:
Let (2j mod n) ∈ S ∀j ∈ S.
Define P(x)
are computed in this field. Then the degree of P(x) whenever ''j''</sup>"}},"i":0}}]}'>α is a root, it follows that the coefficients i</sup>''"}},"i":0}}]}'>p of ''n''−1</sub>''x''<sup>''n''−1</sup> + ⋯ + ''r''<sub>1</sub>''x'' + ''r''<sub>0</sub>"}},"i":0}}]}">R(x) = rn−1x + ⋯ + r1x + r0 is any nonzero polynomial modulo 2 with at most P(x) modulo 2. If follows that the corresponding hash function will map keys with fewer than t will get large, or both, for the scheme to be computationally feasible. Therefore, it is more suited to hardware or microcode implementation.Unique permutation hashing has a guaranteed best worst-case insertion time.
Standard multiplicative hashing uses the formula {0, …, M − 1}. The value and its binary representation a random mixM = 2 are powers of 2 and ha(K) = ⌊(aK mod 2) / 2⌋. This is special because arithmetic modulo ''w''</sup>"}},"i":0}}]}'>2 is done by default in low-level programming languages and integer division by a power of 2 is simply a right-shift, so, in C, for example, this function becomes
and for fixed unsignedhash(unsignedK){ K^=K>>(w-m); return(a*K)>>(w-m); }
Fibonacci hashing is a form of multiplicative hashing in which the multiplier is ''w''</sup> / ϕ"}},"i":0}}]}'>2 / ϕ, where 4050310
The multiplier should be odd, so the least significant bit of the output is invertible modulo ''w''</sup>"}},"i":0}}]}'>2. The last two values given above are rounded (up and down, respectively) by more than 1/2 of a least-significant bit to achieve this.
Simplistic hash functions may add the first and last
Modern microprocessors will allow for much faster processing if 8-bit character strings are not hashed by processing one character at a time, but by interpreting the string as an array of 32-bit or 64-bit integers and hashing/accumulating these "wide word" integer values by means of arithmetic operations (e.g. multiplication by constant and bit-shifting). The final word, which may have unoccupied byte positions, is filled with zeros or a specified randomizing value before being folded into the hash. The accumulated hash code is reduced by a final modulo or other operation to yield an index into the table.
Analogous to the way an ASCII or EBCDIC character string representing a decimal number is converted to a numeric quantity for computing, a variable-length string can be converted as a > 1 that takes the components 0</sub>,''x''<sub>1</sub>,...,''x''<sub>''k''−1</sub>)"}},"i":0}}]}'>(x0,x1,...,xk−1) as the characters of the input string of length 10, or 19 decimal digits with radix 10.
While Knuth worries about adversarial attack on real time systems, Gonnet has shown that the probability of such a case is "ridiculously small". His representation was that the probability of α / (e k!), where "hash digest". Computer Security Resource Center - Glossary. NIST.
| View original on Wikipedia | Back | FazBrowse Home |