Questions tagged [hashing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
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 ...
1
vote
1answer
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$. ...
2
votes
1answer
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 ...
-1
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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, ...
4
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
60 views

Checking whether a given Hashing Function fulfills Uniform Hashing Condition

I am learning about Hashing and have struggles with the following assignment: $U$ is a universe of keys with $Z(m)=\{0,\ldots, m-1 \}$ the amount of possible hash-values. Given $U= \mathbb{Z}...
5
votes
4answers
11k views

Two-way Hash Functions

While I'm aware most (good) hash functions are one-way (or at least mostly so), I'm wondering if there's any construct (not necessarily called a hash function) which behaves in many ways like a hash ...
2
votes
4answers
169 views

Using two hash functions for increased password security?

Forgive me for my brief knowledge on hash functions as I am not from a computer science background, however I am researching password security for my thesis and have been looking into hashing ...
4
votes
1answer
205 views

What is the complexity class of solving hash decision problems?

With $hash_n$, I mean a standard cryptographic hash like sha256, scaled up to have arbitrary length $n$ of its output with the same underlying principles. What is the time complexity class of the ...
0
votes
0answers
40 views

Verification of extendible hashing proof

I have to proof this theorem: "An extendible hashing table always contains at least one bucket where only one pointer points to after an element is added". I made this proof, but I'm not completely ...
2
votes
3answers
149 views

Given a string, is it possible to determine which hashing algorithm has produced it, if any?

Given a string, is it possible to determine which hashing algorithm has produced it, if any? For example, the MD5 hash of "string" is b45cffe084dd3d20d928bee85e7b0f21. Is it possible to determine ...
2
votes
3answers
2k views

Hash function to hash 6-digit positive integers

Let UID denote a unique identifier. UID's are represented as 6-digit positive integers. I want to insert a collection of UID's in a hash table with $M$ buckets, where $M$ is a prime number (for ...
0
votes
1answer
94 views

Reading CLRS analysis of hashing with chaining

I'm currently reading an analysis hashing with chaining, and it goes over two examples: In the first, the search is unsuccessful; no element in the table has key k. In the second, the search ...
2
votes
1answer
303 views

Heuristic analysis of Bloom filters

I am currently watching a lecture on Bloom filters, and the professor is doing a heuristic analysis of Bloom filters. It's all based on the following assumption: All $h_{i}(x)$'s are uniformly ...
1
vote
1answer
60 views

Generate collision resistant identifiers with two-way hashing

Objective: We want to generate a unique and reproducible identifier for a given slice of bytes and avoid collisions. High-level idea: Compute $$fK := hash(k_1)\; and\; sK := hash(k_1^{-1})\; where\; ...
0
votes
1answer
91 views

Hashing Probabilities

I'm not too sure about how to calculate hashing probabilities, and can't find much documents online to help me with it. Am looking to solve this question "If we hash N items into M buckets using a ...
0
votes
2answers
513 views

Hash functions and pathological data sets

So I'm watching an Algorithms course in Coursera, and we are currently discussing hash tables. He's talking about the importance of a good hash function, and about how an ideal hash function would be ...
2
votes
1answer
720 views

Locality-sensitive hashing random projection

I'm trying to understand how the LSH works for Cosine Similarity metric. For instance, let's say you have $\vec{v} \in \mathbb{R}^d$ and the random vectors $\vec{r_{i}} \sim \mathcal{N}(0, 1)^d$ that ...
2
votes
1answer
574 views

Hash multiple integers directly using FNV-1a

An alternative version of FNV-1a hash spread on the internet, which operates directly on integers instead of bytes. The offset basis and prime are the same used in the original version, which operates ...
1
vote
1answer
475 views

Embedding high dimensional vectors into low dimensional space preserving similarity

I have a collection of high dimensional vectors such as $\vec{a}_{i} \in \mathbb{R}^{n}$ where $n$ is 3000. What I want to do is to embed these vectors into a space such as $\vec{b}_{i} \in [0, 255]^{...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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) ...
4
votes
0answers
229 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 $...
2
votes
1answer
300 views

Hash function which is invariant under small changes

I am looking for a hash function which is invariant under small changes. E.g., if I have two strings MyString and MySttring ...
1
vote
1answer
49 views

Is this some kind of hashing?

Say I have $n$ vectors $\{ z_i \in \mathbb{R}^D\}_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\{x_i \in \mathbb{R}^d \}...
6
votes
1answer
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 ...
37
votes
5answers
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
3answers
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 ...
3
votes
1answer
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 ...
1
vote
1answer
124 views

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 ...
2
votes
3answers
79 views

Fast comparison with a tolerance

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