Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

47
votes
4answers
35k 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 ...
24
votes
5answers
2k 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 ...
17
votes
2answers
5k 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
173 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 $...
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
688 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
338 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
2answers
5k 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 ...
8
votes
1answer
531 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
445 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
927 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
321 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
309 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. ...
6
votes
5answers
314 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
3answers
712 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 ...
6
votes
2answers
135 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
284 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
163 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
247 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 ...
6
votes
0answers
609 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 ...
5
votes
3answers
1k 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
741 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 ...
5
votes
1answer
245 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
2k 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 ...
5
votes
1answer
121 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$ ...
5
votes
0answers
193 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
2answers
3k 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 ...
4
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 ...
4
votes
1answer
297 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
1answer
1k 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, ...
4
votes
1answer
509 views

Understanding Murmur3

The Bloom filter data structure requires a set of hashing functions. The Murmur3 family is a great fit, as it contains the seed parameter to easily create a variety ...
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
2answers
660 views

Hash size: do prime numbers “near” powers of two are bad?

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 ...
4
votes
2answers
1k views

Check-digit algorithm that includes characters?

I have a data set that uses a very simple modulo 10 checksum algorithm which ignores alphabetic characters entirely. Which wasn't a big deal, as the few alphabetic characters present weren't ...
4
votes
1answer
104 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
647 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
565 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
178 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
59 views

Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?

Calculating hashes for nodes in an acyclic graph is well known using a Merkle tree. With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a cyclic graph... but ...
4
votes
1answer
346 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
599 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 ...
3
votes
2answers
1k 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 ...
3
votes
2answers
323 views

Term for binary search tree using hashes?

I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, ...
3
votes
2answers
184 views

What is the reasoning behind magic constancs in hash code calculations found in programming practice?

In real-world programming, we frequently need to compute hash codes for complicated objects. The main desired properties are that the values should be deterministic and have few collisions. Let's ...
3
votes
2answers
304 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 ...
3
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 ...
3
votes
5answers
228 views

Efficient set data structure supporting insert and set equal

What's the best way to represent sets that support the following two operations: Insert(s, i) - adds nonnegative integer i to set s Equal(s1, s2) - Tests if s1 and s2 are the same set. In addition, ...
3
votes
1answer
137 views

Why does appending permutations of servers at the end of hash table avoid bottlenecks?

I was reading the following FDS paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf The paper has a TLT (tract locator table) for identifying where to write in each ...
3
votes
1answer
242 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 ...