Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [hashing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
38
votes
5answers
40k 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 ...
6
votes
3answers
170 views

Can we remove duplicates faster than we can sort?

The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers): Given a sequence $S_\text{in}$ of $n$ integers, produce a ...
6
votes
1answer
174 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 ...
5
votes
4answers
124 views

How do you find a hash function that respects a custom equality function?

I've been tasked with hashing arbitrary types in C++, with the caveat that A == B implies hash(A) == hash(B) even if equality of ...
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 ...
4
votes
1answer
98 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 ...
4
votes
1answer
409 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 ...
4
votes
1answer
210 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 ...
4
votes
0answers
255 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 $...
3
votes
1answer
590 views

Knuth's proof of O(1) for linear probing

I'm currently reading Knuth's proof about O(1) number of probes in linear probing. I have a small question on the page 536 (Volume 3, 2nd Edition). Knuth says Let $f(M, N)$ be the number of hash ...
3
votes
1answer
750 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 ...
3
votes
1answer
69 views

Small space hash functions that are weakly but not strongly universal

This is a follow up to this this question about weakly universal hash functions A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ : $$P_{h \in H_w}(h(x) = h(y)) \...
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 ...
3
votes
1answer
49 views

The expectation of the total number of pairs of keys in a hash table that collide using universal hashing

I am reading CLRS relating to perfect hashing. When computing the $$ \mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}] $$ where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...
3
votes
2answers
732 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 ...
3
votes
1answer
143 views

non-binary locality-sensitive hashing with random projections

I'm interested in using a random projection as a locality sensitive hash. In every example of this I've seen, it is suggested to pick a random hyperplane and produce a binary number corresponding to ...
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 ...
2
votes
3answers
81 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 ...
2
votes
3answers
150 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
385 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 ...
2
votes
1answer
600 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 ...
2
votes
1answer
137 views

Ketama hash explanation

(I originally posted this on stackoverflow but thought it would be a better fit here) I'm trying to understand the Ketama hash code used in consistent hashing. link and snippet below: ...
2
votes
1answer
39 views

Is there a heuristic or function to determine if two arrays of integers are alike or similar

What I am trying to do is determine "closeness" or how similar are arrays of integers (or byte arrays, doesn't matter). For example, let's say a = [0, 1, 2, 3, 4], <...
2
votes
1answer
764 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
28 views

Given a family of hash functions in table form, how can I know whether it's universal?

I've been given the following two families of hash functions: H and G Each family has three functions $\{0,1,2,3,4\} \to \{0,1,2\}$ that can be seen in the tables above. For each family I need to ...
2
votes
1answer
57 views

Avoiding correlated values and reduced collision resistance in multiple hash states

I need to design a hash function that fits this criteria: Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system) Produces an n-bit hash digest, ...
2
votes
1answer
62 views

General name for linked lists based on hashes

I am thinking of a particular datastructure, but don't know the name of it. A sequence of elements may be modeled by a collection of some X, where each X consists of: The element, serialized as a ...
2
votes
1answer
317 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 ...
2
votes
1answer
37 views

Is there a way to theoretically compare hash functions?

Say I am given two hash functions f1 and f2 is there anyway that I can prove one hash function will produce fewer collisions ...
2
votes
1answer
104 views

Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation

In this blog the author states that the following So we now have a rather poor estimate of the number of values in the dataset based on bit patterns. How can we improve on it? One ...
2
votes
1answer
79 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
0answers
1k views

Open hashing vs closed hashing

What are advantages of closed hashing over open hashing? I know the difference between those two but can't figure out why would closed hashing be better in any way. Thanks.
2
votes
0answers
132 views

What is the deterministic time complexity of obtaining the set of distinct elements?

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known ...
2
votes
1answer
101 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 ...
2
votes
4answers
174 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 ...
2
votes
1answer
317 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
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) ...
1
vote
2answers
49 views

Check whether all elements are different

Assume we have $n$ double elements $a_1 \dots a_n$. We want to find out if two of the elements of the array are identical. And we have a hash function $h(x)$ which assigns each double value an integer ...
1
vote
2answers
55 views

Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?

This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on). Those algorithms are handy ...
1
vote
1answer
496 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]^{...
1
vote
3answers
1k views

How does Rabin fingerprint finds breakpoints (chunk boundary)?

I was reading up on chunking and found Rabin fingerprinting is also used to break files into chunks. After reading about this algorithm, I understood how rolling hash is computed using Rabin ...
1
vote
1answer
133 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 ...
1
vote
1answer
52 views

Generate numeric or string ID for a sequence of elements

How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter. Example: [41,1001,32] should generate the ...
1
vote
1answer
138 views

Practicality of compressing data with hashing algorithms

I want to compress the string 0cc175b9c0f1b6a831c399e269772661. I can do so by storing the string a, and, when decompressing, using a as input for the MD5 hash algorithm to get the original string. I ...
1
vote
1answer
64 views

Can we recognize the difference of two strings of $2^n$ length using polynomial size strings?

Is it possible to transform binary strings of length $2^n$ to $n^c$ binary strings of sized $n^d$ such that $$\forall s_1,s_2 \; \exists i \in \{1,\cdots,n^c\} \; f_i(s_1)\neq f_i(s_2),$$ Where two ...
1
vote
1answer
136 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
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 ...
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\; ...
1
vote
2answers
153 views

Simple Uniform Hashing Assumption and worst-case complexity for hash tables

My question: Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is O(1)? It says in the Wikipedia article that this ...
1
vote
1answer
29 views

What are the k-collections described in ch. 8 of “An Introduction to the Analysis of Algorithms” by Sedgewick

In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425. My confusion is how to identify the k-...