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

Hot answers tagged

109 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 ...
user avatar
24 votes
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 ...
user avatar
14 votes
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 ...
user avatar
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 ...
user avatar
10 votes
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 ...
user avatar
  • 140k
9 votes
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/...
user avatar
  • 206
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 ...
user avatar
8 votes

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 ...
user avatar
  • 3,200
7 votes
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 ...
user avatar
7 votes
Accepted

Building static hash table with particular collisions

The easiest way is to construct a static hash table $T$ containing all the collisions, in the following form: for each set of keys $S$ which are supposed to map to the same value, single out some $x \...
user avatar
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 ...
user avatar
6 votes
Accepted

Why can the alphabet be represented in numbers in base 256

A number in base ten is just a sequence of digits 0–9, with the string $d_n\dots d_2 d_1 d_0$ representing the number $10^nd_n + \dots + 10^2d_2 + 10^1d_1 + 10^0d_0$. Similarly, a character in ...
user avatar
6 votes

Is there an anti-Bloom filter?

What about just a hash table? When you see a new item, check the hash table. If the item's spot is empty, return "new" and add the item. Otherwise, check to see if the item's spot is occupied by the ...
user avatar
  • 12.6k
6 votes
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 ...
user avatar
  • 140k
6 votes

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

Hash function calculates array position from given string. If this is perfect hash it means that there are for sure no collisions, the most probably array is at least twice bigger than number of ...
user avatar
  • 9,325
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'...
user avatar
  • 140k
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 ...
user avatar
  • 70.8k
5 votes
Accepted

Why does appending permutations of servers at the end of hash table avoid bottlenecks?

Adding permutations isn't about preventing slow servers from becoming bottlenecks, rather it's about dispersing a convoy once one forms behind a slow server. Because of the way tract locations are ...
user avatar
  • 7,833
5 votes
Accepted

What exactly is a hash function?

A hash function is a pseudorandom function with a constant range. Ideally, one would like two central properties: The hash function should be easy (fast) to compute. The probability that two inputs $...
user avatar
5 votes

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 ...
user avatar
  • 140k
5 votes

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 ...
user avatar
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{...
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.1k
4 votes
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 ...
user avatar
  • 140k
4 votes

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$...
user avatar
4 votes

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 ...
user avatar
4 votes
Accepted

Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$

You can reduce your $N \lceil \log_2 M \rceil$ bits to $\lceil N \log_2 M\rceil$ by using Dodis et al's "Changing Base without Losing Space". I don't think you're going to get much smaller than $N \...
user avatar
  • 3,200
4 votes

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

Since you have only 362,880 possible keys, you can uniquely represent every key with just 19 bits. (Where a really naïve representation of the key might take 9*4 = 36 bits). I can't see a way to ...
user avatar
4 votes
Accepted

Which fingerprinting/hashing algorithms support compounding?

This falls into a general class of hash functions known as homomorphic hash functions. Your question is not entirely clear about what definition you are using for $+$. If you want the hash function ...
user avatar
  • 140k
4 votes

Stateless pseudorandom/hash algorithm for ℤⁿ → [0,1)

Every hash function is stateless; that's part of the definition of what it means to be a hash function. A simple approach is to take a representation of the input in binary, using any standard ...
user avatar
  • 140k

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