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

Filter by
Sorted by
Tagged with
84
votes
5answers
68k views

Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$ H = k \bmod \ 11$$ Now all the values will be placed ...
27
votes
5answers
3k views

Is there an anti-Bloom filter?

A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing. When there are many data items then a Bloom filter can result in ...
18
votes
2answers
6k views

Could quantum computing eventually be used to make modern day hashing trivial to break?

Simply put, if one were to build a quantum computing device with the power of, say, 20 qubits, could such a computer be used to make any kind of modern hashing algorithm useless? Would it even be ...
14
votes
2answers
200 views

Function that spreads input

I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics: $f$ should be bijective Both $f$ and $f^{-1}$ should be calculable pretty fast $...
11
votes
2answers
7k views

Fast hashing: combination of different techniques to identify changes in a file?

I want to create a fast way to detect whether a file might or might not be the same. For almost 100% sureness I would use an existing hash algorithm, e.g. SHA256. However, the files are expected to be ...
10
votes
3answers
2k views

Why is a (collision-less) hashtable lookup really O(1)?

Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for. My question is: why is collision-less ...
10
votes
2answers
807 views

Weak hashing function for memorable IPv6 addresses

IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4. There have been ...
9
votes
1answer
393 views

Attack on hash functions that do not satisfy the one-way property

I am revising for a computer security course and I am stuck on one of the past questions. Here is it: Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to ...
8
votes
1answer
834 views

Is there a continuous hash?

Questions: Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$? Can we add an efficiently computable closeness predicate which given $h_k(x)$ and $...
8
votes
2answers
697 views

How to avoid cascading resizes when resizing hash tables?

With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability ...
7
votes
2answers
1k views

Bloom filter and perfect hashing

A Bloom filter uses a hash function to test membership in a given set $S$, by checking if an item is present of not at the specified position. To mitigate the effect of hash collision, multiple ...
7
votes
3answers
332 views

1-to-1 cryptographically secure bit shuffling

Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes). The function should have the following qualities: It should be 1-to-1 so that all inputs ...
7
votes
1answer
315 views

Is it known whether the MD5 algorithm is surjective?

Does MD5 map to all possible 128 bit numbers? To put it another way: For every 128 bit number y, does there exist at least one x ...
7
votes
1answer
398 views

Can proofs-of-work be probabilistically checkable?

I have been lurking for a while; this is my first post here. I’m sorry if my question is ill-formed or formatted poorly. This question came out of some ideas in another question from a sister site. ...
7
votes
1answer
224 views

Most space-efficient lossy dictionary?

Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)? Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ ...
7
votes
0answers
862 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 ...
6
votes
5answers
433 views

Is the codomain/range of a hash function always $\mathbb{Z}$ or $\mathbb{N}$?

From Wikipedia A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length. For example, a person's name, ...
6
votes
2answers
5k views

How does taking modulo 1 make sense?

I need some help understanding the problem statement in CLRS 11.3-4 pg 269. It says: Consider a hash table of size $m = 1000$ and a corresponding hash function $ h(k) =\left \lfloor m(kA \bmod ...
6
votes
2answers
193 views

Is the following intuition valid for understanding $k$-wise independent hash functions?

I really enjoy reading up on algorithms and data structures and in the course of doing so often come across ones that rely on $k$-wise independent families of hash functions. I'm perfectly comfortable ...
6
votes
1answer
1k views

Why does the Count-Min Sketch require pairwise independent hash functions?

The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream. Intuitively, it works by picking a variety of hash functions, hashing each ...
6
votes
1answer
477 views

How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?

Given a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^n$, a difficulty $d\in\mathbb{N}$, and data $D\in\{0,1\}^*$, the framework of the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $c$ such ...
6
votes
1answer
219 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 ...
6
votes
1answer
3k views

Find longest common substring using a rolling hash

The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring ...
6
votes
2answers
2k views

Hash size: Are prime numbers “near” powers of two a poor choice for the modulus?

Cormen et al.'s "Introduction to Algorithms" says the following about the division method hash function $h(k)=k \text{ mod } m$: A prime not too close to an exact power of 2 is often a good choice ...
5
votes
3answers
2k views

What is the point in hashing a value?

I apologise if this is not the right place for this question... I didn't want to ask on Stackoverflow or CodeReview as it will closed in minutes as "too broad". A client of mine is writing an API ...
5
votes
2answers
5k views

why not just use a random number generator as a hash function?

I guess at the heart of this is that I don't really understand hash functions. One article says any function mapping objects to an object of fixed size: A hash function usually means a function ...
5
votes
3answers
2k views

How should I design a hash table where all the keys are permutations?

I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys. Given that I know how all the keys look ...
5
votes
4answers
225 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
2answers
3k views

Why is Big O not defined here for a hash table?

In this cheat sheet, average time complexity for access to a hash table is listed as N/A. I'm curious as to why. Since a hash table is mostly mathematical, I would assume it would be O(1) like the ...
5
votes
3answers
862 views

Building static hash table with particular collisions

Is there efficient algorithm to encode keys in hash function with provided collisions? By efficient I mean with low-ish runtime of lookup operation (taking constants into account) and realistic time ...
5
votes
1answer
555 views

What is an example of a weakly universal hash function that is not pairwise independent?

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)) \leq 1/m$$ Here the function $h:U \rightarrow [m]$ is chosen uniformly from the ...
5
votes
1answer
2k views

What exactly is a hash function?

I have no idea how I managed to get this far in life without ever really grasping this but as it happens I'm still very confused on the concept of a hash function. I did some googling/wikipedia-ing, ...
5
votes
1answer
303 views

A hash function with predicted collisions

As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with predicted collisions? In other words, a hash function that collides ...
5
votes
1answer
482 views

Fixed point of hash

Are hashing algorithms constructed to guarantee that no fixed point exists? My assumption is not, because I don’t see what utility that would have. (Please correct me if I’m wrong.) As such, purely ...
4
votes
1answer
373 views

Hash-Table in Practice

I have a set of $n$ values,$v_i$ and want to insert them into a hash-table, $HT$, in a way that each bucket (or hash-table cell) has at most $d$ values. I set $k=\frac{n }{d}$, where $k$ is the number ...
4
votes
2answers
615 views

Understanding of hash tables

I am currently studying hash tables in an introductory course to computer science. I was taught that hash table is a data structure that associates a key to an index (a hash table) and then to the ...
4
votes
3answers
89 views

Integer set disjointness query on sketches with something like homomorphic hashing

Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. ...
4
votes
1answer
2k views

Finding hash of a substring $[i, j]$ in $O(1)$ using $O(|S|)$ pre computation

Given a string $S$ of length $n$ characters, is it possible to calculate the hash of its substring $[i, j]$ (from index $i$ to $j$, both inclusive) in $O(1)$ using some form of precomputation? Can we ...
4
votes
1answer
146 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
4
votes
1answer
1k views

How can one find an element in a Merkle tree?

How can one find an element in a Merkle tree, as effectively as possible? Each internal node has a hash value. So I think, first, hash the value to find, and if an internal node has the same value ...
4
votes
1answer
169 views

Indexing Edge Permutations for the Rubik's Cube

I'm working on a Rubik's Cube solver that implements Korf's algorithm, as published in his 1997 paper, Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. His method involves creating ...
4
votes
1answer
96 views

Reversible Merge of Integer Hash Values

Context: I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's ...
4
votes
1answer
233 views

Hash for verifying both compressed and uncompressed data?

Is it possible to have a single hash function output simultaneously verify a compressed block of data as well as its uncompressed counterpart? Trivially one could just use a hash function twice (once ...
4
votes
1answer
959 views

Finding similar high dimensional real vectors

I have a collection of vectors $v_1,v_2\in [0,1]^n$ and I want to find similar pairs quickly. For similarity, I want to use the Euclidean distance metric $L: [0,1]^n \times [0,1]^n \longrightarrow R$. ...
4
votes
1answer
660 views

Hashing algorithm for millions of variable length strings (URLs)

The goal is to distribute approximately 100 million variable length strings, average length 100 characters, uniformly among 100 million buckets. Perfection not required, just no egregious clumping. ...
4
votes
1answer
78 views

Prove the probability of which a hash function is collision-free

Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
4
votes
1answer
499 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
369 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
542 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
2answers
2k views

Why does this particular hashCode function help decrease collisions?

I just read in Effective Java about the hashCode method: Store some constant nonzero value, say, 17, in an int variable called result. For each significant ...

1
2 3 4 5 6