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

235 questions
Filter by
Sorted by
Tagged with
14 views

### Convert an arbitrary string of bits to a 3D color such that strings with more bits in common have more similar colors

I am toying with a genetic algorithm for the first time to evolve a very simple neural network. For the purpose of rendering, I would like to assign my agents a color based on their 'genome', such ...
• 121
10 views

### Need to create Minimal Perfect Hash Function

The Task: Let, on a given set of words, two hash functions $h_1, h_2$ give the values ​​indicated in the table. It is necessary to construct the minimal perfect hash function for this set of words. ...
22 views

### Number of possible values of n bit hash function

I was going through the hash function and its properties, The main strength of the hash function depends on the number of bits $n$. While calculating the collision it considered that there are $2^n$ ...
246 views

• 23
14 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,...
• 173
24 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
803 views

• 269
1 vote
36 views

### Possibility of duplicates in hash table

I have a problem where I am trying to find the relationship between parts and the parts that make them up. Like if a boiler is made with two side plates and one bottom plate, and the side plates have ...
• 1,725
99 views

### How to overcome the wastefulness of uniform distributions in a hash function

Recently on the programming StackOverflow I posted a query about my hash function - I was looking for mistake when there was none. I was alarmed by an empty bucket count of around 36%, as I thought, ...
• 14k
59 views

156 views

### Probability distribution for collisions / birthday problem

Let's say I have a source of randomly produced values from a range $M$. I want to test if the source is a uniform distribution by examining a sample sequence of $n$ values $m_1, m_2,\dots,m_n$. ...
88 views

### Probability a near universal hash function $ax \mod p \mod m$ produces an output from inputs equal modulo $m$

For a given near universal hash function $f(x) = ax \mod p \mod m$ where $p$ is prime and $m < p$, what is the probability that given $x_r \in \{ x | x \mod p \mod m =r\}$, $f(x_r) = s$? That is, ...
• 21
1 vote
37 views

### show that $h(k)=\left \lfloor{\frac{k}{m}}\right \rfloor \mod m$ is a bad hash function where $m$ is prime

A "good" hash function should make use of all slots with equal frequency. In this case the ammount of slots is given with $m$. Also keys which are similar should be distributed as broadly as possible....
• 1,225
1 vote