Questions tagged [hash-function]
For questions about hash functions: functions from a big set to a smaller one such that the same output $f(x_1)=f(x_2)$ for different input $x_1\ne x_2$ is unlikely, especially if $x_2$ differs from $x_1$ by a random error or is crafted by an adversary.
252
questions
0
votes
0
answers
25
views
Hash Table and uniformly distribution
I'm trying to understand the relationship between input distributions and hash function performance in hash tables. In statistics, the theoretical probability of landing in a specific slot of a hash ...
- 1
1
vote
0
answers
58
views
Hashing pointers against the largest prime
In another forum someone asked for a hash-function to hash pointers. I suggested to multiply the pointer with the lagest prime fitting into an uintptr_t and ignore the overflow. Someone said that this ...
0
votes
0
answers
12
views
k-independent hash functions vs. orthogonal arrays
In some randomised algorithms, such as Alon-Matias-Szegedy (AMS) algorithm, two different strategies are used for the generation of a family of random numbers with some special correlation properties:
...
- 1,191
0
votes
0
answers
25
views
Expected number of collsions in hashing
Suppose we use a hash function h to hash n keys into m slots. Assuming simple uniform hashing, what is the expected number of collisions? (CLRS, 3rd edition, problem 11.2-1)
My solution is as follows:
...
3
votes
1
answer
231
views
UPD: Structure of subgroups of $S_{2^n}$ generated by $\langle x \mapsto ax \mod 2^n \rangle$ and linear groups
It's a very well known result by Gauss that $(\mathbb{Z}/2^n \mathbb{Z})^\times = \langle -1 \rangle \times \langle 3 \rangle \cong C_2 \times C_{2^{n-2}}$.
Consider a faithful action $\mathrm{mul}: (\...
- 7,585
1
vote
1
answer
57
views
Collision probability of hash function $(ax + b)\bmod m$
I'm trying to calculate the probability of collision for the following family of hash functions:
$$h_{a, b}(x) = (ax+ b) \mathrm{mod}{m} \quad \quad m\in\mathrm{Z}_p, \ a\in\{0, 1, \ldots, m - 1\}, \ ...
- 830
1
vote
0
answers
34
views
Proof of Strong Universality of a Hash Function
I read about a Strongly universal hash function from 64-bit keys to 32 bits, in this paper.
It uses the following function:
$h(x) = ((a_1 + x) \cdot (a_2 + (x \gg 32)) + b) \gg (64 - \ell)$
Where $...
- 11
0
votes
0
answers
36
views
Proving pairwise independence for random matrix hash functions
Let $H_n^m$ be the family of hash functions with $h(x) = Ax + b$ for $A \in \mathbb{Z}_2^{m \times n}$ and $b \in \mathbb{Z}_2^m$. I'm trying to prove that this family of hash functions is pairwise-...
- 260
0
votes
1
answer
39
views
Uniform Distribution of a mod hash function
I wonder if there is any efficient way to determine whether the hash values of $h(x)=3x\ mod\ 2^{64}$ are uniformly distributed for $x$ being uniformly distributed in $[0,2^{512}-1]$?
I try to ...
- 135
0
votes
0
answers
44
views
Scaling a threshold for anomaly detection depending on the sample size
I'm trying to study and test 32-bit hash functions - specifically probability of collision (repeated results for different inputs). And I'm struggling in defining a threshold for outliers/anomalies, ...
- 101
0
votes
0
answers
22
views
Minimum Number of Functions for a Universal Hash Family Mapping {a, b, c, d} to {0, 1}
Determining the Minimum Size of a Universal Hash Family
I'm working on understanding universal hash families and encountered a problem that I'm struggling to solve. The problem is as follows:
Consider ...
- 161
0
votes
0
answers
21
views
Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2]
I came upon the following hash function (pseudo-code):
...
- 13
2
votes
1
answer
280
views
What is the probability that the hash of a hash is the same hash?
Given an $n$-bit uniform cryptographic hash function (128-bit md5, 256-bit sha-256, etc), what is the probability that the input ...
- 67
1
vote
1
answer
54
views
Bucket loads with hashtable
I have a math problem that derives from the frequency with which buckets are occupied in a hash table. Suppose we have a hash table that has as many buckets as there are nodes, i.e. the nominal load ...
1
vote
1
answer
121
views
Probability of collision in a hash function.
Let $T = {1,...,m-1}$ be a hash table with open addressing, and for i = 1,...,n with $n \leq \frac{m}{2}$ let $X_i$ be a random variable denoting the number of probes for the i-th entry being added ...
- 351