Newest questions tagged hashing - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:45:29Z https://cs.stackexchange.com/feeds/tag?tagnames=hashing&sort=newest https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/112339 1 Linear probing and tabulation hashing rbtrht https://cs.stackexchange.com/users/19538 2019-07-31T13:18:11Z 2019-07-31T13:18:11Z <p>I'm currently reading the paper "The Power of Simple Tabulation Hashing" by Mihai Patrascu and Mikkel Thorup [<a href="https://arxiv.org/abs/1011.5200" rel="nofollow noreferrer">1</a>] because I want to adapt the proof of the constant time complexity of linear probing for modified tabulation hashing. I would like to ask a question about Corollary 11 (page 17). In this corollary is shown that <span class="math-container">$Pr[R \ge l] \le 2^{-\Omega(l\epsilon^2)} + (l/m)^\gamma$</span> for <span class="math-container">$\alpha \ge 1/2$</span> and <span class="math-container">$Pr[R \ge l] \le \alpha^{\Omega(l)} + (l/m)^\gamma$</span> for <span class="math-container">$\alpha \le 1/2$</span> when <span class="math-container">$\gamma = O(1)$</span> and <span class="math-container">$l \le n^{1/(3c)}/\alpha$</span>. Here R is the length of the run during linear probing and <span class="math-container">$c \ge 1$</span>.</p> <p>Then as I understand, we can prove that <span class="math-container">$E[R] = O(1/\epsilon^2)$</span> using the formula <span class="math-container">$E[X] = \sum_{l=1}^{n} Pr[X \ge l]$</span>. Could you please explain how do we apply the last formula if <span class="math-container">$l &gt; n^{1/(3c)}/\alpha$</span>? Intuitively, I understand that we have a tight concentration around <span class="math-container">$O(1/\epsilon^2)$</span> and, thus, the expectation is around it. But how do we take into account that <span class="math-container">$l$</span> can be greater than <span class="math-container">$n^{1/(3c)}/\alpha$</span> when showing that <span class="math-container">$E[R] = O(1/\epsilon^2)$</span>? Moreover, what if <span class="math-container">$1/\epsilon^2 &gt; n^{1/(3c)}/\alpha$</span>? Then how do we prove that <span class="math-container">$E[R] = O(1/\epsilon^2)$</span>?</p> <p>Thank you very much for you help.</p> https://cs.stackexchange.com/q/111219 1 Structure Preserving Continuous Hash Function Student https://cs.stackexchange.com/users/106993 2019-06-27T14:25:20Z 2019-06-27T14:25:20Z <p><em>This question was originally posted on <a href="https://superuser.com/">super user</a>, but redirected here based on some suggestions.</em></p> <p>I am completely new with computer science, and not only recently did I run into the notion of hashing. Currently, I use <code>md5sum</code> for indexing reason, but am curious if hash functions can do more things. After educating myself on the surface by reading the wikipedia page on <a href="https://en.wikipedia.org/wiki/Hash_function" rel="nofollow noreferrer">hash functions</a>, I wondered if continuous hash functions can be made true. Luckily, it is called <a href="https://en.wikipedia.org/wiki/Locality-sensitive_hashing" rel="nofollow noreferrer">locality sensitive hashing</a>, and I can find open algorithms online.</p> <p>What makes me more curious, and is something that I have not found, is can I further ask the continuous hash functions to preserve structure? More specifically, the problem I have in mind is to index all of the files I have. Not only do I hope the indexing to be continuous (so the hash won't change too much while I minor-edit a file), I also want it to preserve structure (so for example if I concatenate two files, the hash of the third file should be a reasonable function in the hash of the first two).</p> <p>Please let me know if I should provide more specific information. Again, I am completely new to this field, so I might have missed something obvious.</p> https://cs.stackexchange.com/q/110772 1 Simple Uniform Hashing Assumption and worst-case complexity for hash tables aioobe https://cs.stackexchange.com/users/21883 2019-06-16T22:20:43Z 2019-07-08T04:45:46Z <p><strong>My question:</strong> Is the <a href="https://en.wikipedia.org/wiki/SUHA_(computer_science)" rel="nofollow noreferrer">Simple Uniform Hashing Assumption</a> (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is <em>O</em>(1)?</p> <p>It says in the Wikipedia article that this assumption implies that the average length of a chain is <span class="math-container">$\alpha = n / m$</span>, but...</p> <ul> <li>...this is true even without this assumption, right? If the distribution is [4, 0, 0, 0] the average length is still 1.</li> <li>...this is a probabilistic statement, which is of little use when discussing <em>worst case</em> complexity, no?</li> </ul> <p>It seems to me like a different assumption would be needed. Something like:</p> <blockquote> <p>The difference between the largest and smallest bucket is bounded by a constant factor.</p> </blockquote> <p>Maybe this is this implied by SUHA? If so, I don't see how.</p> https://cs.stackexchange.com/q/110008 1 While computing signature matrix in min hashing, can I take nth row of the permutation P in which document d has value 1? A Beginner https://cs.stackexchange.com/users/105935 2019-05-29T12:26:05Z 2019-05-29T12:26:05Z <p>I am learning about some techniques to find similarity between documents. One of the methods is Min Hashing. According to Min Hashing we can find a signature matrix given a random permutation, P. According to this technique in order to calculate signature matrix, we have to take the index of the first row in which document d has value 1.</p> <p>Is it necessary to do that? If so, then can anyone please explain why? If not, can we take any nth row of boolean matrix permutation P? </p> https://cs.stackexchange.com/q/109916 0 Construction of hash function with a given distribution SomeoneHAHA https://cs.stackexchange.com/users/92568 2019-05-27T09:50:05Z 2019-05-27T13:24:51Z <p>Two questions about the construction of a hash function:<br> Let <span class="math-container">$U = \{u_1,...,u_n\}$</span> be a set of size <span class="math-container">$n$</span>, and suppose that one is interested in a function <span class="math-container">$h\colon U \rightarrow [0,1]$</span> such that <span class="math-container">$h$</span> "looks like" it maps each of the <span class="math-container">$u_i$</span>s to a random number, chosen from the uniform distribution on <span class="math-container">$[0,1]$</span>. One simple way to construct such <span class="math-container">$h$</span> is to store in the memory a table of size <span class="math-container">$n$</span>, and saving, for each element <span class="math-container">$u_i$</span>, the corresponding random sample. This is obviously very inefficient, and impossible to do if <span class="math-container">$U$</span> is infinite (or even continuous). Are there known approaches (or lower bounds) for the discrete, finite case? Are there approaches for the continuous case (i.e. <span class="math-container">$U$</span> is a continuous set)?<br> Clarification for the continues domain case:<br> Suppose that <span class="math-container">$U = \mathbb{R}$</span>. What I am after is a function <span class="math-container">$h : U \rightarrow [0,1]$</span> such that <span class="math-container">$h(u)$</span> has the property of "being random" i.e. if you sample many points from <span class="math-container">$\mathbb{R}$</span>, and look at <span class="math-container">$h(x_1),...,h(x_m)$</span> they would look like numbers which were sampled from uniform distribution </p> https://cs.stackexchange.com/q/109029 2 Given a family of hash functions in table form, how can I know whether it's universal? marianov https://cs.stackexchange.com/users/104917 2019-05-06T13:07:02Z 2019-06-04T11:30:39Z <p>I've been given the following two families of hash functions:</p> <p>H</p> <p><a href="https://i.stack.imgur.com/muWU7.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/muWU7.png" alt=""></a></p> <p>and </p> <p>G</p> <p><a href="https://i.stack.imgur.com/9zcWy.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/9zcWy.png" alt="enter image description here"></a></p> <p>Each family has three functions <span class="math-container">$\{0,1,2,3,4\} \to \{0,1,2\}$</span> that can be seen in the tables above. For each family I need to decide whether it's universal. I know that a family of hash functions <span class="math-container">$F$</span> is called universal if for every <span class="math-container">$x \neq y$</span>, <span class="math-container">$\text{Pr}(f(x) = f(y)) \le \frac{1}{m}$</span> (<span class="math-container">$f$</span> is a function in <span class="math-container">$F$</span>). However, I don't understand how to calculate this probability. Should I calculate it for any one of the functions or for the whole family?</p> https://cs.stackexchange.com/q/108925 0 is modulo of hash function is evenly distributed? nadavgam https://cs.stackexchange.com/users/48322 2019-05-04T03:14:17Z 2019-05-04T18:13:50Z <p>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?</p> <p>so if I have a histogram of values [0,N-1] will the histogram be evenly distributed ?</p> <p>Thanks</p> https://cs.stackexchange.com/q/108540 1 Check whether all elements are different uawff https://cs.stackexchange.com/users/104460 2019-04-25T21:10:25Z 2019-04-26T10:59:31Z <p>Assume we have <span class="math-container">$n$</span> double elements <span class="math-container">$a_1 \dots a_n$</span>. We want to find out if two of the elements of the array are identical. And we have a hash function <span class="math-container">$h(x)$</span> which assigns each double value an integer between <span class="math-container">$1$</span> and <span class="math-container">$n$</span> and which can be calculate in <span class="math-container">$O(1)$</span> time. Let <span class="math-container">$m := \{(i,j) : a_j \neq a_i \text{ and } h(a_j) = h(a_i)\}.$</span></p> <p>How can i check if all <span class="math-container">$n$</span> elements are different in <span class="math-container">$O(n+ |m|)$</span> time and <span class="math-container">$O(n)$</span> memory?</p> <p>1) The naive approach would be to check all <span class="math-container">$n$</span> elements if there is another element with the same value, which requires <span class="math-container">$O(n^2)$</span> time.</p> <p>2) A better way would be if i sort the elements, which needs <span class="math-container">$O(n \cdot \log(n))$</span> time and then check each adjacent pair of elements. In total it would be <span class="math-container">$O(n \cdot \log(n))$</span>. </p> <p>But i don't know how i can solve this problem quicker. I think neither approach 1) nor 2) can be further improved. Apparently I have to use the hash function somehow, but I don't see how. </p> https://cs.stackexchange.com/q/107314 3 The expectation of the total number of pairs of keys in a hash table that collide using universal hashing Snjór https://cs.stackexchange.com/users/101602 2019-04-21T12:53:23Z 2019-05-22T03:03:25Z <p>I am reading CLRS relating to perfect hashing. When computing the <span class="math-container">$$\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]$$</span></p> <p>where <span class="math-container">$m$</span> is the number of slots in the hash table, and <span class="math-container">$n_j$</span> is the number of keys in position <span class="math-container">$j$</span>. I don't understand why we can directly conclude that</p> <p><span class="math-container">$$\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]\leq{n\choose{2}}\frac{1}{m}$$</span></p> <p>I understand that since <span class="math-container">$h$</span> is randomly chosen from a universal hash function family, <span class="math-container">$\Pr{(h(x_i)=h(x_j))}\leq{\frac{1}{m}},\forall{i\neq{j}}$</span>. I don't understand why we can use the total number of pairs (the combination part) directly because if <span class="math-container">$h(x_i)=h(x_j)$</span> and <span class="math-container">$h(x_j)=h(x_k)$</span>, then we have <span class="math-container">$h(x_i)=h(x_k)$</span> immediately instead of a probability of <span class="math-container">$\frac{1}{m}$</span>.</p> <p>Someone can help me out? Thanks!</p> https://cs.stackexchange.com/q/105679 1 What are the k-collections described in ch. 8 of "An Introduction to the Analysis of Algorithms" by Sedgewick gnavarro https://cs.stackexchange.com/users/101692 2019-03-17T00:35:30Z 2019-03-17T19:28:12Z <p>In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425.</p> <p>My confusion is how to identify the k-collections. A k-collection is defined as: "<em>to be a word that consists of k different letters with the last letter in the word being the only time that letter occurs</em>" </p> <p>Exercise 8.6 of the book asks to find all the 2-collections and 3-collections in Table 8.1, where that table shows the configurations of 4 balls in 3 urns</p> <p>If I give it a try, I'd say a 3-collection from Table 8.1 is 2213, where the last letter (number 3) occurring just at the end, but I'm pretty sure I"m wrong.</p> <p>Can anybody help providing an example of a k-collection (2 or 3-collection) from Table 8.1? Thanks</p> https://cs.stackexchange.com/q/105306 0 Probability in 1-universal hash function user650708 https://cs.stackexchange.com/users/101361 2019-03-07T20:50:09Z 2019-03-07T20:50:09Z <p>I am trying to prepare for an exam and I am not sure how to solve this task: </p> <p>Given is a hash function with m buckets, which uses a 1-universal hash function h: U -> H and handles collisions with lists. The table was filled with n keys.</p> <p>1)Specify the probability that the first bucket in the table is empty.</p> <p>2) How should m be chosen as a function of n such that the expected total number of collisions is in O (1)?</p> <p>My idea:</p> <p>1) -probability that it lands in one bucket: 1/m</p> <p>-probability that it lands in a particular bucket: 1- 1/m</p> <p>-probability that after n inserts, the first bucket is empty: <span class="math-container">$(1-1/m)^n$</span></p> <p>2) <span class="math-container">$\Omega(n^2)$</span> </p> <p>Did I do that right?</p> https://cs.stackexchange.com/q/105155 0 Search operation in hash table user101252 https://cs.stackexchange.com/users/101252 2019-03-05T06:46:35Z 2019-03-05T06:46:35Z <p>Suppose that we have a hash table of some size <span class="math-container">$s$</span> and we have a set of keys <span class="math-container">$K$</span>. We decide to hash the keys using chaining.</p> <p>Now assume that we randomly select <span class="math-container">$k \in \mathbb{N}$</span> keys from <span class="math-container">$K$</span> and hash them. Next, we perform the search operation for one of those keys. </p> <p>My question is: is it true that this operation can take <span class="math-container">$O(k)$</span> time? Because, if we are very unlucky, it may happen that we hashed all keys to the same cell in the hash table, and then the key that we decide to search for is exactly the key that was hashed last?</p> https://cs.stackexchange.com/q/104431 3 Small space hash functions that are weakly but not strongly universal Anush https://cs.stackexchange.com/users/12510 2019-02-16T16:19:12Z 2019-02-16T18:37:47Z <p>This is a follow up to this <a href="https://cs.stackexchange.com/questions/104361/what-is-an-example-of-a-weakly-universal-hash-function-that-is-not-pairwise-inde">this question about weakly universal hash functions</a></p> <p>A family of hash functions <span class="math-container">$H_w$</span> is said to be <em>weakly universal</em> if for all <span class="math-container">$x \ne y$</span> :</p> <p><span class="math-container">$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$</span></p> <p>Here the function <span class="math-container">$h:U \rightarrow [m]$</span> is chosen uniformly from the family <span class="math-container">$H$</span> and we assume <span class="math-container">$|U| &gt; m$</span>.</p> <p>A family of hash functions <span class="math-container">$H_s$</span> is said to be <em>strongly universal</em> if for all <span class="math-container">$x \ne y$</span> and <span class="math-container">$k, \ell \in [m]$</span>:</p> <p><span class="math-container">$$P_{h \in H_s}(h(x) = k \land h(y) = \ell) = 1/m^2$$</span></p> <p>I previously asked for an example of a hash function family which is weakly universal but not strongly universal. The very nice answer was:</p> <blockquote> <p>Take <span class="math-container">$U = [m+1]$</span>, and consider the functions <span class="math-container">$h_i$</span>, for <span class="math-container">$i \in [m]$</span>, given by <span class="math-container">$$h_i(x) = \begin{cases} x &amp; \text{if } x \neq m+1, \\ i &amp; &gt; \text{if } x = m+1. \end{cases}$$</span> The same approach can be used for arbitrary <span class="math-container">$|U|$</span>: fix the first <span class="math-container">$m$</span> coordinates, and make all other coordinates uniformly and independently random.</p> </blockquote> <p>For arbitrary <span class="math-container">$|U|$</span>, it seems that in order to represent a single hash function in practice you would need to store a lookup table of size <span class="math-container">$|U|$</span> to ensure that the hashed values are independent and truly random. Then for every key, you would look up its random value in the vast lookup table to compute the hash function.</p> <p>Is there a hash function family where the hash functions require constant or log space that achieves the same result of being weakly but not strongly universal? In other words, are there any practical hash function families that are weakly not but strongly universal?</p> https://cs.stackexchange.com/q/103917 0 How minimal perfect hash functions are discovered / created Lance Pollard https://cs.stackexchange.com/users/9864 2019-02-06T04:54:48Z 2019-02-06T05:39:57Z <p>I have been looking at <a href="https://stackoverflow.com/questions/54546379/how-to-map-256-unique-strings-to-256-unique-but-effectively-arbitrary-integers?noredirect=1#comment95893337_54546379">How to create minimal perfect hash functions</a>, and come across resources such as these:</p> <ul> <li><a href="https://www.ics.uci.edu/~dan/pubs/omphf.pdf" rel="nofollow noreferrer"><em>Finding Succinct Ordered Minimal Perfect Hash Functions</em></a> <span class="math-container">$$h(x) = \Bigg[\sum_{j=0}^{m-1}g(h_j(x))\Bigg] \mod p$$</span></li> <li><a href="http://www.drdobbs.com/architecture-and-design/generating-perfect-hash-functions/184404506" rel="nofollow noreferrer"><em>Generating Perfect Hash Functions</em></a></li> <li><a href="https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf" rel="nofollow noreferrer"><em>Universal and Perfect Hashing</em></a> <blockquote> <p>In this method, we will instead view the key <span class="math-container">$x$</span> as a vector of integers <span class="math-container">$[x_1,x_2,\cdots ,x_k]$</span> with the only requirement being that each <span class="math-container">$x_i$</span> is in the range <span class="math-container">$\{0, 1,... ,M−1\}$</span>. For example, if we are hashing strings of length <span class="math-container">$k$</span>, then <span class="math-container">$x_i$</span> could be the <span class="math-container">$i^{th}$</span> character (assuming our table size is at least 256) or the ith pair of characters (assuming our table size is at least 65536). Furthermore, we will require our table size <span class="math-container">$M$</span> to be a prime number. To select a hash function <span class="math-container">$h$</span> we choose <span class="math-container">$k$</span> random numbers <span class="math-container">$r_1,r_2,\cdots,r_k$</span> from <span class="math-container">$\{0, 1,\cdots ,M-1\}$</span> and define:</p> <p><span class="math-container">$$h(x) = r_1x_1 + r_2x_2 + \dots + r_kx_k \mod M.$$</span></p> </blockquote></li> <li><a href="http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx" rel="nofollow noreferrer">jsw_tut_hashing</a></li> </ul> <p>Other resources are similar.</p> <p>What I don't understand is where this idea of using <span class="math-container">$\mod x$</span> came from, and how they know how to use the components of the hash function equations. That is, I don't see how they knew to use <span class="math-container">$r_1x_1$</span> or <span class="math-container">$\sum_{j=0}^{m-1}g(h_j(x))$</span> or other things. It seems like it just came from thin air. Wondering if one could explain generally how you go about constructing a minimal perfect hash function (not one like <a href="https://stackoverflow.com/questions/4130936/perfect-hash-function/4130965#4130965">this</a>).</p> <p>I'm wondering generally what the process is for coming up with a hash function, how they knew what tricks to use to figure it out.</p> <p>So like there is this <a href="http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx" rel="nofollow noreferrer">Bernstein Hash function</a>:</p> <pre><code>unsigned djb_hash(void *key, int len) { unsigned char *p = key; unsigned h = 0; int i; for (i = 0; i &lt; len; i++) { h = 33 * h + p[i]; } return h; } </code></pre> <p>It seems so arbitrary, I don't see how it got decided.</p> <p>Same with the FNV hash:</p> <pre><code>unsigned fnv_hash(void *key, int len) { unsigned char *p = key; unsigned h = 2166136261; int i; for (i = 0; i &lt; len; i++) { h = (h * 16777619) ^ p[i]; } return h; } </code></pre> <blockquote> <p>Designing a hash function is more trial and error with a touch of theory than any well defined procedure. For example, beyond making the connection between random numbers and the desirable random distribution of hash values, the better part of the design for my JSW hash involved playing around with constants to see what would work best.</p> <p>...</p> <p>The key here is that a hash function should never be used blindly without testing it, no matter how good the author says it is. Often, hash tests are designed around a hash function, and that introduces a bias in favor of that function.</p> </blockquote> <p>The main thing I wonder about is how they know they aren't going to get any collisions in a minimal perfect hash when designing it.</p> https://cs.stackexchange.com/q/102789 1 Ketama hash explanation Shobit https://cs.stackexchange.com/users/27738 2019-01-13T05:00:27Z 2019-01-14T07:45:23Z <p>(I originally posted this on stackoverflow but thought it would be a better fit here)</p> <p>I'm trying to understand the Ketama hash code used in consistent hashing.</p> <p><a href="https://github.com/RJ/ketama/blob/master/java_ketama/SockIOPool.java#L517-L532" rel="nofollow noreferrer">link</a> and snippet below:</p> <pre><code>public static Long md5HashingAlg(String key) { MessageDigest md5 = null; try { md5 = MessageDigest.getInstance("MD5"); } catch (NoSuchAlgorithmException e) { log.error("++++ no md5 algorythm found"); throw new IllegalStateException("++++ no md5 algorythm found"); } md5.reset(); md5.update(key.getBytes()); byte[] bKey = md5.digest(); long res = ((long) (bKey &amp; 0xFF) &lt;&lt; 24) | ((long) (bKey &amp; 0xFF) &lt;&lt; 16) | ((long) (bKey &amp; 0xFF) &lt;&lt; 8) | (long) (bKey &amp; 0xFF); return res; } </code></pre> <p>I think I understand what the code is doing, but I don't get why they're doing it. Particularly, I'm wondering why: </p> <ol> <li><p>the code discards the least significant 8 bytes of the 16-byte MD5 and uses only the first four (bKey through bKey). </p></li> <li><p>the code "flips" the significant bytes meaning that, of the 4 bytes from 1., the least significant now become the most significant (at least that's what I understand happens from the <code>&amp; 0xff</code>s and left shifts).</p></li> </ol> <p>I also came across another piece of code that uses the same logic as above, but in addition performs an <code>&amp; 0xffffffffL</code> on the result to "truncate to 32-bits". </p> <p><a href="https://github.com/dustin/java-memcached-client/blob/c232307ad8e0c7ccc926e495dd7d5aad2d713318/src/main/java/net/spy/memcached/DefaultHashAlgorithm.java#L138-L148" rel="nofollow noreferrer">link</a> and snippet:</p> <pre><code>case KETAMA_HASH: byte[] bKey = computeMd5(k); rv = ((long) (bKey &amp; 0xFF) &lt;&lt; 24) | ((long) (bKey &amp; 0xFF) &lt;&lt; 16) | ((long) (bKey &amp; 0xFF) &lt;&lt; 8) | (bKey &amp; 0xFF); break; default: assert false; } return rv &amp; 0xffffffffL; /* Truncate to 32-bits */ </code></pre> <p>Could someone help me understand the rationale behind picking these particular bytes and re-arranging them in this particular fashion?</p> https://cs.stackexchange.com/q/102731 1 additive hash function Tomasz Grobelny https://cs.stackexchange.com/users/30690 2019-01-11T21:59:17Z 2019-02-11T12:47:11Z <p>Do functions with the following properties exists for x being arbitrary stream of bytes:</p> <ol> <li>op(f(x1), f(x2))=f(x1+x2) and op(f(x1), f(x2))!=f(x2+x1) given that x1!=x2 where plus denotes concatenation and op is an easily computable operation</li> <li>f(x) is fixed length of about 160-512 bytes</li> <li>f does not need to be hard to revert, but should be useful at finding transmission errors or duplicates.</li> </ol> <p>Could you provide any names/articles/pointers?</p> https://cs.stackexchange.com/q/102227 0 Dynamic Perfect Hashing and Lower Bound Mohbenay https://cs.stackexchange.com/users/51341 2018-12-31T23:13:40Z 2018-12-31T23:13:40Z <p>I am writing a Seminar about dynamic perfect hashing and its lower bound by the <a href="https://en.wikipedia.org/wiki/Dynamic_perfect_hashing" rel="nofollow noreferrer">FKS</a> schema using the <a href="https://www.computer.org/csdl/proceedings/focs/1988/0877/00/021968.pdf" rel="nofollow noreferrer">the adversary method</a> mentioned here by using a Tree data structure. But somehow i don t get how the tree is build by the algorithm. What i mean exactly that he algorithm only generates 2 perfect hash functions but according the adversary strategy generates like many perfect hash functions at each node and leaves are the items inserted by the hash function.</p> <p>Can someone please help understand how the data structure is build while running the algo. thnx</p> https://cs.stackexchange.com/q/101561 1 Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents? Jeremy Friesner https://cs.stackexchange.com/users/47367 2018-12-15T04:47:10Z 2018-12-16T11:10:36Z <p>This question is about file-hashing/fingerprinting algorithms (similar to <code>SHA-1</code> and <code>MD5</code> and so on). Those algorithms are handy because they give you a small (and fixed-sized) hash code for any file, which can be later used to efficiently determine if that file is different from another file, and (if we are willing to ignore the unlikely possibility of hash-collisions) also whether two files are the same.</p> <p>One small downside to computing the hash/fingerprint for a file is that you have to read the entire file in order to do so; if the file is very large (e.g. gigabytes or more) this can be an expensive operation.</p> <p>A good way to avoid that expense is to compute the file's hash code as you are writing it to the disk, and store the hash code with the file. You can even resume updating the hash code later on, if/when you append more bytes to the end of the file, and (assuming no bugs or filesystem corruption) you'll have the file's fingerprint/hash cheaply available to you at all times.</p> <p>However, the above "update as you go" approach seems like it may break down if you want to update the file in other ways besides appending -- in particular, if you want to truncate the file, or overwrite some existing bytes within the file with new values, you might have to then re-read the entire file in order to update the fingerprint/hash to the appropriate new value.</p> <p>My question is, is there a type of hashing/fingerprinting algorithm that can efficiently handle file-truncation and byte-overwrite operations, and still provides reasonably good-quality hashing/fingerprinting? ("efficiently" in this case means that one could perform one of these operations on the file and then compute the correct new hash/fingerprint without having to re-read other parts of the file)</p> https://cs.stackexchange.com/q/100786 6 Can we remove duplicates faster than we can sort? einpoklum https://cs.stackexchange.com/users/11796 2018-11-30T23:42:09Z 2018-12-01T19:12:09Z <p>The problem is (integer) <strong>duplicate removal</strong>, which can also be perceived as producing the <strong>image of an evaluated function</strong> (of integers): </p> <blockquote> <p>Given a sequence <span class="math-container">$S_\text{in}$</span> of <span class="math-container">$n$</span> integers, produce a sequence <span class="math-container">$S_\text{out}$</span> of elements such that any element in <span class="math-container">$S_\text{in}$</span> also appears in <span class="math-container">$S_\text{out}$</span>, and all elements in <span class="math-container">$S_\text{out}$</span> are distinct.</p> </blockquote> <p>Ignoring some details regarding the elements' size in bits, this can be done by sorting in <span class="math-container">$O(n \log n)$</span> time; or by hashing in expected time <span class="math-container">$O(n)$</span>.</p> <p>Given that we don't require <span class="math-container">$S_\text{out}$</span> to be sorted - is it possible to do better than sorting in the worst case?</p> <p>Notes: </p> <ul> <li>Some dependence on the output size (let's call it <span class="math-container">$m$</span>) rather than <span class="math-container">$n$</span> is an improvement, but I'm mostly interested in getting closer to linearity in <span class="math-container">$n$</span>.</li> <li>The details I've ignored may not be so insignificant.</li> <li>Algorithms need not be restricted to algebraic computation, i.e. you can tear into the bit representation if it helps.</li> <li>We cannot make any assumptions regarding the input distribution.</li> </ul> https://cs.stackexchange.com/q/100591 2 Is there a way to theoretically compare hash functions? Mitchel Paulin https://cs.stackexchange.com/users/85219 2018-11-27T04:24:32Z 2018-11-27T08:00:13Z <p>Say I am given two hash functions <code>f1</code> and <code>f2</code> is there anyway that I can prove one hash function will produce fewer collisions than another one? That is say for some domain assuming all values in the domain are equally likely to be chosen can I show that <code>f1</code> will on average perform better than <code>f2</code>?</p> <p>Looking up how to determine if one hash is better than the other lead me to some interesting articles of how to compare cannabis but I couldn't find much else. </p> https://cs.stackexchange.com/q/99938 1 Prove hash family is 3-wise independent user2712414 https://cs.stackexchange.com/users/96270 2018-11-11T23:25:36Z 2018-11-11T23:37:28Z <p>Let <span class="math-container">$q$</span> be a prime number and let <span class="math-container">$\mathbb{Z}_q = \left\{1,\dots,q-1\right\}$</span>; I need to prove that the family <span class="math-container">$\mathcal{H} = \left\{h_s \colon \mathbb{Z}_q \rightarrow \mathbb{Z}_q\right\}_{s \in \mathbb{Z}_q^3}$</span> is 3-wise independent, where <span class="math-container">$h_s$</span> is defined as:</p> <p><span class="math-container">$$h_s(x):=h_{s_0,s_1,s_2}(x):=s_0 + s_1 x + s_2 x^2 \bmod q$$</span></p> <p>How could I do it? My intuition would be proving that it is 1-wise independent and use the property <span class="math-container">$$x_1,\dots,x_t \in \mathcal{X}, \quad y_1,\dots,y_t \in \mathcal{Y}, \quad \Pr[h_s(x_1)=y_1 \wedge \dots\wedge h_s(x_t)=y_t \mid s \leftarrow _\ \mathcal{S}]=\frac{1}{|\mathcal{Y}|^t},$$</span> but I'm not sure how to do that.</p> https://cs.stackexchange.com/q/99230 1 Why does Locality Sensitive Hashing use multiple sets of hash tables? How does it guarantee similarity? noname https://cs.stackexchange.com/users/95034 2018-10-29T00:37:12Z 2018-11-05T17:55:47Z <p>With locality sensitive hashing (specifically multi-probe hashing <a href="http://www.cs.princeton.edu/cass/papers/mplsh_vldb07.pdf" rel="nofollow noreferrer">http://www.cs.princeton.edu/cass/papers/mplsh_vldb07.pdf</a>) how are the guarantee of similarity returns made? Why are there multiple tables involved in the hash indexing? Wouldn't that make it LESS probable that an item hashed to a bucket is similar to another rather than the reverse?</p> https://cs.stackexchange.com/q/98637 1 Probability that a random hash from a universal family is injective Colin Null https://cs.stackexchange.com/users/95078 2018-10-15T22:22:01Z 2018-10-16T01:54:29Z <p>This is a homework question, I don't want an actual answer, but rather guidance on how to obtain the correct answer. The question is as follows: </p> <p>In class we saw universal hashing as the solution to processing N elements in the range {0,1,...u-1}, arriving one at a time. Using universal hashing we can get O(1) processing time for each request, but in expectation. Hence sometimes we might get unlucky and processing time might be longer. Consider another scenario where we are given the N requests in advance. Can we process them together and store in a hash table so that any future lookup request for any of these items can be processed in worst case O(1) time (so no uncertainty or expectation here)? In this problem you will design a solution for this, again using universal hashing.</p> <p>You are given a set S of N items in the range {0,1,...u-1) in advance. Consider the following algorithm that stores these items into a table of size N*N.</p> <pre><code>SquareHash(S, u) Input: A set S of N items, an integer u such that each item is in {0,1, ... , u-1} Output: A hash table of size N*N and a corresponding hash function 1. Initialize a table T of size N*N 2. While true 3. Pick a function h uniformly at random from a universal family H that maps {0,1, ... , u-1} to {0,1, ... , N*N-1} // Assume that this can be done in O(1) time 4. Insert all the elements of S into T using h as the hash function 5. If T has no collisions, return (T,h). Otherwise empty T </code></pre> <p>Clearly if the above algorithm terminates then it will produce a table with no collisions and hence any future lookup will be in O(1) time guaranteed. However in the worst case the algorithm might run forever. Show that this is unlikely. In particular, compute the expected running time of the algorithm above. [Hint: Each time a function h is picked, compute the probability (or a lower bound on it) that the resulting table will have no collisions. Then use the fact that if a coin of bias p is flipped until it turns up Heads, the expected number of flips is 1/p]</p> <p>I understand intuitively this is unlikely to run forever. If a hash function causes a collision, it will pick another one until it finds one that does not cause any collisions. However, I am unsure of how exactly to prove this formally and how to compute the expected running time. I know that the probability of two elements colliding is 1/m, where m is the expected range of outputs. </p> https://cs.stackexchange.com/q/98631 1 In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance? alehresmann https://cs.stackexchange.com/users/87345 2018-10-15T17:05:45Z 2018-10-15T19:43:44Z <p>In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for each hyperplane, the projection of the vector to be hashed onto the hyperplane's normal is used for hashing the vector. They highlight that to instead measure euclidean distance, one can involve the use of a value <span class="math-container">$a$</span> as a segment length, used to split all hyperplane normals into some number of <span class="math-container">$a$</span>-length segments. For each hyperplane, the segment into which the vector's projection falls into is used as its hash output. Hence the concatenation of this operation on each hyperplane generates a hash.</p> <p>Yet a number of implementations, including what seems to be one of the most authoritative (falconn), do not use segments at all, and instead simply do a binary output depending on which side of the hyperplane the projection falls into. Why is this ? Why are segments not used ? What does the cosine distance have over the euclidean distance ?</p> https://cs.stackexchange.com/q/98058 0 Do not understand a concept in analysis of open-address hashing eddard.stark https://cs.stackexchange.com/users/94477 2018-10-02T15:46:59Z 2018-10-02T16:13:33Z <p>I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor α=n/m&lt;1, the expected number of probes in an unsuccessful search is at most 1/(1−α), assuming uniform hashing.</p> <p>In the proof they are saying - </p> <p><span class="math-container">$p_i$</span> = It is the probability of <em>exactly</em> i probes where we are finding all of the slots to be occupied. i is 0,1,2,…</p> <p><span class="math-container">$q_i$</span> = It is the probability of <em>at least</em> i probes where we are finding all of the slots to be occupied. i is 0,1,2,…</p> <p>Then it says - </p> <p><span class="math-container">$$\sum_{i=0}^\infty i\,p_i\, = \sum_{i=1}^\infty q_i$$</span></p> <p>How it is so?</p> https://cs.stackexchange.com/q/98055 0 How is this the expected number of of probes in open-address hashing? eddard.stark https://cs.stackexchange.com/users/94477 2018-10-02T14:43:14Z 2018-10-02T15:34:51Z <p>I am reading the "Introduction to Algorithms" by Thomas Cormen <em>et al</em>. Particularly the theorem which says that given an open-address hash table with load factor <span class="math-container">$\alpha = n/m &lt; 1$</span>, the expected number of probes in an unsuccessful search is at most <span class="math-container">$1/(1-\alpha)$</span>, assuming uniform hashing.</p> <p>In the proof they are assuming <span class="math-container">$p(i)$</span> to be the probability of exactly <span class="math-container">$i$</span> probes where we are finding all of the slots to be occupied. <span class="math-container">$i$</span> is <span class="math-container">$0,1,2,\dots$</span> so for <span class="math-container">$i &gt; n$</span> we have <span class="math-container">$p(i) = 0$</span> since we can find <span class="math-container">$n$</span> slots already occupied. I have understood upto this point.</p> <p>Then it says that expected number of probes in an unsuccessful search is <span class="math-container">$$1 + \sum_{i=0}^\infty i\,p(i)\,.$$</span> How is it so?</p> <p>If there is any confusion to the question please comment. I hope I have explained the question properly. Any help would be appreciated. Thanks in advance.</p> https://cs.stackexchange.com/q/97239 0 Does this excerpt from the linear probing Wikipedia page make an assumption? Jeffrey K.A https://cs.stackexchange.com/users/93260 2018-09-12T10:58:36Z 2019-04-10T22:01:25Z <p>Here is the excerpt from <a href="https://en.wikipedia.org/wiki/Linear_probing#Search" rel="nofollow noreferrer">the linear probing page at Wikipedia</a>.</p> <blockquote> <p><em>To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and continuing to the adjacent cells h(x) + 1, h(x) + 2, ..., until finding either an empty cell or a cell whose stored key is x. If a cell containing the key is found, the search returns the value from that cell. <strong>Otherwise, if an empty cell is found, the key cannot be in the table, because it would have been placed in that cell in preference to any later cell that has not yet been searched. In this case, the search returns as its result that the key is not present in the dictionary</strong>.</em></p> </blockquote> <p>Does this assume that the linear probing function let's say P(x) is the same for insertion and searching? Must your linear probing function be consistent throughout the hash table? Is there a combination of linear probing functions that work best together?</p> https://cs.stackexchange.com/q/93662 0 Hashing routine explanation [duplicate] hal https://cs.stackexchange.com/users/90126 2018-06-29T19:41:06Z 2018-06-29T19:41:06Z <div class="question-status question-originals-of-duplicate"> <p>This question already has an answer here:</p> <ul> <li> <a href="/questions/55471/what-exactly-and-precisely-is-hash" dir="ltr">What exactly (and precisely) is &ldquo;hash?&rdquo;</a> <span class="question-originals-answer-count"> 5 answers </span> </li> </ul> </div> <p>As the title states, I would like to know what a hashing routine is. I found online about hashing algorithms but I heard it, being used in a different context. </p> https://cs.stackexchange.com/q/93138 0 Proof of expected number of probes in an unsuccessful search (open addressing hashing) Smartens https://cs.stackexchange.com/users/89544 2018-06-15T21:52:30Z 2018-06-15T21:52:30Z <p>I'm seeking some clarification on the proof of the expected number of probes in an unsuccessful search in open addressing hashing. The proof is given in CLRS on page 275, section 11.4 (Open addressing).</p> <p>Specifically, why is the higher bound of an expectation (of unsuccessful probes) in search is $\infty$? What is the rational behind this?</p> <p>$E[X] = \sum_{i=1}^{\infty} Pr\{X \geq i \}$ $(1)$ p. 275 CLRS</p> <p>My understanding is that the maximum possible amount of probes in the worst case scenario is $n$. So, the expectation in this case is </p> <p>$E[X] = \sum_{i=1}^{n} Pr\{X \geq i \}$ $(2)$</p> <p>where n is the number of elements in a table of size m. </p> <p>Of course, we can assume that $n \rightarrow \infty$, then $(1)$ makes sense. However, <strong>open addressing hashing is not recommended for large data sets</strong>. So, these two concepts contradict each other.</p> https://cs.stackexchange.com/q/91050 1 Generate numeric or string ID for a sequence of elements gneric https://cs.stackexchange.com/users/76368 2018-04-23T07:14:45Z 2018-04-23T15:16:04Z <p>How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter.</p> <p>Example:<br> <code>[41,1001,32]</code> should generate the same ID as <code>[32,1001,41]</code><br> <code>[41,1001,32, 5]</code> should be different. </p> <p>Elements could be hundreds where each individual ID can be a 4/5-digit number. </p> <p>I thought about sorting, concatenate and Hash/Compress the string, but are there gonna be a lot of collisions ?</p> <p>Any ideas would be much appreciated.</p>