Mathematical function that maps arbitrarily-sized data to fixed-size integers, often used as keys in hash tables or to help ensure data integrity

learn more… | top users | synonyms

2
votes
0answers
32 views

Distance preserving projection for Euclidean distance

Suppose I have two vectors $V_1, V_2 \in R^l$. Can they be converted into bit vectors $B_1,B_2 \in \{0,1\}^l $ such that if $V_1, V_2$ is close in Euclidean distance, $B_1,B_2$ is close in hamming ...
3
votes
1answer
74 views

Why does appending permutations of servers at the end of hash table avoid bottlenecks?

I was reading the following FDS paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf The paper has a TLT (tract locator table) for identifying where to write in each ...
2
votes
1answer
27 views

Why does the following function distribute things in a binomial distribution?

I was reading the following FDS paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf and it says that the the following hash function does not distribute things uniformly ...
0
votes
1answer
40 views

Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, ...
2
votes
1answer
49 views

Why is the initial state of Zobrist hashing random?

When generating a board for Zobrist hashing, why are the initial elements random? How can you detect changes to elements later if the initial values are random?
1
vote
1answer
50 views

Help in understanding exactly how lattices used as one way functions for hashing

(This question is related to homework) I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority ...
2
votes
1answer
52 views

Sequential numbers to unique-looking numbers

I'm not sure how to word this because I'm not familiar with this, but I'm sure a process like this is rather common. Basically, I've got members signing up for our website, and each one is assigned a ...
0
votes
1answer
51 views

Transform values of hash functions like MD5 into numbers

I have read about the hash function MD5. I found an online calculator which counts the value of MD5 for different data. But the MD5 function returns as result strings like ...
7
votes
2answers
162 views

Fast hashing: combination of different techniques to identify changes in a file?

I want to create a fast way to detect whether a file might or might not be the same. For almost 100% sureness I would use an existing hash algorithm, e.g. SHA256. However, the files are expected to be ...
1
vote
2answers
43 views

Hashing a Specific Range Of a Character Array [closed]

I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my ...
4
votes
2answers
115 views

How does taking modulo 1 make sense?

I need some help understanding the problem statement in CLRS 11.3-4 pg 269. It says: Consider a hash table of size $m = 1000$ and a corresponding hash function $ h(k) =\left \lfloor m(kA ...
5
votes
1answer
129 views

Universal Hashing in Practice

A family $H$ of hash functions $h: U \rightarrow \{0,\ldots,M-1\}$ is universal if $$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$$ You can find more about ...
1
vote
0answers
26 views

Min/max of hash function (Whirlpool)

The Whirlpool hash function generates a 128-digit hexadecimal number. Could that number ever be ...
2
votes
2answers
214 views

why not just use a random number generator as a hash function?

I guess at the heart of this is that I don't really understand hash functions. One article says any function mapping objects to an object of fixed size: A hash function usually means a function ...
1
vote
1answer
115 views

Double hashing - probe count probabilities

From TAoCP, Vol. 3 by Knuth we know that expected (mean) probe counts for hash tables with open adressing and double hashing collision-resolution are: $1 \over 1 - \alpha$ - for unsuccessful search ...
0
votes
1answer
157 views

Find similar vector by Locality Sensitive Hashing

I have many vectors in my database. They are in high dimensions such as: $v_1$ : $\langle 23, 23, 1, 33, 103, 219, \dots \rangle$ $v_2$ : $\langle 92, 83, 1, 33, 239, 192, \dots \rangle$ ... I ...
0
votes
1answer
767 views

Retrieving data from hash table ordered by insertion time

By default, a hash table is unordered. I have a simple question on the retrieval of elements in a hash table Can we retrieve elements from a hash table in the same order as they are put inside?
-1
votes
1answer
59 views

Complexity of a hash tables with balanced trees in the buckets

If I use a balanced tree instead of lists in a hash table implementation, and also after initializing my table I don't enlarge nor reduce the size of the table, what would be the worst case ...
3
votes
1answer
166 views

Bloom filter and perfect hashing

Bloom filter use a hash function to test membership for S by checking if an item is present of not at the specified position. To mitigate the effect of hash collision, multiple functions are used, ...
2
votes
2answers
82 views

Are those definitions of universal hash family equivalent?

I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is. Definition 1: $H$ is a universal ...
2
votes
0answers
65 views

Collisions of a compression function

I tried posting this in the math forum but I didn't get any responses. I was hoping someone could give me some advice for how to approach the following problem. If $n$ is a positive integer, let ...
2
votes
1answer
104 views

Proving 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 ...
9
votes
3answers
2k views

Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$ H = k \bmod \ 11$$ Now all the values will be placed ...
3
votes
1answer
122 views

Hashing algorithm for millions of variable length strings (URLs)

The goal is to distribute approximately 100 million variable length strings, average length 100 characters, uniformly among 100 million buckets. Perfection not required, just no egregious clumping. ...
1
vote
1answer
306 views

How to get expected running time of hash table?

If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
2
votes
1answer
125 views

Hash function - uniformity / strong universality

I am currently learning how randomised Hashing works. So, you have a class (aka family) $H$ of hash functions, each of which maps the universe $U$ to the hash table $N$. That class is called ...
2
votes
2answers
192 views

What is Harrison hashing, its applications in web search engines?

What is Harrison hashing and what are its applications in web searching? Can some one give me some relevant information? Update: I found it here , and is a part of M.Tech syllabus of a friend ...
2
votes
2answers
369 views

Collision resistant hash function

A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$. ...
5
votes
1answer
464 views

Why does the Count-Min Sketch require pairwise independent hash functions?

The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream. Intuitively, it works by picking a variety of hash functions, hashing each ...
6
votes
5answers
149 views

Is the codomain/range of a hash function always $\mathbb{Z}$ or $\mathbb{N}$?

From Wikipedia A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length. For example, a person's name, ...
12
votes
2answers
150 views

Function that spreads input

I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics: $f$ should be bijective Both $f$ and $f^{-1}$ should be calculable pretty fast ...
2
votes
1answer
123 views

How do the following Hash Functions compare?

Consider the two hash functions used to map IP addresses. $x_i$ represents a octave (or "bit field") of the address. Hash Function 1: $$h_a(x_1, x_2, x_3, x_4) = \sum^{4}_{i=1} a_ix_i \bmod n$$ ...
2
votes
1answer
159 views

Modulo hash function and multiples of three

This is a textbook based question. In The Art of Computer Programming Volume 3, Knuth says that for a hash function $h(k) = k \bmod M$, $M$ should not be a multiple of $3$. The explanation given is: ...
1
vote
2answers
150 views

Collisions of prefixes of MD5 hashes in some fixed interval

I was wondering, if there is an MD5 hash collision in the UNSIGNED MEDIUMINT Range (0 - 16777215). Sadly, I'm unable to run a script to check this myself, due to Memory (RAM) limitations. The answer ...
3
votes
0answers
101 views

Algorithm that hashes a collection of sets following their disjointness relation

I wonder whether there is a simple algorithm to do this work: Say I have a collection of objects $C$, and a binary relation $R: C\times C$ that is auto-reflective ($\forall c\in C: c R c$) , and ...
5
votes
1answer
181 views

A hash function with predicted collisions

As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with predicted collisions? In other words, a hash function that collides ...
9
votes
1answer
293 views

Weak hashing function for memorable IPv6 addresses

IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4. There have been ...
1
vote
1answer
116 views

Is open adressing with prime steps bijective?

Who can help me with this topic: Probing with a step width that is a prime number. I am struggling with this question about defining a hashing function $h(k, i)$ for open addressing on a table of ...
8
votes
1answer
170 views

Attack on hash functions that do not satisfy the one-way property

I am revising for a computer security course and I am stuck on one of the past questions. Here is it: Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to ...
10
votes
2answers
878 views

Could quantum computing eventually be used to make modern day hashing trivial to break?

Simply put, if one were to build a quantum computing device with the power of, say, 20 qubits, could such a computer be used to make any kind of modern hashing algorithm useless? Would it even be ...