Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
2k views

Can someone offer an intuitive understanding of linear/quadratic probing and double hashing?

I'm reading through Introduction to Algorithms, and I'm having trouble grasping intuitively how linear probing, quadratic probing, and double hashing exactly work. I suspect my confusion lies within ...
4
votes
3answers
1k views

Birthday Problem applied to collisions

I'm trying to extend the birthday problem to detect collision probability in a hashing scheme. Here is my problem. I use the letters and numbers [A-Z][a-z][0-9] to make a set of keys by randomly ...
4
votes
2answers
1k views

“Additive” hash function

I need a hash function that is easily computable in parallel(think of MapReduce framework), so such hash function must be "additive". I.e. given such function f, ...
1
vote
1answer
227 views

How to create 2048 random bits from 256 bits?

Would merely repeating the same value 8 times be sufficient ? Or is there a more clever approach for doing this ? The 256 bit values would be generated from SHA256 of files.
3
votes
1answer
2k views

Difference between universal and k-universal

After reading definitions of universal and k-universal (or k-independent) hash function families, I can't get the difference between them. Also, I couldn't find any examples of hash function families ...
0
votes
1answer
269 views

probability of repeating values in a hashmap

Suppose you have a hashmap where you store values. The hashmap is of size m and supports chaining. The hash function is simple uniform hashing assumption. I understand that the average length of a ...
0
votes
1answer
249 views

Universal hashing (bijection) with multiplication

I came across this question while thinking about a CS problem: Given a set $S = [a,b]$ , and a string $x \in S^{n}, x = r_1r_2 \cdots r_n$, under what conditions is $H(x) = r_1 * r_2 * \cdots * r_n$ ...
1
vote
1answer
177 views

Function for unique hash code

I am interested in finding $F(x,y)$, such that $x$ and $y$ $\in \mathbb Z^+$ and $F(x,y)$ is one to one function i.e., $F(x,y)$ is unique for any unique unordered pairs of $x$ and $y$. Regards, ...
0
votes
1answer
116 views

Hash Functions and Probabilty

We are considering bit strings of length 160. Let there be some input x, and hash function $H(x) \rightarrow \left \{ 0,1 \right \}^{160}$. How many turns at least it takes to make collision: $H(x_{1})...
2
votes
1answer
757 views

Is the product of 2 unique prime number unique?

I am wondering if I take the product of 2 unique prime numbers, and will the product be unique ? any chance to have collision ? I mean will any other 2 unique prime numbers have the same product ? ...
0
votes
1answer
1k views

Is this function reversible?

I have a function which takes an integer from within a range (for example, 0-9999 with a range of 10,000) which outputs another integer within the same range. To my understanding, this is a perfect ...
1
vote
2answers
1k views

Proof of calculating MinHash

I'm reading about MinHash technique to estimate the similarity between 2 sets: Given set A and B, h is the hash function and $h_\min(S)$ is the minimum hash of set S, i.e. $h_\min(S) = \min(h(s))$ for ...
3
votes
1answer
1k views

Do hashing functions have a probability distribution calculated for their output?

This question might look strange, so I will try to be clear. Consider a hashing function $f : M \mapsto H$ which takes a message with arbitrary length $m \in M$ as input and returns a hash $h \in H$ ...
1
vote
1answer
2k views

hash function for matrices over finite field (Matlab)?

What is a good hash function for small nonsingular matrices over a field $\mathbb{F}_p$ for $p$ prime? I'm looking for an integer function which is close to being injective (but not necessarily ...
0
votes
1answer
2k views

Analogy of Binary subtraction to decimal subtraction [duplicate]

Possible Duplicate: How to do +, -, *, / with number in a base b? Subtraction of numbers with arbitrary bases This is a very basic question. But I come from non computer science background and ...
2
votes
1answer
4k views

Why choose a prime number as the number of slots for hashing function that uses divison method?

The division method is one way to create hash functions. The functions take the form: h(k) = k mod m Where k is a key and m is the number of slots Edit: If this is my hash function why should I ...
1
vote
2answers
146 views

How to implement a hash function intentionally prone to preimage attacks? (and hence pseudo-reversible)

I need to design a hash function such that it is possible to enumerate all possible 'candidate' input strings (preimages) for a given hash (image). It must otherwise be a normal hash function [i.e. ...
3
votes
1answer
501 views

Help in understanding the properties of prime numbers

I was reading about hashing. The oldest/standard approach is to use a prime number to produce the hash. At first I couldn't get why use a prime when I came to this Why hash functions use primes: ...
4
votes
2answers
1k views

Universal Hashing

to my current understanding Universal Hashing is a method whereby the hash function is chosen randomly at runtime in order to guarantee reasonable performance for any kind of input. I understand we ...
0
votes
1answer
119 views

Unique $C = \operatorname{hash}(A, B)$

I want to derive a non-associative operation $\circ$ such that $C = A \circ B$ and that same $C$ can not be obtained by any other combination(s) of $A$ and $B$ e.g. much like $C = \operatorname{hash}(...
0
votes
1answer
69 views

Discreet bounding/mapping function with convergence/uniformity

Firstly, I was sent here from cstheory.stackexchange.com's FAQ, please tell me if this too is the wrong board (this board's FAQ indicates that I have to goto stackoverflow ??) This is my first ...
1
vote
2answers
126 views

Can I reverse any hash algorithms to find a set of the possible orginals?

If I map 1024 bits onto a 16 bit hash (just random numbers for conversation sake), I will have an average of 64 collisions per hash (assuming a good algorithm). I wonder if anyone knows any hash ...
13
votes
3answers
1k views

Curious Properties of 33

Because my explanation has so many words, I'll start with my question and then you can read the explanation if you need to: The Bernstein Hash method uses the number 33 as a multiplier. From what I'...
1
vote
1answer
249 views

Is there some reversible mapping that as uniform as a hash?

I am looking for a mapping to encode a n-bits information into n-x+m bits. The (n-x) bits need to be as uniform as posible, and ...
2
votes
1answer
160 views

Is the encoding process in coding theory a hash function?

I was wondering if the encoding process in coding theory is a hash function? Are hash function and what is studied in coding theory basically the same thing? Thanks and regards!