{"history":[],"article":{"id":"580a8aaa-4caa-4cef-8c0e-4565a57b57a4","title":"Universal hashing","slug":"universal-hashing","content":":::summary\n:::\n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics) and [computing](https://bliptext.com/articles/computing), **universal hashing** (in a [randomized algorithm](https://bliptext.com/articles/randomized-algorithm) or data structure) refers to selecting a [hash function](https://bliptext.com/articles/hash-function) at random from a family of [hash function](https://bliptext.com/articles/hash-function)s with a certain mathematical property (see definition below).\nThis guarantees a low number of collisions in [expectation](https://bliptext.com/articles/expected-value), even if the data is chosen by an adversary.\nMany universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient.\nUniversal hashing has numerous uses in computer science, for example in implementations of [hash tables](https://bliptext.com/articles/hash-table), [randomized algorithms](https://bliptext.com/articles/randomized-algorithm), and [cryptography](https://bliptext.com/articles/cryptography).\n\n# Introduction\nAssume we want to map keys from some universe U into m bins (labelled ).\nThe algorithm will have to handle some data set of |S|=n keys, which is not known in advance.\nUsually, the goal of hashing is to obtain a low number of collisions (keys from S that land in the same bin).\nA deterministic hash function cannot offer any guarantee in an adversarial setting if, since the adversary may choose S to be precisely the [preimage](https://bliptext.com/articles/image-mathematics) of a bin.\nThis means that all data keys land in the same bin, making hashing useless.\nFurthermore, a deterministic hash function does not allow for rehashing: sometimes the input data turns out to be bad for the hash function (e.g. there are too many collisions), so one would like to change the hash function.\nThe solution to these problems is to pick a function randomly from a family of hash functions.\nA family of functions is called a **universal family** if,.\nIn other words, any two different keys of the universe collide with probability at most 1/m when the hash function h is drawn uniformly at random from H. This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key.\nSometimes, the definition is relaxed by a constant factor, only requiring collision probability O(1/m) rather than \\leq 1/m.\nThis concept was introduced by Carter and Wegman in 1977, and has found numerous applications in computer science (see, for example ).\nIf we have an upper bound of \\epsilon<1 on the collision probability, we say that we have \\epsilon-almost universality.\nSo for example, a universal family has 1/m-almost universality.\nMany, but not all, universal families have the following stronger **uniform difference property**:\nNote that the definition of universality is only concerned with whether h(x)-h(y)=0, which counts collisions.\nThe uniform difference property is stronger.\n(Similarly, a universal family can be XOR universal if, the value is uniformly distributed in [m] where \\oplus is the bitwise exclusive or operation. This is only possible if m is a power of two.)\nAn even stronger condition is [pairwise independence](https://bliptext.com/articles/pairwise-independent): we have this property when we have the probability that x,y will hash to any pair of hash values z_1, z_2 is as if they were perfectly random:.\nPairwise independence is sometimes called strong universality.\nAnother property is uniformity.\nWe say that a family is uniform if all hash values are equally likely: for any hash value z. Universality does not imply uniformity.\nHowever, strong universality does imply uniformity.\nGiven a family with the uniform distance property, one can produce a pairwise independent or strongly universal hash family by adding a uniformly distributed random constant with values in [m] to the hash functions.\n(Similarly, if m is a power of two, we can achieve pairwise independence from an XOR universal hash family by doing an exclusive or with a uniformly distributed random constant.) Since a shift by a constant is sometimes irrelevant in applications (e.g. hash tables), a careful distinction between the uniform distance property and pairwise independent is sometimes not made.\nFor some applications (such as hash tables), it is important for the least significant bits of the hash values to be also universal.\nWhen a family is strongly universal, this is guaranteed: if H is a strongly universal family with m=2^L, then the family made of the functions for all h \\in H is also strongly universal for L'\\leq L. Unfortunately, the same is not true of (merely) universal families.\nFor example, the family made of the identity function h(x)=x is clearly universal, but the family made of the function fails to be universal.\n[UMAC](https://bliptext.com/articles/umac-cryptography) and [Poly1305-AES](https://bliptext.com/articles/poly1305-aes) and several other [message authentication code](https://bliptext.com/articles/message-authentication-code) algorithms are based on universal hashing.\nIn such applications, the software chooses a new hash function for every message, based on a unique nonce for that message.\nSeveral hash table implementations are based on universal hashing.\nIn such applications, typically the software chooses a new hash function only after it notices that \"too many\" keys have collided; until then, the same hash function continues to be used over and over.\n(Some collision resolution schemes, such as [dynamic perfect hashing](https://bliptext.com/articles/dynamic-perfect-hashing), pick a new hash function every time there is a collision. Other collision resolution schemes, such as [cuckoo hashing](https://bliptext.com/articles/cuckoo-hashing) and [2-choice hashing](https://bliptext.com/articles/2-choice-hashing), allow a number of collisions before picking a new hash function).\nA survey of fastest known universal and strongly universal hash functions for integers, vectors, and\nstrings is found in.\n\n# Mathematical guarantees\nFor any fixed set S of n keys, using a universal family guarantees the following properties.\nAs the above guarantees hold for any fixed set S, they hold if the data set is chosen by an adversary.\nHowever, the adversary has to make this choice before (or independent of) the algorithm's random choice of a hash function.\nIf the adversary can observe the random choice of the algorithm, randomness serves no purpose, and the situation is the same as deterministic hashing.\nThe second and third guarantee are typically used in conjunction with [rehashing](https://bliptext.com/articles/double-hashing).\nFor instance, a randomized algorithm may be prepared to handle some O(n) number of collisions.\nIf it observes too many collisions, it chooses another random h from the family and repeats.\nUniversality guarantees that the number of repetitions is a [geometric random variable](https://bliptext.com/articles/geometric-distribution).\n\n# Constructions\nSince any computer data can be represented as one or more machine words, one generally needs hash functions for three types of domains: machine words (\"integers\"); fixed-length vectors of machine words; and variable-length vectors (\"strings\").\n\n## Hashing integers\nThis section refers to the case of hashing integers that fit in machines words; thus, operations like multiplication, addition, division, etc. are cheap machine-level instructions.\nLet the universe to be hashed be.\nThe original proposal of Carter and Wegman was to pick a prime p \\ge |U| and define\nwhere a,b are randomly chosen integers modulo p with a \\neq 0.\n(This is a single iteration of a [linear congruential generator](https://bliptext.com/articles/linear-congruential-generator).)\nTo see that is a universal family, note that h(x) = h(y) only holds when\nfor some integer i between 0 and (p-1)/m.\nSince p \\ge |U|, if x \\neq y their difference x-y is nonzero and has an inverse modulo p. Solving for a yields\nThere are p-1 possible choices for a (since a=0 is excluded) and, varying i in the allowed range, possible non-zero values for the right hand side.\nThus the collision probability is\nAnother way to see H is a universal family is via the notion of [statistical distance](https://bliptext.com/articles/statistical-distance).\nWrite the difference h(x) - h(y) as\nSince x - y is nonzero and a is uniformly distributed in, it follows that a(x-y) modulo p is also uniformly distributed in.\nThe distribution of is thus almost uniform, up to a difference in probability of \\pm 1/p between the samples.\nAs a result, the statistical distance to a uniform family is O(m/p), which becomes negligible when p \\gg m.\nThe family of simpler hash functions\nis only approximately universal: for all x\\neq y. Moreover, this analysis is nearly tight; Carter and Wegman show that whenever.\n\n### Avoiding modular arithmetic\nThe state of the art for hashing integers is the **multiply-shift** scheme described by Dietzfelbinger et al. in 1997.\nBy avoiding modular arithmetic, this method is much easier to implement and also runs significantly faster in practice (usually by at least a factor of four ).\nThe scheme assumes the number of bins is a power of two, m=2^M.\nLet w be the number of bits in a machine word.\nThen the hash functions are parametrised over odd positive integers a < 2^w (that fit in a word of w bits).\nTo evaluate h_{a}(x), multiply x by a modulo 2^w and then keep the high order M bits as the hash code.\nIn mathematical notation, this is\nThis scheme does not satisfy the uniform difference property and is only 2/m-almost-universal; for any x\\neq y,.\nTo understand the behavior of the hash function,\nnotice that, if and ay\\bmod 2^w have the same highest-order 'M' bits, then has either all 1's or all 0's as its highest order M bits (depending on whether or is larger).\nAssume that the least significant set bit of x-y appears on position w-c.\nSince a is a random odd integer and odd integers have inverses in the [ring](https://bliptext.com/articles/ring-mathematics) Z_{2^w}, it follows that will be uniformly distributed among w-bit integers with the least significant set bit on position w-c.\nThe probability that these bits are all 0's or all 1's is therefore at most 2/2^M=2/m.\nOn the other hand, if c < M, then higher-order M bits of contain both 0's and 1's, so it is certain that.\nFinally, if c=M then bit w-M of is 1 and if and only if bits are also 1, which happens with probability.\nThis analysis is tight, as can be shown with the example x=2^{w-M-2} and y=3x.\nTo obtain a truly 'universal' hash function, one can use the multiply-add-shift scheme that picks higher-order bits\nwhere a is a random positive integer with a < 2^{2w} and b is a random non-negative integer with b < 2^{2w}.\nThis requires doing arithmetic on 2w-bit unsigned integers.\nThis version of multiply-shift is due to Dietzfelbinger, and was later analyzed more precisely by Woelfel.\n\n## Hashing vectors\nThis section is concerned with hashing a fixed-length vector of machine words.\nInterpret the input as a vector of k machine words (integers of w bits each).\nIf H is a universal family with the uniform difference property, the following family (dating back to Carter and Wegman ) also has the uniform difference property (and hence is universal):\nIf m is a power of two, one may replace summation by exclusive or.\nIn practice, if double-precision arithmetic is available, this is instantiated with the multiply-shift hash family of hash functions.\nInitialize the hash function with a vector of random **odd** integers on 2w bits each.\nThen if the number of bins is m=2^M for M\\le w:\nIt is possible to halve the number of multiplications, which roughly translates to a two-fold speed-up in practice.\nInitialize the hash function with a vector of random **odd** integers on 2w bits each.\nThe following hash family is universal:\nIf double-precision operations are not available, one can interpret the input as a vector of half-words (w/2-bit integers).\nThe algorithm will then use multiplications, where k was the number of half-words in the vector.\nThus, the algorithm runs at a \"rate\" of one multiplication per word of input.\nThe same scheme can also be used for hashing integers, by interpreting their bits as vectors of bytes.\nIn this variant, the vector technique is known as [tabulation hashing](https://bliptext.com/articles/tabulation-hashing) and it provides a practical alternative to multiplication-based universal hashing schemes.\nStrong universality at high speed is also possible.\nInitialize the hash function with a vector of random integers on 2w bits.\nCompute\nThe result is strongly universal on w bits.\nExperimentally, it was found to run at 0.2 CPU cycle per byte on recent Intel processors for w = 32.\n\n## Hashing strings\nThis refers to hashing a variable-sized vector of machine words.\nIf the length of the string can be bounded by a small number, it is best to use the vector solution from above (conceptually padding the vector with zeros up to the upper bound).\nThe space required is the maximal length of the string, but the time to evaluate h(s) is just the length of s. As long as zeroes are forbidden in the string, the zero-padding can be ignored when evaluating the hash function without affecting universality.\nNote that if zeroes are allowed in the string, then it might be best to append a fictitious non-zero (e.g., 1) character to all strings prior to padding: this will ensure that universality is not affected.\nNow assume we want to hash, where a good bound on \\ell is not known a priori.\nA universal family proposed by treats the string x as the coefficients of a polynomial modulo a large prime.\nIf x_i \\in [u], let be a prime and define:\nUsing properties of modular arithmetic, above can be computed without producing large numbers for large strings as follows:\nThis [Rabin-Karp rolling hash](https://bliptext.com/articles/rolling-hash) is based on a [linear congruential generator](https://bliptext.com/articles/linear-congruential-generator).\nAbove algorithm is also known as Multiplicative hash function.\nIn practice, the mod operator and the parameter p can be avoided altogether by simply allowing integer to overflow because it is equivalent to mod (Max-Int-Value + 1) in many programming languages.\nBelow table shows values chosen to initialize h and a for some of the popular implementations.\nConsider two strings and let \\ell be length of the longer one; for the analysis, the shorter string is conceptually padded with zeros up to length \\ell.\nA collision before applying implies that a is a root of the polynomial with coefficients.\nThis polynomial has at most \\ell roots modulo p, so the collision probability is at most \\ell/p.\nThe probability of collision through the random brings the total collision probability to.\nThus, if the prime p is sufficiently large compared to the length of strings hashed, the family is very close to universal (in [statistical distance](https://bliptext.com/articles/statistical-distance)).\nOther universal families of hash functions used to hash unknown-length strings to fixed-length hash values include the [Rabin fingerprint](https://bliptext.com/articles/rabin-fingerprint) and the [Buzhash](https://bliptext.com/articles/buzhash).\n\n### Avoiding modular arithmetic\nTo mitigate the computational penalty of modular arithmetic, three tricks are used in practice:","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T07:09:10.303Z","updated_at":"2025-01-26T07:09:10.303Z","search_vector":"'hash':2 'univers':1","search_content":" \n \n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics) and [computing](https://bliptext.com/articles/computing), **universal hashing** (in a [randomized algorithm](https://bliptext.com/articles/randomized-algorithm) or data structure) refers to selecting a [hash function](https://bliptext.com/articles/hash-function) at random from a family of [hash function](https://bliptext.com/articles/hash-function)s with a certain mathematical property (see definition below).\nThis guarantees a low number of collisions in [expectation](https://bliptext.com/articles/expected-value), even if the data is chosen by an adversary.\nMany universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient.\nUniversal hashing has numerous uses in computer science, for example in implementations of [hash tables](https://bliptext.com/articles/hash-table), [randomized algorithms](https://bliptext.com/articles/randomized-algorithm), and [cryptography](https://bliptext.com/articles/cryptography).\n\n# Introduction\nAssume we want to map keys from some universe U into m bins (labelled ).\nThe algorithm will have to handle some data set of |S|=n keys, which is not known in advance.\nUsually, the goal of hashing is to obtain a low number of collisions (keys from S that land in the same bin).\nA deterministic hash function cannot offer any guarantee in an adversarial setting if, since the adversary may choose S to be precisely the [preimage](https://bliptext.com/articles/image-mathematics) of a bin.\nThis means that all data keys land in the same bin, making hashing useless.\nFurthermore, a deterministic hash function does not allow for rehashing: sometimes the input data turns out to be bad for the hash function (e.g. there are too many collisions), so one would like to change the hash function.\nThe solution to these problems is to pick a function randomly from a family of hash functions.\nA family of functions is called a **universal family** if,.\nIn other words, any two different keys of the universe collide with probability at most 1/m when the hash function h is drawn uniformly at random from H. This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key.\nSometimes, the definition is relaxed by a constant factor, only requiring collision probability O(1/m) rather than \\leq 1/m.\nThis concept was introduced by Carter and Wegman in 1977, and has found numerous applications in computer science (see, for example ).\nIf we have an upper bound of \\epsilon<1 on the collision probability, we say that we have \\epsilon-almost universality.\nSo for example, a universal family has 1/m-almost universality.\nMany, but not all, universal families have the following stronger **uniform difference property**:\nNote that the definition of universality is only concerned with whether h(x)-h(y)=0, which counts collisions.\nThe uniform difference property is stronger.\n(Similarly, a universal family can be XOR universal if, the value is uniformly distributed in [m] where \\oplus is the bitwise exclusive or operation. This is only possible if m is a power of two.)\nAn even stronger condition is [pairwise independence](https://bliptext.com/articles/pairwise-independent): we have this property when we have the probability that x,y will hash to any pair of hash values z_1, z_2 is as if they were perfectly random:.\nPairwise independence is sometimes called strong universality.\nAnother property is uniformity.\nWe say that a family is uniform if all hash values are equally likely: for any hash value z. Universality does not imply uniformity.\nHowever, strong universality does imply uniformity.\nGiven a family with the uniform distance property, one can produce a pairwise independent or strongly universal hash family by adding a uniformly distributed random constant with values in [m] to the hash functions.\n(Similarly, if m is a power of two, we can achieve pairwise independence from an XOR universal hash family by doing an exclusive or with a uniformly distributed random constant.) Since a shift by a constant is sometimes irrelevant in applications (e.g. hash tables), a careful distinction between the uniform distance property and pairwise independent is sometimes not made.\nFor some applications (such as hash tables), it is important for the least significant bits of the hash values to be also universal.\nWhen a family is strongly universal, this is guaranteed: if H is a strongly universal family with m=2^L, then the family made of the functions for all h \\in H is also strongly universal for L'\\leq L. Unfortunately, the same is not true of (merely) universal families.\nFor example, the family made of the identity function h(x)=x is clearly universal, but the family made of the function fails to be universal.\n[UMAC](https://bliptext.com/articles/umac-cryptography) and [Poly1305-AES](https://bliptext.com/articles/poly1305-aes) and several other [message authentication code](https://bliptext.com/articles/message-authentication-code) algorithms are based on universal hashing.\nIn such applications, the software chooses a new hash function for every message, based on a unique nonce for that message.\nSeveral hash table implementations are based on universal hashing.\nIn such applications, typically the software chooses a new hash function only after it notices that \"too many\" keys have collided; until then, the same hash function continues to be used over and over.\n(Some collision resolution schemes, such as [dynamic perfect hashing](https://bliptext.com/articles/dynamic-perfect-hashing), pick a new hash function every time there is a collision. Other collision resolution schemes, such as [cuckoo hashing](https://bliptext.com/articles/cuckoo-hashing) and [2-choice hashing](https://bliptext.com/articles/2-choice-hashing), allow a number of collisions before picking a new hash function).\nA survey of fastest known universal and strongly universal hash functions for integers, vectors, and\nstrings is found in.\n\n# Mathematical guarantees\nFor any fixed set S of n keys, using a universal family guarantees the following properties.\nAs the above guarantees hold for any fixed set S, they hold if the data set is chosen by an adversary.\nHowever, the adversary has to make this choice before (or independent of) the algorithm's random choice of a hash function.\nIf the adversary can observe the random choice of the algorithm, randomness serves no purpose, and the situation is the same as deterministic hashing.\nThe second and third guarantee are typically used in conjunction with [rehashing](https://bliptext.com/articles/double-hashing).\nFor instance, a randomized algorithm may be prepared to handle some O(n) number of collisions.\nIf it observes too many collisions, it chooses another random h from the family and repeats.\nUniversality guarantees that the number of repetitions is a [geometric random variable](https://bliptext.com/articles/geometric-distribution).\n\n# Constructions\nSince any computer data can be represented as one or more machine words, one generally needs hash functions for three types of domains: machine words (\"integers\"); fixed-length vectors of machine words; and variable-length vectors (\"strings\").\n\n## Hashing integers\nThis section refers to the case of hashing integers that fit in machines words; thus, operations like multiplication, addition, division, etc. are cheap machine-level instructions.\nLet the universe to be hashed be.\nThe original proposal of Carter and Wegman was to pick a prime p \\ge |U| and define\nwhere a,b are randomly chosen integers modulo p with a \\neq 0.\n(This is a single iteration of a [linear congruential generator](https://bliptext.com/articles/linear-congruential-generator).)\nTo see that is a universal family, note that h(x) = h(y) only holds when\nfor some integer i between 0 and (p-1)/m.\nSince p \\ge |U|, if x \\neq y their difference x-y is nonzero and has an inverse modulo p. Solving for a yields\nThere are p-1 possible choices for a (since a=0 is excluded) and, varying i in the allowed range, possible non-zero values for the right hand side.\nThus the collision probability is\nAnother way to see H is a universal family is via the notion of [statistical distance](https://bliptext.com/articles/statistical-distance).\nWrite the difference h(x) - h(y) as\nSince x - y is nonzero and a is uniformly distributed in, it follows that a(x-y) modulo p is also uniformly distributed in.\nThe distribution of is thus almost uniform, up to a difference in probability of \\pm 1/p between the samples.\nAs a result, the statistical distance to a uniform family is O(m/p), which becomes negligible when p \\gg m.\nThe family of simpler hash functions\nis only approximately universal: for all x\\neq y. Moreover, this analysis is nearly tight; Carter and Wegman show that whenever.\n\n### Avoiding modular arithmetic\nThe state of the art for hashing integers is the **multiply-shift** scheme described by Dietzfelbinger et al. in 1997.\nBy avoiding modular arithmetic, this method is much easier to implement and also runs significantly faster in practice (usually by at least a factor of four ).\nThe scheme assumes the number of bins is a power of two, m=2^M.\nLet w be the number of bits in a machine word.\nThen the hash functions are parametrised over odd positive integers a < 2^w (that fit in a word of w bits).\nTo evaluate h_{a}(x), multiply x by a modulo 2^w and then keep the high order M bits as the hash code.\nIn mathematical notation, this is\nThis scheme does not satisfy the uniform difference property and is only 2/m-almost-universal; for any x\\neq y,.\nTo understand the behavior of the hash function,\nnotice that, if and ay\\bmod 2^w have the same highest-order 'M' bits, then has either all 1's or all 0's as its highest order M bits (depending on whether or is larger).\nAssume that the least significant set bit of x-y appears on position w-c.\nSince a is a random odd integer and odd integers have inverses in the [ring](https://bliptext.com/articles/ring-mathematics) Z_{2^w}, it follows that will be uniformly distributed among w-bit integers with the least significant set bit on position w-c.\nThe probability that these bits are all 0's or all 1's is therefore at most 2/2^M=2/m.\nOn the other hand, if c < M, then higher-order M bits of contain both 0's and 1's, so it is certain that.\nFinally, if c=M then bit w-M of is 1 and if and only if bits are also 1, which happens with probability.\nThis analysis is tight, as can be shown with the example x=2^{w-M-2} and y=3x.\nTo obtain a truly 'universal' hash function, one can use the multiply-add-shift scheme that picks higher-order bits\nwhere a is a random positive integer with a < 2^{2w} and b is a random non-negative integer with b < 2^{2w}.\nThis requires doing arithmetic on 2w-bit unsigned integers.\nThis version of multiply-shift is due to Dietzfelbinger, and was later analyzed more precisely by Woelfel.\n\n## Hashing vectors\nThis section is concerned with hashing a fixed-length vector of machine words.\nInterpret the input as a vector of k machine words (integers of w bits each).\nIf H is a universal family with the uniform difference property, the following family (dating back to Carter and Wegman ) also has the uniform difference property (and hence is universal):\nIf m is a power of two, one may replace summation by exclusive or.\nIn practice, if double-precision arithmetic is available, this is instantiated with the multiply-shift hash family of hash functions.\nInitialize the hash function with a vector of random **odd** integers on 2w bits each.\nThen if the number of bins is m=2^M for M\\le w:\nIt is possible to halve the number of multiplications, which roughly translates to a two-fold speed-up in practice.\nInitialize the hash function with a vector of random **odd** integers on 2w bits each.\nThe following hash family is universal:\nIf double-precision operations are not available, one can interpret the input as a vector of half-words (w/2-bit integers).\nThe algorithm will then use multiplications, where k was the number of half-words in the vector.\nThus, the algorithm runs at a \"rate\" of one multiplication per word of input.\nThe same scheme can also be used for hashing integers, by interpreting their bits as vectors of bytes.\nIn this variant, the vector technique is known as [tabulation hashing](https://bliptext.com/articles/tabulation-hashing) and it provides a practical alternative to multiplication-based universal hashing schemes.\nStrong universality at high speed is also possible.\nInitialize the hash function with a vector of random integers on 2w bits.\nCompute\nThe result is strongly universal on w bits.\nExperimentally, it was found to run at 0.2 CPU cycle per byte on recent Intel processors for w = 32.\n\n## Hashing strings\nThis refers to hashing a variable-sized vector of machine words.\nIf the length of the string can be bounded by a small number, it is best to use the vector solution from above (conceptually padding the vector with zeros up to the upper bound).\nThe space required is the maximal length of the string, but the time to evaluate h(s) is just the length of s. As long as zeroes are forbidden in the string, the zero-padding can be ignored when evaluating the hash function without affecting universality.\nNote that if zeroes are allowed in the string, then it might be best to append a fictitious non-zero (e.g., 1) character to all strings prior to padding: this will ensure that universality is not affected.\nNow assume we want to hash, where a good bound on \\ell is not known a priori.\nA universal family proposed by treats the string x as the coefficients of a polynomial modulo a large prime.\nIf x_i \\in [u], let be a prime and define:\nUsing properties of modular arithmetic, above can be computed without producing large numbers for large strings as follows:\nThis [Rabin-Karp rolling hash](https://bliptext.com/articles/rolling-hash) is based on a [linear congruential generator](https://bliptext.com/articles/linear-congruential-generator).\nAbove algorithm is also known as Multiplicative hash function.\nIn practice, the mod operator and the parameter p can be avoided altogether by simply allowing integer to overflow because it is equivalent to mod (Max-Int-Value + 1) in many programming languages.\nBelow table shows values chosen to initialize h and a for some of the popular implementations.\nConsider two strings and let \\ell be length of the longer one; for the analysis, the shorter string is conceptually padded with zeros up to length \\ell.\nA collision before applying implies that a is a root of the polynomial with coefficients.\nThis polynomial has at most \\ell roots modulo p, so the collision probability is at most \\ell/p.\nThe probability of collision through the random brings the total collision probability to.\nThus, if the prime p is sufficiently large compared to the length of strings hashed, the family is very close to universal (in [statistical distance](https://bliptext.com/articles/statistical-distance)).\nOther universal families of hash functions used to hash unknown-length strings to fixed-length hash values include the [Rabin fingerprint](https://bliptext.com/articles/rabin-fingerprint) and the [Buzhash](https://bliptext.com/articles/buzhash).\n\n### Avoiding modular arithmetic\nTo mitigate the computational penalty of modular arithmetic, three tricks are used in practice:","revisionCount":0},"hasMore":false,"nextCursor":null}

History