Questions tagged [hash]

Mathematical function that maps arbitrarily-sized data to fixed-size integers, often used as keys in hash tables or to help ensure data integrity

69 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
887 views

Double Hashing and Variations for Bloom Filters

I am reading a few papers on Bloom Filters – Bloom Filters in Probabilistic Verification (Dillinger and Manolios) suggests the following allocations for double and triple hashing respectively ...
4
votes
0answers
392 views

Mean and variance of number of buckets of length $i$ in hashing with chaining

Consider a hash table with $m$ buckets, with chaining as collision resolution policy. Given the set $S$ that will be stored in the hash table, let $X_i$ be the number of buckets whose chain length is $...
4
votes
1answer
552 views

How to find a 2-wise independent hash family that is not 3-wise independent?

I'm trying to find a family of hash functions mapping $\{1, 2, ..., 2^n\}$ to $\{0, 1\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that? I know two 2-wise independent ...
3
votes
1answer
91 views

How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?

Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental ...
3
votes
0answers
32 views

String to small integer mapping without collision

Is there any good approach to devise a mapping of limited number of strings $N_1 << 2^{15}$ to integers less than $2^{15}$ without conflicts? Strings are quite often of the form of prefix + ...
3
votes
0answers
247 views

Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?

Calculating hashes for nodes in an acyclic graph is well known using a Merkle tree. With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a cyclic graph... but ...
3
votes
0answers
511 views

Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...
3
votes
0answers
112 views

Algorithm that hashes a collection of sets following their disjointness relation

I wonder whether there is a simple algorithm to do this work: Say I have a collection of objects $C$, and a binary relation $R: C\times C$ that is auto-reflective ($\forall c\in C: c R c$) , and ...
2
votes
0answers
55 views

Proving that a successful search of hash function is $\Theta(1+\alpha)$

Question: Prove that successful search of hash function with chaining (list at each slot) takes $\Theta(1+\alpha)$. Given a dictionary or hash table that has a chain at each slot in case we have a ...
2
votes
0answers
18 views

Does there exist a locality sensitive hashing for $\ell_p$-norm distance where $p>2$?

It is well known that the $p$-stable distribution can be used to generate locality sensitive hash code for $\ell_p$-norm distance measure where $p \le 2$. However, it seems that the situation for $p&...
2
votes
0answers
30 views

Finding the longest power subsequence

A power sequence is a sequence containing consecutive powers of a number starting from power one. for example $3^1, 3^2, 3^3$ is a power sequence. The question is to find the length of the longest ...
2
votes
0answers
56 views

In Universal Hashing- probability of poor performance is small and is the same for any set of keys of the same size

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following claim: Universal Hashing uses randomization.For the example of a compiler's symbol table, ...
2
votes
0answers
120 views

Approximate dot product between neural network output layer's parameter vector and input activations with winner-take-all hashing

In the paper Deep Networks with Large Output Spaces, Vijayanarasimhan et al. describe their approach to approximating the dot product between a neural network's output layer's parameter vector and ...
2
votes
0answers
38 views

Altering the size of a Hash

Does removing the leading(or trailing) n bits of any given hash have any negative effects other then increasing the likeliness of collisions? Does appending 2 hashes of the same object with different ...
2
votes
0answers
612 views

Distance preserving projection for Euclidean distance

Suppose I have two vectors $V_1, V_2 \in R^l$. Can they be converted into bit vectors $B_1,B_2 \in \{0,1\}^l $ such that if $V_1, V_2$ is close in Euclidean distance, $B_1,B_2$ is close in hamming ...
2
votes
0answers
99 views

Collisions of a compression function

I tried posting this in the math forum but I didn't get any responses. I was hoping someone could give me some advice for how to approach the following problem. If $n$ is a positive integer, let $...
1
vote
0answers
41 views

Finding a full collision within a large array

I apologize for the vagueness of the title, but this question is quite difficult for me to describe. For that reason, I'm unable to directly convey my problem. In an effort to circumvent this, I've ...
1
vote
0answers
25 views

Average-case retrieval time

The book CLRS claims these statements before introducing the topic of universal hashing: If a malicious adversary chooses the keys to be hashed by some fixed hash function, then the adversary can ...
1
vote
0answers
31 views

Is there a standard name for this property of hash functions?

A hash function $H$ operating on strings can have the following property: Let $x$ be a string and $c$ a character. Given $H(x \cdot c)$ and $c$, $H(x)$ can be determined uniquely (where $\cdot$ stands ...
1
vote
0answers
73 views

Pairwise independent hash function family?

I am looking for a family of pairwise independent hash functions $\mathcal{H} = \{h \mid h:[n]\rightarrow [m]\}$ that is easily computable. As an example that doesn't seem to work, choose a prime $p &...
1
vote
2answers
401 views

Double Hashing with Strings as key

How would you choose the second hash function with for double hashing with string as key? My first hash function is the scalar product of a random int array with the 16 bit number of each char. Is ...
1
vote
0answers
73 views

Variance of chain length in hashtable

I have a hashtable with length $m$. Initially it's empty. Next, $n/2$ unique random numbers $\in [0, n]$ are added to it. What would be variance of chain length when such $n/2$ numbers are being added ...
1
vote
0answers
167 views

How can I choose good hash function for PCY algorithm

As far as I understand from PCY (Park, Chen, and Yu) algo is that the algo uses hashing during the first pass to reduce the number of CANDIDATE pairs that are considered in the second pass. I have 2 ...
1
vote
0answers
71 views

A tree-like data structure with rights delegation for distributed computing

Every actor can create a root node and delegate a right to add a child node. Every node contains name of its’ creator or who added it, and value S. Sum of all values S at the same level of the tree ...
1
vote
0answers
35 views

Is there a good way to hash abstract binding trees?

The hash function should be invariant under alpha-renaming. Using de Bruijn notation seems to be possible, but it requires alpha-converting the whole tree when a binding is created, and has the ...
1
vote
0answers
69 views

What is a minimal, pseudo-random hash function?

I want to generate pseudo-random hashes of inputs in a way that is optimally time and space efficient. I'm not at all concerned about security. The output should be evenly distributed and appear ...
1
vote
0answers
889 views

Why is the module of the second function in double hashing a prime number?

When using double hashing, the second hash function is defined as $$h_2(x)=A-x\mod A,$$ where $A$ is a prime number less than the capacity of the hash table. But why must $A$ be a prime number? (This ...
1
vote
0answers
56 views

Double Hashing Collision

Less Hashing Same Performance: Building A Better Bloom Filter (Kirsch and Mitzenmacher) mentioned that we can use $ g_i(x) = (h_1 (x)+ih_2 (x))\pmod{p}$, where $h_1(x)$ and $h_2(x)$ are two ...
1
vote
0answers
153 views

why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?

I am self-studying the book Intro to Algorithms 3ed by CLRS. One of the problems seems to give a piece of information that is not necessary, Problem 11-4 in the book states Let H be class of hash ...
1
vote
0answers
117 views

Bloom filters vs storing hashes as numbers

In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers)...
1
vote
0answers
53 views

What is the difference between O(n^2) and O(N)[N*O(1)]?

I was reading this article on gperf. In it they claim that the use of nested if statements for parsing command line input of $N$ options ends up making $O(N^2)$ ...
1
vote
0answers
318 views

What needs to be done after deleting an item in a hash table built under opening addressing with linear probing

In some textbook problems, the problem asks me to insert a bunch of elements and remove a bunch of elements. Insertion is done using linear probing, i.e. h = XmodR + I, when there is a collision, I ...
1
vote
0answers
71 views

Min/max of hash function (Whirlpool)

The Whirlpool hash function generates a 128-digit hexadecimal number. Could that number ever be ...
0
votes
1answer
76 views

hash-tables - Expected-time for an unsuccessful search

The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c. Suppose you have a hash table where the load-factor $\alpha$ is related to the number $n$ of elements in the table by ...
0
votes
0answers
17 views

A successful search takes $\Theta(1 + \alpha)$ time on average when resolving collisions by chaining

I would to discuss a proof found in CLRS book please. Theorem: In a hash table in which collisions are resolved by chaining, a successful search takes time $\Theta(1 + \alpha)$, on the average, under ...
0
votes
0answers
17 views

Prove that if $k$ was the $(i+1)$st key to be inserted into the hash table, then $E[probes(k)]=\frac{1}{1-\frac{i}{m}}$

Theorem: Inserting an element into an open-address hash table with load factor α requires at most $1/(1 − α)$ probes on average, assuming uniform hashing. By following unsuccessful search strategy, we ...
0
votes
0answers
34 views

Prove that Horner's method produce only 6 collisions on 50000 English words

Polynomial for producing hash values: $p(z)=a_0+a_1z+\cdots, a_{n-1}z^{n-1}$ Honor's method for that polynomial: $$ p_0(z)=a_{n-1} \\ p_i(z)=a_{n-i-1}+zp_{i-1}(z), (i=1, \cdots, n-1)\\ $$ Problem: For ...
0
votes
1answer
16 views

Detecting and correcting collisions in (Zorbist) hashing to avoid errors in transposition table

Context Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions. The table has a finite recycled memory (key % p is the <...
0
votes
0answers
17 views

Propose a family of hash functions with $mod p^2$ for some prime number $p$

I need to define a family H of universal functions $\{0,1, ..., p^k−1\} →\{0,1, ..., p^2−1\}$. Now based on a similar example I was thinking of something like: Given some $a= (a1, a2, ..., ak)∈\{0, ......
0
votes
0answers
19 views

Hash tables for storing data in an application that supports partial search

Is a hash table a good data structure for storing data in an application that support partial search such as "select * from MyTable where name like 'John%'. If not, what is? I would have thought ...
0
votes
0answers
21 views

What is the order of magnitude of bitwise operations involved in a SHA-256 hash?

Specifically, how many bitwise operations (approximately, could be just order of magnitude) occur each time a Bitcoin ASIC miner performs a SHA-256 hash in typical mining computation, i.e. as it ...
0
votes
0answers
26 views

If the load factor is a decimal (say 3.6), what is the length of each chain in a hash table that utilizes separate chaining?

I understand that if the load factor were 2, then the length of the chain would be 2 for each index in the array, but what happens if the load factor is a decimal? Do we round up or down?
0
votes
0answers
22 views

Bad data for hash function

Is it possible to choose such a nontrivial set of queries so that the amortized running time for a hash table with a public key and a function like $(a_{N − 1}k^{N − 1} +... + A_{1}k + a_0) (mod \: p)$...
0
votes
0answers
41 views

Minimal perfect hash function for set of integers

This might be a trivial question, but I have the following problem: I want to (perfectly) hash a number of lists of integers of length $n$, with all entries between $k_{min}$ and $k_{max}$. How can I ...
0
votes
0answers
27 views

Expected runtime for hashing with a binary search tree as collision handling

I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption ...
0
votes
0answers
53 views

Simple incremental hash funcion

I have permutations: 4 1 2 5 3 4 3 2 5 1 numbers can be order magnitude of 1000 (fits in two bytes) I want compute 32 bit (or better 64 bit) hashes, it should be ...
0
votes
0answers
25 views

Double Hash Family Universality

Here I am given 2 hash families and I need to prove the universality of the double hash, but I am stuck as to how to prove this. I know the properties of an epsilon-universal family is that the ...
0
votes
1answer
126 views

Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)

I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of Universal Class of Hash Function. The versions are as follows: ...
0
votes
0answers
34 views

Is this example in Skiena's Algorithm Design Manual correct?

i think the above is incorrect; specifically, i think H isn't bijective. say our alphabet is the lowercase letters [a-z] and ...
0
votes
0answers
46 views

Hashing algorithm which minimizes distribution

Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...