Hot answers tagged

47 votes
Accepted

What exactly (and precisely) is "hash?"

The Wikipedia article on hash functions is very good, but I will here give my take. What is a hash? "Hash" is really a broad term with different formal meanings in different contexts. There ...
user avatar
  • 4,029
10 votes

What exactly (and precisely) is "hash?"

A hash function is a function that takes an input and produces a value of fixed size. For example you might have a hash function stringHash that accepts a ...
user avatar
  • 291
7 votes
Accepted

Two-way Hash Functions

Yes, this is possible. Here are two examples of such a function. One function is $f(x)=x$. This has no collisions, and the function is easy to invert. Here is another function: define $f(x) = x$ ...
user avatar
  • 143k
6 votes
Accepted

Hash functions and pathological data sets

An easy way to visualize this is to imagine a hash table of size $n$ (implemented with chaining) that contains all of the elements of $U$ (even though this is unrealistic in practice because $U$ ...
user avatar
6 votes
Accepted

Understanding hashtable performance in the worst-case

The load factor denotes the average expected length of a chain, therefore it is interesting for an average case analysis, not the worst case analysis. That's why on average you expect needing constant ...
user avatar
6 votes

Can we remove duplicates faster than we can sort?

It is a classical result that the element distinctness problem requires $\Omega(n\log n)$ comparisons in the comparison model (the one used to analyze sorting algorithms); in fact, it also requires $\...
user avatar
5 votes

simple uniform hashing: unclear definition of probability

First, the outcome of a situation being deterministic doesn't mean we will necessarily assign a probability of $1$ or $0$ to it. If I say I'm going to flip a coin, but it is actually a double-sided ...
user avatar
5 votes

How do you find a hash function that respects a custom equality function?

The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever ...
user avatar
  • 29.2k
4 votes

Finding a (minimal?) program that maps $M$ items to indices $[0,M)$

There is a deterministic algorithm for constructing a perfect hash, if you don't care about efficiency. For instance, you can enumerate all programs (in order of increasing size) and test each one to ...
user avatar
  • 143k
4 votes
Accepted

Why Bloom filter needs $\frac{m}{n}\ln{2}$ hash functions?

This is explained in Wikipedia. Given $n,m$, the false positive probability is $$ \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k. $$ This is the quantity we want to minimize. While the exact ...
user avatar
4 votes
Accepted

Two definitions of universal hash functions

The two definitions are not equivalent. The second definition does not imply the first. You can take $\mathcal{H}$ to be the collection of all functions $h$ such that $h(1) = 1$.
user avatar
4 votes

Fast comparison with a tolerance

If for all $|r - s| < 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise). What you are asking is impossible. One thing which is possible is to compare keys with three rather ...
user avatar
4 votes
Accepted

Hash multiple integers directly using FNV-1a

It's not equivalent, and I suspect there will be a loss of statistical randomization/mixing. The core step that offers mixing of the bits is multiplication by ...
user avatar
  • 143k
4 votes
Accepted

Embedding high dimensional vectors into low dimensional space preserving similarity

Locality-sensitive hashing is one reasonable approach for this. I suggest reading standard resources on locality-sensitive hashing (LSH). In your case, a locality-sensitive hash is a hash function ...
user avatar
  • 143k
4 votes

Difference between properties of good hash function: uniformity and randomness

Uniformity is about potential values, while randomness is about actual values. For example, suppose you make a very simple hash function that takes the first byte of a string, resulting in 256 ...
user avatar
4 votes

Hash functions and pathological data sets

Assume there is no such bucket. Then each bucket has at most $|U|/n - 1$ items. There are $n$ buckets, so the total number of items is at most $n*(|U|/n - 1) = |U| - n$. This is less than $|U|$, which ...
user avatar
  • 3,235
4 votes
Accepted

Knuth's proof of O(1) for linear probing

Let $p_i$ be the probability that position $i$ is empty. A simple coupling (detailed below) shows that $p_i = p_j$ for all $i,j$, and so $Mp_0 = p_0 + \cdots + p_{M-1}$. Now let $X_i$ be the indicator ...
user avatar
4 votes
Accepted

Ketama hash explanation

This is simply a way to generate 32-bit hash for the string. Assuming that MD5 is a good cryptographic hash function, it doesn't matter which bits you take from the hash and in which order you ...
user avatar
4 votes

is modulo of hash function is evenly distributed?

if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed? It depends on the hash function. For a good hash ...
user avatar
3 votes
Accepted

Locality-sensitive hashing random projection

No. The statement you're reading is correct. Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens. The ...
user avatar
  • 143k
3 votes

Hash function to hash 6-digit positive integers

A hash function cannot avoid collisions when the size $M$ of the hash table is smaller than the size of the universal set $U$ that you are hashing. This is a consequence of the compression step. In ...
user avatar
3 votes

Hash function to hash 6-digit positive integers

A hash table usually uses two different things: One, a hash function that maps an item to a hash code (with the requirement that equal items are mapped to equal hash codes), and two, a function that ...
user avatar
  • 25.5k
3 votes

What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$

The mean chain length is the sum of the chain lengths divided by the number of chains. The sum of the chain lengths is, by definition $n$ and the number of chains is $m$. This is by far the easiest ...
user avatar
  • 19.1k
3 votes

Merkle tree collision probability

Yes, the root has a higher probability of collision. Take, for example, simple trees with two leaves. Label tree 1's leaves $A$ and $B$, and tree 2's leaves $X$ and $Y$. The probability that the ...
user avatar
  • 3,235
3 votes

Hash function to hash 6-digit positive integers

I think you've missed the point of hash tables. Hash tables are used to give array-like access to a dataset that's too big and sparse to store in an array. So, for example, it sounds like you're ...
user avatar
3 votes
Accepted

Given a string, is it possible to determine which hashing algorithm has produced it, if any?

You will first need to define what you mean by a hashing algorithm. For example, my favorite hashing algorithm is simple: check whether the input is "string", and if so, output "...
user avatar
3 votes

Given a string, is it possible to determine which hashing algorithm has produced it, if any?

No it is not possible to determine that is produced by a hashing algo, or which one that produced it -- at least not from a single sample. Good hashing algo will produce a uniform set of values ...
user avatar
  • 209
3 votes

Two-way Hash Functions

In addition to everything that others have said: any cipher is an invertible "hash" function. And there are standard ways to construct them; one common way of turning a one-way function into an ...
user avatar
  • 19.1k
3 votes
Accepted

Lemma 2 in Knuth's "Notes on Open Addressing"

I think that the notes have been reported incorrectly. Indeed CruiskeenLawn, you are right. I've found some very old notes here which report the correct result. Indeed, in your copy, they simply ...
user avatar
  • 460
3 votes
Accepted

Is there a heuristic or function to determine if two arrays of integers are alike or similar

There are many measures of similarity between sequences (or arrays or even strings), which one to use depends on the specific goals for the similarity. It may be the case that some trial and error is ...
user avatar
  • 6,998

Only top scored, non community-wiki answers of a minimum length are eligible