Skip to main content
128 votes
Accepted

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

Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that ...
Mario Cervera's user avatar
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
  • 162k
13 votes
Accepted

What is the point in hashing a value?

The purpose of a hash in this scenario to be able to uniquely identify an entity. It's not strictly unique, only probabilistically unique. Hashes are not reversible functions, so your client can't ...
Koenig Lear's user avatar
9 votes
Accepted

Hashing using Horner’s Rule

Let's prove by induction that after $i$ iterations, $$ r = \sum_{j=1}^i 256^{i-j} c[j] \bmod m, $$ where $m$ is the size of the table. The base case is $i = 0$, where $r = 0 = 0 \bmod m$. Now suppose ...
Yuval Filmus's user avatar
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
9 votes
Accepted

Are there associative cryptographic / collision resistant hashes?

There is a plausible construction of such a hash. At design time, randomly choose two $2\times 2$ matrices with entries in $\mathbb{F}_{2^n}$ that have determinant 1, fix them, and call them $h(0),h(...
D.W.'s user avatar
  • 162k
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

Does this problem offer any insight into $P$ vs $NP$

It depends what your hash function is. If your hash function is the identity function, it's trivial to invert without constructing the hash table. Your question seems to be essentially reinventing ...
David Richerby's user avatar
6 votes
Accepted

What is the reasoning behind magic constancs in hash code calculations found in programming practice?

XOR is not a good method, because then the hash of $(a,b)$ will be equal to the hash of $(b,a)$. Also, the hash of $(a,a,c)$ will be equal to the hash of $(b,b,c)$ and to the hash of just $c$. That'...
D.W.'s user avatar
  • 162k
6 votes

Why is Big O not defined here for a hash table?

The chart is underspecified. I assume they mean by "Access" to "retrieve the $i$-th element¹. In hashtables, there is no notion of order. While you could pick the $i$-th element in the underlying ...
Raphael's user avatar
  • 72.6k
5 votes

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

First of all, the question is phrased incorrectly. The following are equivalent and correct expressions of the intended question: why must we use a prime number as the modulo of the hash value (not "...
bking's user avatar
  • 51
5 votes
Accepted

How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?

I can see some similarity too, but only in a loose sense; there are also some significant differences. Here's the similarity. Define $H_2(x)$ to be the first $d$ bits of $H(x||D)$. Then you can ...
D.W.'s user avatar
  • 162k
5 votes
Accepted

What is an example of a weakly universal hash function that is not pairwise independent?

Let $U = [m]$, and let $h$ be the identity function. If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$ h_i(x) = \begin{...
Yuval Filmus'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
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

What Exactly Does the Term "Key" Mean with Regards to a Hash Table?

A hash table is an implementation of a more general principle: A key/value table. In a key/value table you can insert values according to a key, you cannot add two values under the same key. You can ...
gnasher729's user avatar
  • 30.7k
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
  • 162k
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
  • 162k
4 votes

"Hash" Probing?

Your scheme is very similar to Cuckoo Hashing. In Cuckoo Hashing you have two (or, in variations, more) independent hash functions $h,g$. To insert an item $x$ you check at location $h(x)$. If that ...
adrianN's user avatar
  • 5,951
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

range / interval query algorithm

Use an interval tree. It is designed to support exactly this. In particular, the query "find all ranges that contain this value" is known as a stabbing query, and it can be answered in essentially $O(...
D.W.'s user avatar
  • 162k
4 votes
Accepted

Surprisingly high collision rates when hashing a short list with few buckets

Depending on how you count collisions, we can expect either about 2000 collisions, or about 1472 collisions. The latter is in close agreement with what you observe, so yes, 1500 collisions looks ...
D.W.'s user avatar
  • 162k
4 votes

Method for eliminating spent hashes from a large collection?

There is no lossless way to compress a set of arbitrary numbers where the size of the set is unbounded to a fixed number of bits. Cryptography won't help with that. If you're okay with the storage ...
Future Security's user avatar
4 votes

Can we do 4-sum algorithm in O(n^2)?

You are right, but Jeff's answer in the link you provided works in the "linear decision tree model". You cannot use hashing in that model.
hqztrue's user avatar
  • 126
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
4 votes

Store a n-bit string using only O(log n) space

There are $2^n$ many $n$-bit strings, but only polynomially many strings of length $O(\log n)$.
Yuval Filmus's user avatar
4 votes
Accepted

Self referential hash function possible?

Yes. You can construct such a function. Let $g:\{0,1\}^* \to \{0,1\}^k$ be any hash function. We will define $f$ as follows. On input $x = x_1 \cdots x_n$, compute: For $i := 1,2,3,\dots,n$, do: ...
D.W.'s user avatar
  • 162k
3 votes
Accepted

Hash functions producing uniform outputs

What are the quadratic residues in $\mathbb{Z}_{10}$? What about the cubic residues? What are the orders of $[11]$ and $[12]$ in the group $(\mathbb{Z}_{10}, +)$? A brief solution follows. For the ...
quicksort's user avatar
  • 4,272
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

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