# 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

200 questions
24 views

### Function to generate longer bit-sequence from shorter sequence with certain properties

im not familiar with the terminology of computer-science which makes it pretty difficult to search for the problem I have. I'm looking for a function that generates a sequence of bits (B) of a given ...
47 views

### Deterministic algorithm to find number of collisions

Let $h:U \to[m]=\{0,1,\dots,m\}$ be hash function, which can calculate $h(u), \forall u\in U$ in $O(1).$ Let $D \subseteq U$ be a subset of size $n.$ I'm looking for a deterministic algorithm, ...
43 views

### Computing 'score' of string which preserves < relation

Is there a way to calculate some kind of numerical 'score' for arbitrary strings which when compared with score of some other string will preserve '<' relation? I've searched for order preserving ...
280 views

### Can Double Hashing return the same value 2 times?

$h(i,k)=(h^{}_{1}(k)+i * h^{}_{2}(k)) mod |T|$ as it defined in wikipedia I would like to know if it possible that Double Hashing return the same value for given $k$ when $i=1$ and $i=2$. Or from ...
35 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], <...
39 views

### Double Hashing Collision

Less Hashing Same Performance: Building A Better Bloom Filter (Kirsch and Mitzenmacher) mentioned that we can use $g_i(x) = (h_1 (x)+ih_2 (x))\pmod{p}$, where $h_1(x)$ and $h_2(x)$ are two ...
775 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 ...
401 views

### Probability of hash collision in the case of two parallel hashes

I understand how to calculate the probability of a hash collision. I am designing a DB and have a potential case where a record could have the inherited hash of its parent plus its own hash, meaning ...
40 views

### why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?

I am self-studying the book Intro to Algorithms 3ed by CLRS. One of the problems seems to give a piece of information that is not necessary, Problem 11-4 in the book states Let H be class of hash ...
6k views

### Explain Hashed page tables in operating system

I have a difficult time understanding hashed page tables used in virtual memory management. Here is picture of the slide that I am referring to: I understand that p is hashed and then the hash is ...
85 views

### Is a powerful two-way hash function provably impossible?

A two-way hash function that could hash complex strings to a fixed length would change the world. Imagine the decreased load on wires around the world if, for example, HTML pages could be hashed, ...
824 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 ...
88 views

### Bloom filters vs storing hashes as numbers

In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers)...
52 views

### Problem about getting a value of the hashed password [closed]

Given a database with usernames and the first six bytes of their hashed passwords. A standard hashing function has been used for hashing. admin 827ccb0eea8a user c3981fa8d26e operator 5f4dcc3b5aa7 ...
104 views

### range / interval query algorithm

I've an hash (base 32 for what it's worth): hash = 'ab352eghjhngd4' And I've subscribers that want to listen to new hashes in a range. ...
526 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 ...
290 views

### Universal family of hash functions

How to prove that a $k$-universal family of hash functions is $(k-1)$-universal family? I tried to prove it by definition of k-universal family of hash functions but I didn't know how to use the ...
78 views

### Existence of perfect hash function

In their original paper, Storing a sparse table with O(1) worst case access time (Fredman, Kolmos and Szemeredi, Proc. FOCS '82, IEEE, 1982), the authors show that a perfect hash function must exist, ...
304 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 ...
82 views

### Are there any hash functions/stateless RNGs that do not use XOR, but produce good quality visual randomness?

I'm looking for a small function from integers to integers - in a language that only has floats - that can act as a visual RNG. Normally I would use a function such as the one described here: ...
148 views

### “Hash” Probing?

While there are many types of probing in hash tables, such as linear probing, quadratic probing, and more, I haven't encountered a so-called "hash-probing" (maybe this method which I describe below ...
127 views

### Does this problem offer any insight into $P$ vs $NP$

What is the input of a given hash? The problem can be verified in polynomial time (using a hash that executed in polynomial time), and I suspect that it may be possible to prove that there is ...
208 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 ...
27 views

### Hash function for searching, is that feasible?

I have a set of sorted values $\left\{a_j \right\}_{1 \leq j \leq n}$, suppose now a number $x$ is given and we would like to find out the index $j$ such that $a_j \leq x < a_{j+1}$ (you can assume ...
26 views

### Prove you computed hash^r(input) for some cryptographic hash function [closed]

What is the most efficient way to prove that a person computed r rounds of some cryptographic hash function (ex. sha256) on an input?. The trivial solution seems to be to show all r hashes, where <...
327 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. ...
34 views

### Altering the size of a Hash

Does removing the leading(or trailing) n bits of any given hash have any negative effects other then increasing the likeliness of collisions? Does appending 2 hashes of the same object with different ...
80 views

### What hash algorithm is it?

I've found a simple multiply-with-add hash function in an old Usenet post. Can someone identify what hash algorithm is it? An algorithm name or any attribution? ...
20 views

### are these functions for open address hashing, proper?

I want to use these two functions in two hash-tables with open-addressing. Is there any problems with these functions? If yes, why they are not appropriate? ...
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 ...
58 views

### Hashing methods for validating dowloaded files

The standard algorithm to generate hashes of files which are downloaded is MD5. For example, when ISO files of Linux distributions are offered most of the time they also give the MD5 sum so that you ...
93 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 ...
76 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$. ...
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 ...
84 views

### Perfect hashing function algorithm

Is there a good (perfect) hashing algorithm for the following problem? We have $n \ll m$ (say $n=150$ and $m=5\times 10^{12}$) and we want a hash table to store integers up to $m$ whose prime ...
1k 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 ...
335 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 ...
41 views

### Repeated fingerprinting after array updates

I've got a microprocessor and want to quickly identify the settings of my application (stored in some eeprom regions) via a fingerprint instead of having to dump the entire memory every time. So I ...
192 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 ...
101 views

### Hash functions producing uniform outputs

I've seen this question in a past exam paper, and I know that the answer given is (b), but I'm not sure why. Which one of the following hash functions on integers will distribute keys most ...
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 ...
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 ...
118 views

### Do cryptographic hash function solve clustering problems with linear probing?

I understand in open addressing hash tables some clustering will always happen just by random chance, even if the input data is perfectly random, leading to some "best possible" lookup performance hit ...
45 views

### Information on Tavori and Dreizin ranged hash function?

While doing some digging around in the GNU implementation of the C++ standard library I came across a section in bits/hashtabe.h that refers to a hash function "in ...
85 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 ...
665 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 ...
765 views

### Graph adjacency using Hashing

Consider a graph $G = (V,E)$ and the following operation $\text{neighbour}(v_1,v_2)$: returns true if the vertices $v_1$ and $v_2$ are adjacent, and ...
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 ...
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]^{...