Hot answers tagged

4

There are $2^n$ many $n$-bit strings, but only polynomially many strings of length $O(\log n)$.


3

$\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$ Denote the support of $f$ by $f_1\le f_2\le...\le f_s$. Given a frequency sequence $f$, denote by $E_{f,a}$ the random variable $\hat{f}_a$ where the stream frequencies are given by $f$ (the evaluation depends on the inner randomness of the sketch and the input stream). The probability that the hash of one ...


2

One example is consistent hashing. The usual scenario used for motivation is assigning files to servers. To avoid having too many files associated with a single server, you map $n$ files to $m$ servers via some hash function $h:[n]\rightarrow[m]$. Suupose you add a new server or that an existing server crashes, then you would have to rehash all the files to ...


2

A bit late to the party, but the second approach can be useful to simplify the merkle-path. When hashing a pair, it's required to know if the leaf is on the left or right side of the pair. This can become quite complex, for example, when implementing multi-leaf inclusion proofs. By sorting the pairs before hashing, it doesn't matter which side the leaf ...


2

Assume you have a good hash function producing an n bit hash code, that is $2^n$ possible values. Assume you are hashing k values, so there are about $k^2/2$ pairs of hash codes that might collide. The probability of a collision is about $k^2 / 2^{n+1}$. By picking a large n, you can make that probability arbitrarily small. Ask a physicist to calculate the ...


2

Let $A_n\subseteq \{0,1\}^{\log n}$ denote the set of binary strings of length $\log n$ with at least $c\log n$ trailing zeros on the right (here I assume that $\log n$ in an integer and $0\le c\le 1$). Note that $|A_n|=2^{\log n -\lceil c\log n\rceil}\le 2^{(1-c)\log n}$. Since $H:\{0,1\}^{\log n}\rightarrow \{0,1\}^{\log n}$ is a one to one function, $\Pr_{...


2

Let us first look at the total number of hash functions in $H$. Since each key can be mapped to $m$ different indexes and there $n$ different keys. We get: \begin{align} |H| = m^{n} \end{align} Now, without loss of generality, let us consider the first two keys $x = k_{1}$ and $y = k_{2}$. We will compute the number of hash functions where $x$ and $y$ will ...


2

Here is one simple idea -- not sure if it's practical. Define $\mathsf{sketch}_n(X)$ to be a length-$n$ bitstring in which bit $i$ is set iff there exists $x \in X$ such that $x = i \mod n$. In practice, this means that inserting an element $x$ into a set involves turning on bit $x \mod n$. $\mathsf{disjoint}_n(\cdot)$ is defined as before. Then $\mathsf{...


2

Originally, the hash function was defined as follows: Input: a 64-bit unsigned integer $x$. Calculate $(9E3779B185EBCB87)_{16} \cdot x = 2^{64} x_h + x_l$, where $x_l,x_h$ are 64-bit unsigned integers. Output $x_l \oplus \lfloor (x_h + 2x_l)/8 \rfloor$. Under this definition, there is a collision: both $(2DCE4F983BBEB685)_{16}$ and $(72E04DBED1540FE1)_{16}$...


2

The term first described by Horst Feistel (1973) As the input moves through successive layers the pattern of 1's generated is amplified and results in an unpredictable avalanche. It is rather very good naming. Consider a bit flip in the AES's input; It enters the first Sbox, then according to the design of the Sboxes of AES the output is different since ...


2

Any such hash function must have an infinite key. Suppose that your hash function maps binary strings to some alphabet $\Sigma$ of size $m > 1$. We can identify binary strings with natural numbers, and so can think of the hash function as a function $h\colon K \times \mathbb{N} \to \Sigma$, where $K$ is the (finite) set of keys. For each $n \in \mathbb{N}$...


2

Ami Tavory, Vladimir Dreizin (IBM), and Benjamin Kosnik (Red Hat) authored the "Policy-Based Data Structures" library. Ideas developed there were later used in the GNU implementation of the C++ standard library. Link-only answers are typically discouraged, but let me post the link here anyway because it is not discoverable with Google in a simple ...


1

I think this is a reasonable approach. To make it more solid, I suggest replacing Murmur3 with a cryptographic hash, such as SHA256. Then we get a kind of guarantee: it is believed to be intractable to find a collision for the hash function. In other words, for all engineering purposes, we expect you will never in your lifetime encounter a pair of inputs ...


1

Can you give me a hint on how to prove this? Let $H$ be a class of all functions which map universe $Z_n$ to $Z_m$. We will assume that, any particular mapping is done by exactly one of the functions in the class. Total functions in $H$ = number of all possible mappings = $m^n$ Given any distinct keys $x$ and $y$, we need to find number of all possible ...


1

The output of the function can always be expressed as a 256-bit value. The value 5 is expressed as 00000...000101 (some 0's omitted).


1

Throughout, we assume that $|D| \geq k$. Suppose that $H$ satisfies, for all distinct $x_1,\dots,x_k \in D$ and all $y_1,\ldots,y_k \in R$, $$ \Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k}. $$ Now let $x \in D$ be arbitrary. Since $|D| \geq k$, we can find $x_2,\ldots,x_k \in D$ such that $x,x_2,\ldots,x_k$ are distinct. For each $y \in R$, $$...


1

If you use bijective hash functions, you can recover the original keys from filter structures like cuckoo filters or quotient filters. The reason is that these are essentially quotienting dictionaries, not just filters. The problem, of course, is that the values in the sketch have to come from a universe as large as your input - otherwise you must not have a ...


1

Yes. Use any linear function as your hash function. If $h(x)= \alpha x + \beta \bmod n$, where $\alpha,\beta$ are fixed constants, then $$h(x+\delta) = h(x) + \alpha \delta \bmod n.$$ Consequently, $\mathsf{shift}$ can just rotate the bitstring right by $\alpha \delta$ positions. Note that if $n$ is prime this hash function is 2-universal, so it should be ...


1

Suppose that $t=11$, $i=5$, $j=6$. Then $i+j \bmod t = 0$, and there is no contradiction. However, in this example $i < t/2$ while $j > t/2$. This sort of example cannot happen if $i,j < t/2$, since then $i+j < t$.


1

Because two sequences with the same acids in different order (e.g. two acids switch places) will have the same hash code; this will only produce numbers from 0 to your large simple modulus instead of all $2^{32}$ or $2^{64}$ possibilities.


1

When you say "store", I suppose you're also expecting to be able to retrieve the original string based on the shorter string, right? If so, then the answer is a categorical no. And not only to log(n), but even to n-1. Theorem: it is not possible to construct a program that reversibly converts all possible strings of length n to strings of length m, ...


1

No hash function can guarantee a good distribution. All you can do is finding a hash function that will usually create a good distribution. The table size is quite important for this: If the table size is a prime p, then just using n modulo p as the hash value is usually quite good. Note that in your case, 4 is not a prime. Actually all your values are ...


1

Assume you have strings that you hash to a 64 bit hashcode. Since the number of possible strings is unlimited, it is guaranteed possible to have n strings that all have the same hashcode. Think about what your hashtable will do in that case.


1

What do you mean by "collision", and what does your professor mean? If you try to insert a key into a hash table, the usual case should be that there is no key with the same hash in the table yet. In that case, no collision, and you insert the key. If there is a key with the same hash already there, I would say that either the same key is already ...


1

Think of the hash function as a box with input and output values. Here, the number of possible output values is fixed to 10 (because of the mod10). Hence, uniformity depends on the input and the function. Our input is uniform in this case(whole numbers). But the functions seem to mess up this uniformity(or variability). We'll choose the one which preserves ...


1

The first method is the standard one that I've seen. I'm not clear on what the purpose of the second method would be, or even exactly how it works. It's not something I've seen before. I'd suggest you use the first method by default, and if you encounter a situation where it is insufficient or has some problems, post a question asking about the specific ...


1

We want to show that if $k_1\neq k_2\in\mathbb{Z}_p$ then $\Pr\limits_{(a,b)\in\mathbb{Z}_p^*\times\mathbb{Z}_p}[ak_1+b\equiv ak_2+b \pmod m]\le\frac{1}{m}$. Where both addition and multiplication are preformed in $\mathbb{Z}_p$. We start by showing that if $a\sim U(Z_p^*)$ and $b\sim U(Z_p)$ then for all $k_1\neq k_2\in \mathbb{Z}_p$, $(ak_1+b,ak_2+b)$ is ...


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