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

Filter by
Sorted by
Tagged with
-2
votes
2answers
37 views

Calculating efficiency?

A program must construct and then use a set $S$ of 1000 integers. ...
1
vote
1answer
21 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
2answers
42 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 ...
0
votes
2answers
67 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 ...
1
vote
2answers
36 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
44 views

Hashing algorithm which minimizes distribution

Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
2
votes
1answer
46 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
33 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
0answers
13 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 ...
-1
votes
0answers
18 views

What is the benefit of using seeded hashes with blockckain?

I'm a student and my supervisor asked me to use seeded hashes with blockchain.I want to know what is the benefit of using seeded hashes with blockchains.. and how it affects the security of the ...
4
votes
1answer
468 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 ...
0
votes
1answer
45 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
25 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 ...
5
votes
2answers
2k views

Hash size: Are prime numbers “near” powers of two a poor choice for the modulus?

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
1answer
40 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 ...
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
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 ...
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 ...
3
votes
1answer
57 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
25 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 ...
70
votes
5answers
54k 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 ...
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)...
0
votes
2answers
253 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 ...
3
votes
1answer
106 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$ ...
7
votes
1answer
196 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
1answer
364 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
0
votes
1answer
24 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
33 views

Computing hash of a compound key

Why is the initial value of hash 17 and not 0? ...
1
vote
3answers
543 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 ...
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 ...
1
vote
2answers
79 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)$-...
5
votes
4answers
159 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
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
39 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
69 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
21 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". ...
3
votes
1answer
68 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 ...
1
vote
0answers
68 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
votes
2answers
54 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 (...
2
votes
2answers
137 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 ...
2
votes
1answer
52 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 ...
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
58 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 ...
3
votes
1answer
82 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 ...
4
votes
1answer
71 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
2 3 4 5