# 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.

251 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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
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: ...
231 views

• 1,189
1 vote
139 views

### Domain of hash function

I am reading Buchmann's Introduction to Cryptography, 2nd ed. On page 267, $G$ is a finite cyclic group of prime order $q$. $a\in\mathbb{Z}_{q}=\mathbb{Z}/q\mathbb{Z}$. $h:\{0,1\}^{*}\to G$ is a hash ...
• 1,889
1 vote
307 views

### Analysis of multiplication method for hashing

Given two hashing functions, namely: division method versus multiplication method disadvantages. Multiplication method: Given that we have hash function $f(k)=⌊N\times(kA−⌊kA⌋)⌋$, where $N,k\in Z$ and ...
• 1,189
1 vote
726 views

### Produce a unique integer out of list of integers with constraints

Problem I am a computer programmer looking for a mathematical function (or a more advanced algorithm) able to produce a 32bits integer out of a list of integers with the following constraints: Each ...
• 53
180 views

### Is it possible to efficiently solve a system of Boolean equations only containing XOR?

Let $h$ and $x$ be vectors of Boolean variables. Given a system of Boolean equations like  h_0 = x_0 \oplus x_2 \oplus x_4 \\ h_1 = x_0 \oplus x_3 \oplus x_5 \\ h_2 = x_1 \oplus x_2 \oplus x_5 \\ ...
• 123
19 views

### Conditioning on the output of a function from Universal set, find input that causes collision

We have a Universal set of functions that map the universe of inputs to $\mathbb{Z_{p}}$ with prime $p$, in the sense that for any two non-equal $x$ and $y$ inputs into a uniformly randomly chosen one,...
• 273
44 views

### Perfect Hash Function that detects invalid inputs?

I work in hardware/electronics where everything is power of 2. To avoid storing the key along with the value, I can find a perfect hash function for the known-in-advance keys. Nevertheless, the PHF ...
• 101
3k views

• 301
1 vote