# Questions tagged [hashing]

The tag has no usage guidance.

120 questions
Filter by
Sorted by
Tagged with
5answers
45k 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 ...
4answers
15k 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 ...
3answers
231 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 ...
1answer
195 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 ...
4answers
182 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 ...
1answer
54 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 ...
1answer
130 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 ...
1answer
468 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 ...
1answer
306 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 ...
0answers
70 views

### Expected search times with quadratic vs linear probing

Why exactly does quadratic probing lead to a shorter avg. search time than linear probing? I fully get that linear probing leads to a higher concentration of used slots in the hash table (i.e. ...
0answers
333 views

1answer
87 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 ...
1answer
82 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, ...
1answer
63 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 ...
1answer
351 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 ...
1answer
46 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 ...
1answer
166 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 ...
1answer
97 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$. ...
0answers
31 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, ...
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.
1answer
105 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 ...
4answers
198 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 ...
1answer
431 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 ...
1answer
11k 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) ...
2answers
66 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 ...
2answers
68 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 ...
1answer
607 views