New answers tagged

0

In the second paragraph: "In other words, with a hash function randomly chosen from $\mathscr{H}$, the chance of a collision between distinct keys $k$ and $l$ is no more than the chance $1/m$ of a collision if $h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$." Here, "the chance of a collision between ...


0

Both definitions are equivalent, and I think you have almost specified the reason behind it. The below equivalence work in both ways. From Definition 2: "the chance of a collision between distinct keys $k$ and $l$" $\le$ $1/m$ $\Leftrightarrow$ {note that the "chance" here is about the process of picking $h$ from the class $\mathscr{H}$} (...


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


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


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


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


0

Probing doesn’t find an empty slot if all probed slots are full. If less than half the slots are full, and half the slots or more are probed, then you are probing more than the full slots, so the probed slots cannot all be full.


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


Top 50 recent answers are included