What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Tag Info

85

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.

18

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

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 In fact, there's an argument to be made that the 'range' of CRC-style hashes is not the integers (or naturals), but is in fact the field of polynomials over GF(2) modulo a primitive polynomial of degree$n$(i.e., the field GF$(2^n)$). All of the operations are done on$n$-bit entities, but those entities are only 'numbers' in so much as that's 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 Range of any hash function is a sub-set of natural numbers (this is how we think of it, exactly for access to the arrays, that could lie behind). The actual output of common hash-functions (MD5, SHAX...) is$n$bits, where$n$is$128$for MD5 and$512$for SHA2 with 80 rounds. These bits can then be interpreted as natural numbers from interval$[0, 2^n-1]$... 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 That's not a misprint.$kA \bmod 1$makes sense. For instance,$37.239 \bmod 1 = 0.239$. 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

Generally the collisions in a hash function are, in a way, what winds up improving the running time. This is because running time (or size, or insertion time) is generally defined in terms of worst-case input. If you use an algorithm without any randomness or hash, you need to deal with the worst case. For example, finding duplicate elements in an array ...

5

Just to complete Yuval's answer, there are plenty of collisions if you pick the first 9 digits of the MD5. For example: md5('40236') = f46657d67 3d95ccf8d12b1075ab7c653 md5('400704') = f46657d67 e7a3de02f64013bfcbd932c Let $m = 2^{36}$ (nine hex digits), $n = 2^{24}$ (three bytes for an UNSIGNED MEDIUMINT); assuming that MD5 is a good hash :), the ...

5

You are right: universal hashing suffices. Pairwise independence, while stronger, is the usual method to construct a universal hash family. Also pairwise independence is contrasted in the paper with the 4-wise independence required by previous methods, such as the AMS sketch.

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