Hot answers tagged

44

The Wikipedia article on hash functions is very good, but I will here give my take. What is a hash? "Hash" is really a broad term with different formal meanings in different contexts. There is not a single perfect answer to your question. I will explain the general underlying concept and mention some of the most common usages of the term. A "hash" is ...


10

A hash function is a function that takes an input and produces a value of fixed size. For example you might have a hash function stringHash that accepts a string of any length and produces a 32-bit integer. Typically it is correct to say that the output of a hash function is a hash (aslo known as a hash value or a hash sum). However, sometimes people refer ...


6

It is a classical result that the element distinctness problem requires $\Omega(n\log n)$ comparisons in the comparison model (the one used to analyze sorting algorithms); in fact, it also requires $\Omega(n\log n)$ time in stronger models such as algebraic decision trees, in which we are allowed to compute the sign of arbitrary bounded degree polynomials (...


5

An easy way to visualize this is to imagine a hash table of size $n$ (implemented with chaining) that contains all of the elements of $U$ (even though this is unrealistic in practice because $U$ typically has massive size). Since $|U| >> n$, all of the elements of $U$ do not fit into the hash table; therefore, there will be collisions. Consider, for ...


5

The load factor denotes the average expected length of a chain, therefore it is interesting for an average case analysis, not the worst case analysis. That's why on average you expect needing constant time for search operations. In the worst case however, all your elements hash to the same location and are part of one long chain of size n. Then, it depends ...


5

Yes, this is possible. Here are two examples of such a function. One function is $f(x)=x$. This has no collisions, and the function is easy to invert. Here is another function: define $f(x) = x$ if $x$ is 256 bits long, otherwise $f(x) = \operatorname{SHA256}(x)$. Then it is very hard to find collisions for $f$ (since SHA256 is collision-resistant). ...


4

Uniformity is about potential values, while randomness is about actual values. For example, suppose you make a very simple hash function that takes the first byte of a string, resulting in 256 buckets. It is uniform, because the number of possible strings starting with a particular byte doesn't depend on. But it is not random for most data sets: at least 12....


4

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


4

If for all $|r - s| < 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise). What you are asking is impossible. One thing which is possible is to compare keys with three rather than two possible outcomes: If $K(r)$ is close to $K(s)$ then $|r - s| < 1$. If $K(r)$ is far from $K(s)$ then $|r - s| \geq 1$. Otherwise, we don't know. Of ...


4

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 FNV_PRIME modulo $2^{32}$. The original version (operating on bytes) does this once for each byte of the input. The alternative version (operating on integers) does this once for each integer, i.e., ...


4

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 that maps $h:\mathbb{R}^n \to S$ where if $x,y \in \mathbb{R}^n$ are close enough, then we'll have $h(x)=h(y)$ with high probability. To get started, tead https:...


4

Assume there is no such bucket. Then each bucket has at most $|U|/n - 1$ items. There are $n$ buckets, so the total number of items is at most $n*(|U|/n - 1) = |U| - n$. This is less than $|U|$, which is the number of items we distributed to the buckets in the first place. This is a contradiction, so we proved that the statement "each bucket has at most $|U|/...


4

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 for the event "$i$ is empty". Then $$p_0 + \cdots + p_{M-1} = \mathbb{E}[X_0] + \cdots + \mathbb{E}[X_{M-1}] = \mathbb{E}[X_0 + \cdots + X_{M-1}], $$ using ...


3

No. The statement you're reading is correct. Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens. The set of points $v$ such that $v \cdot r = 0$ is a line; the set of points $v$ such that $v \cdot r \ge 0$ is a half-plane (e.g., the half-plane above that line).


3

I think you've missed the point of hash tables. Hash tables are used to give array-like access to a dataset that's too big and sparse to store in an array. So, for example, it sounds like you're trying to store a mapping of UIDs to usernames or something like that. The naive way of doing that would be to just have an array with one entry for each possible ...


3

A hash function cannot avoid collisions when the size $M$ of the hash table is smaller than the size of the universal set $U$ that you are hashing. This is a consequence of the compression step. In your case, $U$ is the set of UIDs. Since $|U|=1000000$ and $M= 524309$, then $M < |U|$ and, therefore, collisions will inevitably occur (see Pigeonhole ...


3

A hash table usually uses two different things: One, a hash function that maps an item to a hash code (with the requirement that equal items are mapped to equal hash codes), and two, a function that maps hash codes to locations in the hash table where the item would be stored. Hashing every UID to a different 32 bit hash code is trivial - just hash every ...


3

The mean chain length is the sum of the chain lengths divided by the number of chains. The sum of the chain lengths is, by definition $n$ and the number of chains is $m$. This is by far the easiest way to calculate it, and it's true even if the SUHA doesn't hold. But since you asked, let's look at the distribution of the chain lengths. Suppose you're ...


3

There is a deterministic algorithm for constructing a perfect hash, if you don't care about efficiency. For instance, you can enumerate all programs (in order of increasing size) and test each one to see which is the first that produces a valid perfect hash. This is a valid deterministic algorithm that is guaranteed to always find a valid perfect hash (and ...


3

This is explained in Wikipedia. Given $n,m$, the false positive probability is $$ \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k. $$ This is the quantity we want to minimize. While the exact expression is hard to minimize exactly, we can use the approximation $$ \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k \approx (1-e^{-kn/m})^k, $$ which is ...


3

You will first need to define what you mean by a hashing algorithm. For example, my favorite hashing algorithm is simple: check whether the input is "string", and if so, output "b45cffe084dd3d20d928bee85e7b0f21", otherwise output "error". In the simplest case, you have one algorithm $A$, and string $w$ and you are wondering, is there an input $x$ (and maybe ...


3

No it is not possible to determine that is produced by a hashing algo, or which one that produced it -- at least not from a single sample. Good hashing algo will produce a uniform set of values across the entire range of possible values -- where modern algo produces values from 128 to 512 bit in width, but if we take it back to a simpler example that may be ...


3

I think that the notes have been reported incorrectly. Indeed CruiskeenLawn, you are right. I've found some very old notes here which report the correct result. Indeed, in your copy, they simply forgot to add $\left[\begin{matrix} t\\ t\end{matrix}\right]$ term. The Lemma you are looking for is on Page 2.


3

There are many measures of similarity between sequences (or arrays or even strings), which one to use depends on the specific goals for the similarity. It may be the case that some trial and error is required to find the 'best' one. Therefore, I'll give a brief overview of some well-known similarity measures: First, I consider distances most commonly ...


3

Let $H$ be a family of strongly universal hash functions from $U$ to $[m]$. Construct a new family of hash functions from $U \cup \{x\} \to [m]$ by extending all functions $h \in H$ with $h(x) = 1$. The family is weakly universal since $h(u)$ is distributed uniformly for every $u \in U$, but it is clearly not strongly universal.


3

if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed? It depends on the hash function. For a good hash function the output should be uniformly distributed. so if I have a histogram of values [0,N-1] will the histogram be evenly distributed ? For any reasonable ...


2

As others have said, what you want is impossible. But you might want to look at locality-sensitive hashing. It achieves something vaguely similar: if two elements are similar, then with significant probability they will have the same hash. It is possible to amplify the probability by hashing with multiple independent hash functions. With high probability,...


2

The second variant isn't much better: $\forall s,r: |r-s| < 1 \Rightarrow K(r) = L(s)$ implies that $\forall r: K(r) = L(r)$, as $r = s$ is only a special case. On the other hand, you are down to two comparisons: $K(x) := \lfloor 0.5\cdot r + 0.5 \rfloor \\ L(s) := \lfloor 0.5\cdot s \rfloor \\ \forall r,s: |r-s|<1 \Rightarrow K(r) = L(s) \lor K(r) = ...


2

This has nothing to do with any property of the hash function. Rather, $$\mathbb{E}[n_j] = \frac{1}{m} \sum_{j=1}^m n_j = \frac{1}{m} \cdot n = \frac{n}{m}.$$ (This is under the assumption that by $\mathbb{E}[n_j]$ you mean the expectation of $n_j$ over uniformly chosen $j$.)


2

Yes, the root has a higher probability of collision. Take, for example, simple trees with two leaves. Label tree 1's leaves $A$ and $B$, and tree 2's leaves $X$ and $Y$. The probability that the tree hashes collide at the root is the probability that $\langle h(A),h(B) \rangle \neq \langle h(X),h(Y)\rangle \land h(h(A)||h(B)) = h(h(X)||h(Y))$ plus the ...


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