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
249
questions
0
votes
0answers
34 views
Simple incremental hash funcion
I have permutations:
4 1 2 5 3
4 3 2 5 1
numbers can be order magnitude of 1000 (fits in two bytes)
I want compute 32 bit (or better 64 bit) hashes, it should be ...
-1
votes
1answer
55 views
What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case
Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
0
votes
0answers
20 views
Double Hash Family Universality
Here I am given 2 hash families and I need to prove the universality of the double hash, but I am stuck as to how to prove this. I know the properties of an epsilon-universal family is that the ...
1
vote
1answer
64 views
When and Why do I Rehash?
I am studying hashing and reading the part of universal hashing. I have read that I want to draw a hash function from universal hash families when I rehash. When and why do I rehash?
One reason to ...
3
votes
1answer
48 views
Merkle tree sorting leaves and pairs
I am implementing a Merkle tree and am considering using either of the two options.
The first one is sorting only by leaves. This one makes sense to me since you would like to have the same input ...
2
votes
0answers
30 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, ...
1
vote
1answer
40 views
Difficulty in understanding few steps in the proof: “The class $\mathscr{H}_{p,m}$ of hash functions is universal”
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following excerpt regarding the said proof and the steps where I felt difficulty are marked with $\...
1
vote
0answers
33 views
Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)
I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of Universal Class of Hash Function.
The versions are as follows:
...
1
vote
0answers
13 views
In Hashing-collison resolved by chaining: Intuition behind $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$
Hashing-collison resolved by chaining: $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$
I was going through the text Introduction to Algorithms by Cormen et. al. and in the ...
1
vote
2answers
76 views
Double Hashing with Strings as key
How would you choose the second hash function with for double hashing with string as key?
My first hash function is the scalar product of a random int array with the 16 bit number of each char. Is ...
1
vote
0answers
58 views
Variance of chain length in hashtable
I have a hashtable with length $m$. Initially it's empty. Next, $n/2$ unique random numbers $\in [0, n]$ are added to it.
What would be variance of chain length when such $n/2$ numbers are being added ...
0
votes
0answers
21 views
Is this example in Skiena's Algorithm Design Manual correct?
i think the above is incorrect; specifically, i think H isn't bijective. say our alphabet is the lowercase letters [a-z] and ...
-2
votes
2answers
37 views
1
vote
1answer
30 views
Size of order-preserving minimal perfect hash family
Suppose we have a universe of $u=|U|$ elements. We called a set of $H$ function $(U,m)$ order-preserving minimal perfect hash family (OPMPHF) if for every subset $M\subset U$ of size $m$ has at ...
0
votes
3answers
74 views
What is the best hash functions for millions of String keys?
I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value.
The problem that the retrieval process is too slow and I want to ...
1
vote
2answers
38 views
Theoretical question about Zobrist hashing and chances of collision with slight modification
I have a hash table that uses zobrist hashing to calculate the hash for various positions. The hash table is used to look up various transpositions. For some positions I do not want to allow any ...
0
votes
0answers
45 views
Hashing algorithm which minimizes distribution
Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
0
votes
0answers
15 views
Are elements of the Hash Table's backing array Linked Lists from the initial point when using Separate Chaining?
As usual, did quite a research in different books and academic articles, but can't really get a clear picture.
For the Hashing Collision resolution in Hash Tables, we have one very popular strategy ...
2
votes
1answer
52 views
How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?
Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental information it ...
2
votes
2answers
47 views
Rolling hash hacking
The hash value of a string $s$ is given by
$$
h(s) = \sum^{|s|}_{i = 1} s_i \cdot p^{|s| - i} \mod m; \text{ $m$ is prime, $m < 10^{12}$}.
$$
The string $s$, $p$, $m$ is given,
$|s| \le 14$, ...
0
votes
1answer
81 views
Separate Chaining hashing: time complexity of successful search
In a simple uniform hashing with chaining collision, the time complexity of a successful search is: $Θ(1 + (1 + \frac{α}{2} - \frac{α}{2n}))$ where $α=\frac{n}{m}$, but I don't understand how to ...
0
votes
1answer
27 views
Formal definition of hash function
I was reading through the classic CLRS with the intention of reviewing the hash tables theory, more specifically the hash function definition I just wanted a reference to quote.
I cannot find a ...
0
votes
0answers
20 views
How to generate unique keys for different two dimensional matrices having different sizes?
No. of rows in the table (as given in image) is not known beforehand . The problem I am dealing with generates different 2-D matrices based on the input data given. As soon as a matrix generates it ...
0
votes
0answers
29 views
Protecting a specific sized message with some limitations
So I make a research on my own. I have a device it allows a 64bit message. I wanted to secure it but I 64bits arent just enough to hash it and encrypt it. Is there really any good Hash function out ...
0
votes
0answers
22 views
Hashfunction for unique character distributions
The original problem is given a large input file, with n input lines of random string, find the number of pairs-> meaning same number and type of characters, in the file. Constraint on type of ...
3
votes
1answer
65 views
generalizing ball-bin problem to k-universal family
I am trying to solve a question in the book on Probability and Computing by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal ...
0
votes
1answer
30 views
Primary clusting in linear probing coliision resolution: there can only be one cluster/block, right?
I believe primary clustering is a problem with the linear probing method of hash collision resolution. But the description makes it sound like there can be multiple clusters of contiguous blocks. I ...
1
vote
2answers
63 views
Looking for memory-efficient way to detect hash collisions
Given a hash function H, it's possible that H(a) = H(b) = c
Let's assume we have a big data set [N1 ... Nk], with K items and we hash each item in this set
After operation is done, we'd get a set of ...
3
votes
1answer
57 views
Efficiently extendable hash function?
I'm wondering whether there exist any good hash functions with the following property: Assume that $x$ is some string over some alphabet $A$, then given $H(x)$ we can compute in $O(1)$ time both $H(ax)...
3
votes
1answer
107 views
Choosing an independent hash function, given hash function value
Supposed we have a function $h:U\to [m_1]$. Given this hash function, can we generate without using randomization or a universal hash collection another hash $h':U \to [m_2]$, which depends on $h$ ...
0
votes
1answer
27 views
Pairwise hash functions that are independent from each other
Is there there a way to build a collection of universal hash functions $H=\{h| h:U\to D \}$ where the values of two hash functions are independent one from another? i.e., $\Pr_{h_1,h_2\in H}(h_1(x)=y ...
0
votes
1answer
37 views
0
votes
2answers
401 views
Hash function to return only positive number from integer
What would be a good hash function that will return a positive integer value, even if the key is an negative integer value? How do I pick a hash function? So what I would want is to associate negative ...
1
vote
2answers
80 views
Are hash functions one-way?
I have heard that we can convert any text to hash code , but hash code can't be converted back to text without brute force.
Suppose we consider the text "mal". The hash codes of the ...
0
votes
0answers
9 views
Creating a specific hash setup
While solving a practice exam, this is the question I could not answer. Any help is appreciated. I am new to hashing and have no idea how to solve this question.
Let $H$ be a $(0.15, 0.85, 0.9, 0.1)$-...
2
votes
3answers
100 views
How can I create 10-character, unique codes with no collisions, but without being predictable?
If we are using numbers and letters, there are $36^{10}$ unique combinations. Collision is already unlikely, but I need it to be impossible, so using hashing is out of the picture(?).
The use-case is ...
5
votes
4answers
170 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 ...
2
votes
0answers
24 views
String to small integer mapping without collision
Is there any good approach to devise a mapping of limited number of strings $N_1 << 2^{15}$ to integers less than $2^{15}$ without conflicts?
Strings are quite often of the form of prefix + ...
0
votes
1answer
25 views
vector hashing function having collisions for permutations
let's consider vectors in space dim=3 and values {0,1,2,...,99} on each dimension I would like to create hash function but with special trait: collisions only for ...
0
votes
0answers
17 views
Why did Wegman-Carter call their class of hash functions as universal on their seminal paper
Wegman-Carter on their seminal Universal classes of hash functions uses the term universal for their definition. They gave this definition as:
Let $H$ be a class of functions from $A$ to $B$. We ...
0
votes
0answers
40 views
How can I hash an attributed graph?
I am interested in solving the following problem using a learning to hash algorithm:
I've got several attibuted graphs (a graph with node and edge labels - you can think about that as a description ...
1
vote
0answers
78 views
How can I choose good hash function for PCY algorithm
As far as I understand from PCY (Park, Chen, and Yu) algo is that the algo uses hashing during the first pass to reduce the number of CANDIDATE pairs that are considered in the second pass. I have 2 ...
1
vote
2answers
59 views
What does “prime” mean in this context?
In a lecture video the instructor introduced the quadratic probing method for hash tables. The formula he gave was the following:
$h(k,i) = (h'(k) + c_1 + c_2i^2)$ $\% M$
where $h'$ was h "prime". ...
-1
votes
2answers
56 views
Can data be compressed through this hash function technique?
I'd like to know if this data compression scheme would work or not, and why:
Suppose we have a file. If we treat the bits that make up the file as the binary representation of a number n, we have n (...
1
vote
0answers
70 views
A tree-like data structure with rights delegation for distributed computing
Every actor can create a root node and delegate a right to add a child node. Every node contains name of its’ creator or who added it, and value S. Sum of all values S at the same level of the tree ...
3
votes
3answers
604 views
Simple Uniform Hashing Assumption and worst-case complexity for hash tables
Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is O(1)?
It says in the Wikipedia article that this assumption implies ...
2
votes
2answers
156 views
Universal hashing function probability
Can somebody explain the following:
U is a universe of keys, and H is a finite collection of hash functions mapping U to {0, 1, … , m-1}.
I do not understand definition 2, and thus why amount of ...
1
vote
0answers
24 views
Is there a good way to hash abstract binding trees?
The hash function should be invariant under alpha-renaming. Using de Bruijn notation seems to be possible, but it requires alpha-converting the whole tree when a binding is created, and has the ...
0
votes
0answers
34 views
Construction of hash function with a given distribution
Two questions about the construction of a hash function:
Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "...
3
votes
1answer
87 views
Fast hash function for set equality
I'm searching an hash function for integer set equality that must be fast.
It must support update (adding an element already in the set must not change the hash) and union.
MinHash has these 2 ...
