Hot answers tagged

96

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 are multiples of $3$: Keys $\{0,12,24,36,...\}$ will be hashed to bucket $0$. Keys $\{3,15,27,39,...\}$ will be hashed to bucket $3$. Keys $\{6,18,30,42,...\}$ ...


24

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 entries, the hash function will return an integer in the range 0–9.


19

Whether a collision is less likely using primes depends on the distribution of your keys. If many of your keys have the form $a+k\cdot b$ and your hash function is $H(n)=n \bmod m$, then these keys go to a small subset of the buckets iff $b$ divides $n$. So you should minimize the number of such $b$, which can be achieved by choosing a prime. If on the ...


13

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 know the data that was encoded with it. It could be guessed by brute force and maybe some know attacks to the hash assuming the type/format of data is known, ...


12

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 be easily made negligibly small. Choose the parameters $n$ and $k$; practical values might be, say, $n = 128$ and $k = 16$. Let $H$ be a secure cryptographic ...


10

If I understand the question correctly, the answer is simple: if Hash(object) returns 27 when you call it this afternoon, we want Hash(object) to return 27 if we call it next week, on a different computer. If you use a random number generator in such a way that this is guaranteed, then go for it. Consider that a key use case for hash functions is ...


10

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 constructions for one-way permutations, e.g., based on raising to the third power modulo an RSA modulus or other schemes.


9

Whether this has an impact (also) depends on how you treat collisions. When using some variants of open hashing, using primes guarantees empty slots are found as long as the table is sufficiently empty. Try to show the following, for instance: Assume we want to insert an element that hashes to address $a$ and resolve collisions by trying positions $a + i^2$ ...


9

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/questions/5131497/find-the-index-of-a-given-permutation-in-the-sorted-list-of-the-permutations-of Once you have that index, you can make a table with exactly 9! ...


8

There are two sides to your coin: if you want to do it secure, you will need to use a cryptographically secure hash like SHA256 (crypto-hashes are meant to be fast, but tend to be a bit slow due to security constraints), things like CRCs are definitely quicker, but will never be able to offer the same kind of security (especially when we’re talking about . ...


8

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 new" if it is in fact new; no false negatives allowed). Any such data structure will need to keep all of the data to ever respond "not new". See pents90's ...


7

That's not a misprint. $kA \bmod 1$ makes sense. For instance, $37.239 \bmod 1 = 0.239$.


7

I think your reasoning is in principle correct. Perfect hashing is an alternative to Bloom filters. However, classical dynamic perfect hashing is rather a theoretical result than a practical solution. Cuckoo hashing is probably the more "reasonable" alternative. Note that both dynamic perfect hashing and standard cuckoo hashing performance is only expected ...


7

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 values in advance then you could indeed arrange that each cell would get exactly the same number of hits. Unfortunately, when you throw $n$ balls into $k$ bins, the ...


7

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 \in S$, and put all other $y \in S$ in the table with an entry stating "$x$". Now take a good hash function $h$, and construct a new one as follows: On input $...


7

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 the idea of one-way functions. A one-way function is a function that can be computed in polynomial time but whose inverse cannot be. It is well known that the ...


6

You can use Fibonacci hashing, namely $\qquad h_F(k) = k \cdot \frac{\sqrt{5} - 1}{2} - \left\lfloor k \cdot \frac{\sqrt{5} - 1}{2} \right\rfloor$. For $k=1,\dots,n$ you get $n$ pairwise-distinct numbers (about) evenly spread in $[0,1]$. By scaling to $[1..M]$ and rounding (down), you get about evenly spread numbers in that interval. For example, these ...


6

To expand Patrick87's comment and help you better understand the probabilistic counting algorithm : Linear Counting is used to get an approximate value of the number of distinct elements in a big set $S$ using a small amount of space. Suppose that you have a set of 1000 of names and you want to know how many distinct names are present in it. In the worst ...


6

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 item. If so, return "not new". If the spot is occupied by some other item, return "new" and overwrite the spot with the new item. You'll definitely always ...


6

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 an 8-bit character set can be considered to be a "digit" between 0 and 255, so a sequence $d_n\dots d_1d_0$ of these "digits" represents the number $256^...


6

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 independent basically means "it behaves like a perfect hash function, if you only feed it $k$ inputs" or "it behaves like a perfect hash function, as far as ...


6

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 elements. For example I will give very poor hash for letters, just to ilustrate mechanism: 0) $x = 0;$ 1) for each character in string take ascii value, subtract 'a'...


6

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's not good. A better method is to make the hash of $(a,b)$ be equal to $H(H(a) || H(b))$, where $H$ is your hash function on basic objects (ints, strings, etc.)...


6

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 array, that would have no meaning at all. Hence, this operation does not make sense on hashtables -- n/a. Which is of course underspecified or unfair, depending ...


5

The initial elements are chosen randomly to minimize hash collisions. You can think of the Zobrist hash as a random hash function $h$, mapping board positions to bit vectors of length $N$, chosen from some collection of hash functions. What we are trying to accomplish is this: given any choice of positions $p_1,\ldots,p_n$ arising in the program, we want ...


5

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 hashed, sequential reads of any blob always walk the tract locator table in the same order. Suppose you have six tract servers and your tract locator table looks ...


5

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 $x,y$ hash to the same value is roughly $2^{-n}$, where $n$ is the output length. The second property isn't stated rigorously. There are several ways to state ...


5

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 functions are designed to "have no structure", so they don't admit anything like this. In technical terms, modern cryptographic hash functions behave "like a random ...


5

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 int is 32 bits, and ignoring signed/unsigned distinctions. In view of this, the integers 17 and 31 should satisfy the following two properties: 17 should be non-zero. ...


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