# Questions tagged [hashing]

The tag has no usage guidance.

90 questions
Filter by
Sorted by
Tagged with
108 views

### Using random projections for locally sensitive hashing

I recently came to see that this library sparselsh uses random projection to perform locally sensitive hashing of documents. The proof is such that based on cosine similarity to the vector. In other ...
78 views

### How to extend a hash function to manipulate longer integers?

Carter and Wegman introduced in the paper Universal Classes of Hash Functions the $H_{1}$ universal class of hash function. This is essentially the function $h_{a,b}(x) = ((a\cdot x+b)\mod p)\mod m$. ...
99 views

### Approximate Similarity Search

I am implementing an approximate similarity search using multi-index hashing. I have a set (T) of millions of strings (of same length) and I have a query string(P) (or set of strings) that needs to ...
174 views

### Help in understanding calculation of hash collision from a document

UPDATE In an earlier question of mine asked here : https://math.stackexchange.com/questions/2206095/beginner-level-understanding-concept-on-how-to-derive-probability-of-hash-collis , I got the answer ...
128 views

### Collision resistant Hash function in chaos cryptography

In my earlier Question asked here Help in understanding how to apply nonlinear function in hashing about chaos cryptography, since then I have come across several research papers that apply atleat ...
29 views

### Time complexity of finding duplicates across multiple lists using hashing

If I have m lists with n elements each, how would I go about finding duplicates in them (i.e. an element is in more than one of the lists)? My idea is to use hashing on the elements inside the list, ...
91 views

### Lemma 2 in Knuth's “Notes on Open Addressing”

I'm trying to read Knuth's Notes on Open Addressing, and I don't quite follow the proof of Lemma 2. The set-up We're thinking about hashing $k - 1$ keys into a size $N$ array, with collision ...
155 views

### Method for finding Hyperrectangle that a coordinate is within

I have a problem at work where I have set of hyperrectangles, in no particular order, that do not overlap and when unioned create a hyperrectangle with no gaps. At the moment I am looking for a way to ...
2k views

### How would you prove a family of functions is universal?

A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a ...
60 views

392 views

### Is FKS hashing really linear space?

In FKS hashing, I wonder if the size of the table $G[ 1..n]$ (used to record the functions $g_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability ...
135 views

### Help in understanding how to apply nonlinear function in hashing

Can somebody help in brainstorming how to apply the map as a hashing function? I am aware that chaos is used in cryptography but I fail to understand how to apply it. Most popular hashing techniques ...
721 views

### Difference between properties of good hash function: uniformity and randomness

I did go through Korth's book of DBMS and I got these definitions: Uniformity: Each bucket is assigned the same number of search-key values from the set of all possible values. Randomness: Each ...
94 views

### Constraint on Universal set of hash functions

I was reading hashing from CLRS. In it author says: Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a ...
8k views

### Understanding hashtable performance in the worst-case

Under assumption that the hash function is uniform, we have worst-case performance for the search operation in a separate-chaining (e.g. java.util.HashMap) ...
229 views

168 views

### Two definitions of universal hash functions

I have seen two definitions of universal hash functions in the literature. For any $i \geqslant 2$ let $[i]=\{1,\ldots,i\}$. Definition 1: A family $\mathcal H$ of hash functions from $[n]$ to ...
38k views

### What exactly (and precisely) is “hash?”

I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, in the chapter on ...
686 views

### Merkle tree collision probability

Say I use a perfect 128-bit hash function to construct a merkle tree. By perfect I mean that any of the values in the $0$–$2^{128}$ range has an equal probability to be an outcome of the ...
89 views

### Different probabilistic statement for Simple Uniform Hashing

Let me denote the number of elements with $n$ and the size of the table with $m$. I was trying to understand the Simple Uniform Hashing assumption that people and books describe in works and make them ...
342 views

### What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$

Recall the definition of the load factor is the average number of elements in a chain for hashing for a table $T$ of size $m$ (with $n$ elements in consideration). Let $n_j = T[j]$ be the size of the ...
51 views

### Finding a (minimal?) program that maps $M$ items to indices $[0,M)$

Let's say there are $M$ strings that we are trying to create a perfect hash for such that we get as output of the hash $[0,M)$ with no collisions, when hashing those $M$ items. I know that there are ...
### Why Bloom filter needs $\frac{m}{n}\ln{2}$ hash functions?
I show from Wikipedia that the optimal number of hash functions is: $k =\frac{m}{n}\ln{2}$. However it's not obvious for me why, even after reading the Wikipedia article (such as the one on false ...
I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$. I want to do this by ...