Skip to main content
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 ...
usul's user avatar
  • 4,129
22 votes

Do passwords need a max length?

No. There is no* limit on the length of the input to for most* good cryptographic hash functions. As a result, password hashing can support passwords of unlimited length and do not need to impose a ...
D.W.'s user avatar
  • 161k
11 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 ...
Pharap's user avatar
  • 301
9 votes

Do passwords need a max length?

Yes, passwords need maximum length, but not because of collision risk (see other answers regarding collisions). Reason for setting maximum length - possibility of denial of service attack. Someone ...
IndustryUser1942's user avatar
8 votes

Do passwords need a max length?

As hashes are fixed length, does that mean that even if not specified when creating the password, all login systems would need to have some sort of maximum input length (although probably very high)? ...
ilkkachu's user avatar
  • 191
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$ ...
D.W.'s user avatar
  • 161k
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$ ...
Mario Cervera's 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 ...
Philip Becker's 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 $\...
Yuval Filmus's 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 ...
Derek Elkins left SE's 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 ...
Joey Eremondi's user avatar
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 ...
Gilles 'SO- stop being evil''s user avatar
4 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 ...
jbapple's user avatar
  • 3,380
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 ...
D.W.'s user avatar
  • 161k
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 ...
D.W.'s user avatar
  • 161k
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 ...
jbapple's user avatar
  • 3,380
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$.
Yuval Filmus's user avatar
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 ...
Yuval Filmus's 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 ...
Dmitri Urbanowicz's 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 ...
Tom van der Zanden's user avatar
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 ...
Pseudonym's user avatar
  • 22.2k
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 ...
D.W.'s user avatar
  • 161k
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 ...
Soren's user avatar
  • 209
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 "...
Lieuwe Vinkhuijzen's user avatar
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 ...
David Richerby's user avatar
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 ...
Mario Cervera's 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 ...
gnasher729's user avatar
  • 30.5k
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 ...
Maczinga's user avatar
  • 460
3 votes

How does Rabin fingerprint finds breakpoints (chunk boundary)?

Note that any hash algorithm can be used to break files into chunks where chunk boundaries don't change much after inserts/deletes. Rabin fingerprinting (and RabinKarp rollsums) are just hash ...
Donovan Baarda's user avatar
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 ...
Discrete lizard's user avatar
  • 8,303

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