Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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

### Is there an anti-Bloom filter?

Going with Patrick87's hash idea, here's a practical construction that almost meets your requirements — the probability of falsely mistaking a new value for an old one is not quite zero, but can ...
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

### How should I design a hash table where all the keys are permutations?

Simply compute the index of the permutation into the sorted list of all permutations and use that as your hash key. This can be achieved with a relatively simple algorithm: https://stackoverflow.com/...
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 ...

### Is there an anti-Bloom filter?

No, it is not possible to have an efficient data structure with these properties, if you want to have a guarantee that the data structure will say "new" if it is really new (it'll never, ever say "not ...
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

### Is there a continuous hash?

For modern cryptographic hash functions, no, there is no efficiently computable closeness predicate, assuming the distribution on $x$ has sufficient entropy. The intuition is that these hash ...

### Why does this particular hashCode function help decrease collisions?

If the hashed codes are $x_1,\ldots,x_n$ (in that order), then the resulting hash value is $$x_n + 31 x_{n-1} + 31^2 x_{n-2} + \cdots + 31^{n-1} x_1 + 31^n \cdot 17 \pmod{2^{32}},$$ assuming ...
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

### Finding hash of a substring $[i, j]$ in $O(1)$ using $O(|S|)$ pre computation

Yes, you can solve your problem, roughly speaking, by precomputing prefix sums. In particular, if you are willing to do $O(n)$ precomputation and to use $O(n)$ space, we can solve your problem, for ...

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

The second function is easier to explain: it sends tract $t$ to position $t + h \pmod{n}$, where $h = hash(g)$. The function $t \mapsto t + h \pmod{n}$ is injective (one-to-one), and so every index $i$...

### Is there an anti-Bloom filter?

In the case where the universe of items is finite, then yes: just use a bloom filter that records which elements are out of the set, rather than in the set. (I.e., use a bloom filter that represents ...