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

177 questions
Filter by
Sorted by
Tagged with
10 views

### What is the formula for calculating load factor of hash table when collisions are handled by many different techniques?

I am in a rush to submit some assignment, may I have the formula for calculating the load factor of hash tables when collisions are handled by linear probing, quadratic probing and double hashing? I ...
41 views

### Probability of distribution using a discrete random function

Problem: Given P persons (say 1000) distribued among N rooms (say 50) using a discrete random distribution function. What would be the probability of a room having at least K persons (say 30 or more ...
20 views

### A more general case of pairwise hash functions

I want to find a set $H = \{x\mid x=(x_1, x_2, \ldots, x_k), x_i \in \{0, 1, \ldots, k-1\}\}$, which is pairwise independent(every $x_i$ and $x_j$ of the vector $\mathbf x$ in the set, it's $k^2$ ...
27 views

### Universal hashing family

I'm not really sure this question is proper for MathExchange but I have found it more suitable than StackOverFlow. So, I'm taking the course of Data Structures and Algorithms and we got some example ...
13 views

### perfect hashing when not knowing the keys

knowing only the number of keys, n, how can you create a data structure of some sort that satisfies the following: initialization takes O(n) time after being initialized, you can insert and search ...
15 views

### Hash proof system programming implementation

Does anyone know if there is a hash proof system implementation using some programming language? Like C++, python.
13 views

### Prove the probability of which a hash function is collision-free

Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
26 views

### Approximating a probability threshold for hash collisions

First off: I know this is on the verge of being subjective and i'll try my best to make it as specific as possible. I am in a situation where I need to generate a fixed number of hashes (k), say 10,...
47 views

### How can I increase the complexity of a number and maintain uniqueness

I have an 8-digit number and you have an 8-digit number - I want to see if our numbers are the same without either of us passing the other our actual number. Hashing the numbers is the obvious ...
16 views

43 views

### Days required to collide at least one hash? [closed]

Sorry I am new here and learning mathematics and cryptographic problems. Assume an hash algorithm is collision resistant like SHA256, and the hash value is 64bit in length, (2^{64} possibilities) ...
103 views

### Hash without overflow

I am trying to hash an $n$-character string into one of $m$ slots by treating the string as radix-128 number without overflowing a 32-bit word, where $0 < m < 2^{31}$. I utilize the properties ...
128 views

593 views

46 views

### 3 Letter Initial Phone Keypad Hash Distribution

I have written a c++ function that generates a 3 digit number corresponding to each letter in a random 3 letter initial and their location on a phone keypad. For Example, my initials MSG, would return ...
423 views

### Why is this hash function for english words is perfect hash?

I have a question that seems really intuitive to me but I can't think of a way to prove it. Assume we a have a file with words that are different from each other and contain digits only for example ...
I read the concept about dynamical resizing hash table from this lecture. And for my understanding, it claims that the average run time of all insertions is $O(1)$ for each iteration. Now, suppose we ...