# 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

274 questions
Filter by
Sorted by
Tagged with
68 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 ...
29 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 ...
64 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$, ...
38 views

### Calculating efficiency?

A program must construct and then use a set $S$ of 1000 integers. ...
34 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 ...
50 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 ...
45 views

### Hashing algorithm which minimizes distribution

Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
395 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 ...
56 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 ...
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 ...
51 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 ...
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 ...
24 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 ...
110 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 ...
48 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 ...
69k 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 ...
59 views

62 views

### Computing hash of a compound key

Why is the initial value of hash 17 and not 0? ...
1k 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 ...
27 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 ...
86 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 ...
235 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 ...
26 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 + ...
163 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 ...
62 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". ...
80 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 ...
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 ...
81 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 (...
267 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 ...
152 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 ...
32 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 ...
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$ "...
76 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 ...
95 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 ...
84 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 ...
564 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 ...
78 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. ...
176 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 ...
73 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 ...
180 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$ ...
98 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 ...
2k views

### Finding hash of a substring $[i, j]$ in $O(1)$ using $O(|S|)$ pre computation

Given a string $S$ of length $n$ characters, is it possible to calculate the hash of its substring $[i, j]$ (from index $i$ to $j$, both inclusive) in $O(1)$ using some form of precomputation? Can we ...
320 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 ...
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 ...
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)) \...