# Tag Info

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 ...
Accepted

### Why is a (collision-less) hashtable lookup really O(1)?

The hash function doesn't return some string such as mkwer. It directly returns the position of the item in the array. If, for example, your hash table has ten ...

### 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 ...
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 ...
Accepted

### 1-to-1 cryptographically secure bit shuffling

This is known as a one-way permutation. The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements. There are various candidate ...
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 ...

### 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 ...
Accepted

Accepted

### Hash-Table in Practice

SHA1 or SHA256, whichever you use, is for any practical purpose a random function. What you are observing is that random allocation is not as good as deterministic allocation. If you knew all the ...
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 ...
Accepted

### Is the following intuition valid for understanding $k$-wise independent hash functions?

Your intuition is exactly right. Yes, that's equivalent to choosing a random polynomial over $\mathbb{F}_p$. The reason why it works is exactly the interpolation theorem for finite fields. $k$-wise ...
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'...

### 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 ...

### 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 "...
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{...

### 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 ...
Accepted

### Understanding Murmur3

You have asked two questions. I will answer them one by one. Choosing the seed. The usual approach here is to choose the seeds randomly once and for all, and to hard-code them. If the hash family is ...

### Why is a (collision-less) hashtable lookup really O(1)?

To expand on David Richerby's answer, the term "hash function" is a little overloaded. Often, when we talk about a hash function we think of MD5, SHA-1, or something like Java's ...
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$.

### 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 ...
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 ...
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 ...

### "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 ...
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 ...
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 ...