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
231
questions
0
votes
0answers
17 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
27 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
20 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 ...
-1
votes
0answers
8 views
inserting keys into initially extendible hashing data structure does or how its affected differently? [closed]
In one of my books that I'm reading for fun it has a question which says Show the result of inserting the keys 10111101, 00000010, 10011011, 10111110, 01111111, 01010001, 10010110, 00001011, 11001111, ...
3
votes
1answer
56 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
18 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 ...
0
votes
1answer
35 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 ...
2
votes
1answer
53 views
Static Perfect Hashing - FKS
I am trying to understand perfect hashing aka FKS, but I have a few questions.
From my understanding, perfect hashing is a two level hashing in which you take a hash function from a universal family ...
3
votes
1answer
56 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
104 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
21 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
32 views
0
votes
2answers
158 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
77 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 individual ...
0
votes
0answers
8 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)$-...
0
votes
3answers
76 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
146 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
23 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
24 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
38 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
63 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 ...
0
votes
0answers
19 views
When to apply a probe sequence when inserting an element to a hash table
So, if we start out with an empty table with M elements. Do we always need to have a specified hash function say $h(x) = x \% 8$ as well as a specific probing sequence to use when inserting a ...
1
vote
2answers
58 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
52 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
67 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 ...
1
vote
3answers
423 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
119 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
22 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
75 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 ...
2
votes
1answer
40 views
Given a family of hash functions in table form, how can I know whether it's universal?
I've been given the following two families of hash functions:
H
and
G
Each family has three functions $\{0,1,2,3,4\} \to \{0,1,2\}$ that can be seen in the tables above. For each family I need to ...
0
votes
0answers
18 views
Time complexity of website access analysis using Hash Tables
I would like to calculate the time complexity of an algorithm which returns the number of accesses of a website and the number of different users who entered. Each user is represented by a unique ...
0
votes
1answer
148 views
is modulo of hash function is evenly distributed?
if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed?
so if I have a histogram of values [0,N-1] will the ...
4
votes
1answer
68 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 ...
1
vote
1answer
70 views
are they any implications if i reduce a sha256 result into 248 bits?
i am working a prototype using some cryptographic properties.
the question is simple but perhaps deep enough for me to decide :
sha256 is a strong hash function, but i have space for 248 bits only.
...
3
votes
1answer
55 views
The expectation of the total number of pairs of keys in a hash table that collide using universal hashing
I am reading CLRS relating to perfect hashing. When computing the
$$
\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]
$$
where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...
4
votes
1answer
99 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 ...
2
votes
1answer
143 views
Compute hash value according to multiplication method
In "Introduction to Algorithms" by C. E. Leiserson, R. L. Rivest and C. Stein (ISBN: 978-0262033848), p. 264 they state this:
I get everything but the last part stating $h(k) = 67$
...
3
votes
1answer
62 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 ...
0
votes
2answers
61 views
Hash function orders ships from closest to furthest from the origin
Suppose we have a circular radar that scans for ships in an area enclosed by $x^2+y^2 \leq z^2$ (a circle).
We wish to design a hash function $h$ such that, we can order the $n$ ships from closest to ...
2
votes
2answers
127 views
O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible?
Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem.
If
s = little string and S = len(s)
b = big string and ...
0
votes
0answers
34 views
Search operation in hash table
Suppose that we have a hash table of some size $s$ and we have a set of keys $K$. We decide to hash the keys using chaining.
Now assume that we randomly select $k \in \mathbb{N}$ keys from $K$ and ...
3
votes
1answer
95 views
Small space hash functions that are weakly but not strongly universal
This is a follow up to this this question about weakly universal hash functions
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)) \...
3
votes
1answer
349 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 ...
1
vote
0answers
45 views
What is a minimal, pseudo-random hash function?
I want to generate pseudo-random hashes of inputs in a way that is optimally time and space efficient.
I'm not at all concerned about security. The output should be evenly distributed and appear ...
0
votes
1answer
262 views
Hash table open addressing without dummy
If a hash table is using open addressing as the collision resolution strategy, then during deletion, we mark that slot as dummy.
I understand the reason behind ...
0
votes
1answer
99 views
My professor claims that inserting the same key into a hash table again will lead to a collision … – Is he really right?
My whole life I thought
a collision is a situation that occurs when two distinct pieces of data have the same hash value.
Everything looks a little bit different now: A few days ago we had to ...
5
votes
1answer
231 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 ...
0
votes
2answers
122 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 ...
