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
0
votes
1answer
20 views
additive hash function
Do functions with the following properties exists for x being arbitrary stream of bytes:
op(f(x1), f(x2))=f(x1+x2) and op(f(x1), f(x2))!=f(x2+x1) given that x1!=x2 where plus denotes concatenation ...
1
vote
2answers
58 views
probability of collision
my data's range is from 1 to 9 and I have two subsets of integers from this range.
the hash function takes each of this subsets and calculate product of these three integers and maps this set to the ...
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 ...
1
vote
0answers
33 views
Is my universal hash function of factor 2?
Imagine that we have a simple family of Hash functions $H=\{h_a\mid a\in[p],\, a\neq 0\}$, where $h_a(x)=(ax\bmod p)\bmod n$.
Let's assume $p$ is a prime number between $u$ and $2u$.
I want to show ...
1
vote
1answer
31 views
Most efficient way to check if key exist on a table
Imagine a person called Albert. Albert lives in Europe and would love to move to America. One day he got his wish come true. A person called Margareta gave him a key. The value of the key is the same ...
0
votes
1answer
33 views
Finding duplicates in a stream of numbers
This is an interview question.
Say you have a function foo() which returns some integer.
You need to write an algorithm that does the following:
(...
1
vote
1answer
31 views
In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?
In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for ...
2
votes
1answer
34 views
Are hash functions really quantum resistant for commitment schemes?
It is commonly stated that hash functions remain secure in a post quantum world, the justification being that a quantum computer only has the advantage of Grover's search to give it a quadratic ...
0
votes
1answer
16 views
Do not understand a concept in analysis of open-address hashing
I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor α=n/m<1, the expected number of ...
0
votes
1answer
34 views
How is this the expected number of of probes in open-address hashing?
I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor $\alpha = n/m < 1$, the expected ...
1
vote
2answers
47 views
Why can't hash coding be reversed?
Why is it impossible to reverse a hash code? There could be some way to crack this coding?
1
vote
1answer
91 views
Can we do 4-sum algorithm in O(n^2)?
this is related to the following question:
Generalised 3SUM (k-SUM) problem?
Without loss of generality, let's only consider even $k$, or just $k=4$.
My question is, after summing all pairs of ...
0
votes
1answer
40 views
Does this excerpt from the linear probing Wikipedia page make an assumption?
Here is the excerpt from the linear probing page at Wikipedia.
To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and ...
0
votes
1answer
107 views
How to get all in constant time?
We are planning to design a system where following operations are supported.
...
0
votes
1answer
45 views
Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p
Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely.
Could you explain ...
1
vote
3answers
70 views
Is the capacity of a hash table a constant value?
In this paper, page 4, it is said:
"...there is always a constant expected number of elements that map to the same slot"
Assume we have a set $S$ of $n$ values, and we want to insert them into a ...
2
votes
1answer
77 views
Clarification reg. jump consistent hashing
I was reading the paper on Jump consistent hashing, and I'm having some trouble understanding one particular line (page 5, paragraph 2)
"Since we want P(j ≥ i) = (b+1) / i, we set P(j ≥ i) iff r ≤ (b+...
5
votes
1answer
118 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$ ...
0
votes
0answers
37 views
Is this PJW hash function incorrect?
I came across this implementation of PJW and it seems incorrect:
...
0
votes
0answers
17 views
Can I uses with same hashing-function for two hash-tables?
Given 2 hash tables , can I use only one hashing function for the two hash tables?
I don't sure if the size of the hash-tables is necessarily affect about the hashing-function that this hash-table ...
3
votes
1answer
36 views
Bounds on probe lengths and number of rehashes with universal hashing
Say I have a family of hash functions that are weakly universal, i.e. the probability of two non-identical keys $x\neq y$ are mapped to the same hash-value is bounded by $k/m$ when I have $m$ bins and ...
2
votes
0answers
37 views
Approximate dot product between neural network output layer's parameter vector and input activations with winner-take-all hashing
In the paper Deep Networks with Large Output Spaces, Vijayanarasimhan et al. describe their approach to approximating the dot product between a neural network's output layer's parameter vector and ...
-1
votes
2answers
136 views
Perfect (or almost perfect) Hash function for n bit integers with exactly k bits set
I have a a data set with 2598960 elements of of unsigned integers of (at most) 52-bit length. The data set has a property that exactly 5 bits set.
This is only 1 data sets – I have similar data sets ...
0
votes
1answer
11 views
Method for eliminating spent hashes from a large collection?
Consider a DB with a large set of numbers, like hashcash tokens, where new numbers are constantly added(spent). Only numbers that has not been already added can be accepted.
Is there a functional way ...
0
votes
0answers
90 views
Proving a hash function family is weakly universal
$H$ is a family of weakly universal hash functions if for two elements $x,y$:
$$ P(h(x) = h(y)) \le \frac1m, $$
where $m$ is the size of the domain, and $h$ is chosen at random from $H$.
...
0
votes
1answer
47 views
Can anyone find a mapping from the set of all possible string to the natural numbers?
Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$?
$$h : S^* \rightarrow \mathbb{N} $$
Assume $S$ is finite. I would prefer an ...
0
votes
1answer
24 views
Bloom Filter which does not fit in RAM [closed]
Is it possible to efficiently create a bloom filter with 10^12 buckets on a single machine with 32GB of RAM and a hard drive. We can assume that the keys are already on the disk and are small in size?
0
votes
0answers
151 views
Average number of comparisons for hash/rehash operations
I have the below problem, which I've already been given the answer to, I'm just trying to understand why the answer is the way it is. I've modified the language of the problem significantly so it ...
0
votes
0answers
470 views
Rolling Hash calculation with Horner's method
I understood how Horner's method reduces the complexity(number of operations) while evaluating a polynomial.
I have a character array derived from a string
...
0
votes
1answer
283 views
How to actually implement universal hashing?
I sort of get what it is, but I don't understand how its actually supposed to be used in algorithms. Suppose the hash function is $h_{ab}(x) = ((ax+b) \mod p ) \mod m$ where $a$ not equal to 0. If I ...
2
votes
1answer
52 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, ...
4
votes
0answers
58 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 ...
0
votes
0answers
185 views
Why is the module of the second function in double hashing a prime number?
When using double hashing, the second hash function is defined as $$h_2(x)=A-x\mod A,$$ where $A$ is a prime number less than the capacity of the hash table. But why must $A$ be a prime number?
(This ...
0
votes
0answers
29 views
Can you compress standard HyperLogLog sketches to a small vector?
I've come across this paper by Otmar Ertl in Github. If I understand it correctly, he points out that when you use p + q bit hashes, you put integers at most of value q into 2^p registers. Instead, he ...
0
votes
1answer
99 views
Will Java's hashCode() reduce collisions regardless of table size?
for a class project we have to count the number of collisions from inserting words from a plaintext document into a hashtable. I read that using prime numbers for table sizes can offset the collisions ...
0
votes
0answers
26 views
Is it possible to retrive the Hash from an encrypted folder?
So first of all I've a software which basically locks/encrypts a folder with a given password. Afterwards it's almost impossible to open the folder without entering the password through the software.
...
0
votes
0answers
20 views
Expected block count of linear hashing
I ran in to this problem and I can't figure it out myself.
Can anyone give me a hint?
A linear-hashing scheme with blocks that hold k records uses a threshold constant c, such that the current number ...
2
votes
1answer
67 views
Surprisingly high collision rates when hashing a short list with few buckets
I'm trying to help my daughter with her CS assignment on hashing. She has an input list of about 4000 English words, each 5 letters long. The prof has limited her to 4000 output buckets (digests? -- ...
0
votes
1answer
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 ...
1
vote
1answer
45 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, ...
1
vote
1answer
41 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 ...
0
votes
1answer
242 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 ...
2
votes
1answer
34 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], <...
1
vote
0answers
37 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
...
4
votes
2answers
622 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 ...
0
votes
2answers
260 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 ...
1
vote
0answers
38 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 ...
0
votes
1answer
4k 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 ...
-2
votes
1answer
83 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, ...
2
votes
2answers
507 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 ...
