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
1
vote
2answers
401 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 ...
3
votes
1answer
37 views

A question about hash problems in CLRS book

Consider the following problem 11.2-6 from CLRS book: Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, ...
1
vote
1answer
32 views

A hash function for a 2D hash table with a scattering property?

I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. ...
0
votes
1answer
16 views

Detecting and correcting collisions in (Zorbist) hashing to avoid errors in transposition table

Context Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions. The table has a finite recycled memory (key % p is the <...
1
vote
0answers
41 views

Finding a full collision within a large array

I apologize for the vagueness of the title, but this question is quite difficult for me to describe. For that reason, I'm unable to directly convey my problem. In an effort to circumvent this, I've ...
1
vote
0answers
39 views

Check if string contains pattern (with respect to one-to-one symbols mapping) [closed]

I'm trying to solve following problem: Check, if the string contains substring, that can be obtained from pattern using one to one lower case symbols replacement (using bijection between original ...
0
votes
1answer
76 views

hash-tables - Expected-time for an unsuccessful search

The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c. Suppose you have a hash table where the load-factor $\alpha$ is related to the number $n$ of elements in the table by ...
3
votes
1answer
90 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 ...
1
vote
1answer
50 views

Expected Lookup Length in Open Addressing Hash Table with Simple Uniform Hashing

In several proofs of the expected lookup length in an open addressing hash table, an assumption is made (which is said to follow from the "simple uniform hashing assumption": Given a hash ...
0
votes
1answer
125 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: ...
0
votes
1answer
18 views

What are the chances of hash collision given large input and small hash?

I have an input of 128 bits (binary, 0s and 1s) and want to hash this input with 32 bit CRC. But I am not sure if collision rate is moderate or too high ? Is it 2^128/2^32 = 2^98. And does that ...
1
vote
1answer
74 views

Can one brute force entries to create the whole file?

I want to know if one can brute-force a large list of entries (>10,00,000) in linear time to form a whole file. For example: I have an ebook and i extract all the words and symbols from that ebook....
1
vote
0answers
25 views

Average-case retrieval time

The book CLRS claims these statements before introducing the topic of universal hashing: If a malicious adversary chooses the keys to be hashed by some fixed hash function, then the adversary can ...
1
vote
2answers
91 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
1answer
53 views

Quadratic probing variant scheme

Suppose that we are given a key $k$ to search for in a hash table with positions $0, 1, \dots , m-1$, and suppose that we have a hash function $h$ mapping the key space into the set $\{0, 1, \dots , m-...
0
votes
0answers
17 views

A successful search takes $\Theta(1 + \alpha)$ time on average when resolving collisions by chaining

I would to discuss a proof found in CLRS book please. Theorem: In a hash table in which collisions are resolved by chaining, a successful search takes time $\Theta(1 + \alpha)$, on the average, under ...
1
vote
1answer
47 views

If $(h_2(k),m) = 1$ then $h_1(k)+ih_2(k) \bmod{m}$ is a permutation of $0,\ldots,m-1$

The following question appears in Introduction to Algorithms (CLRS): Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h_1(k) + ih_2(k)) \bmod{m}...
0
votes
1answer
26 views

Can possiblity of hash collision be "zero" when we hash same file in different formats?

Let's say I have a file A, which is any normal file (pdf, jpeg, mp3 etc.) Now I get the binary dump of file, say another file B{A}. And the hexdump of file say, file H{A}. Now I hash all the three ...
1
vote
1answer
43 views

Number of probes in a unsuccessful search in open address hashing

Theorem: Given an open-address hash table with load factor $α = n/m < 1$, the expected number of probes in an unsuccessful search is at most $1/(1−α)$, assuming uniform hashing. Let us define the ...
0
votes
2answers
61 views

Can 2 files have "same" "many" "different" types of hash?

I know that hash collision is possible with large number of files. But i want to know if 2 files can share "many , different" types of hash. I have 2 hashes SHA256 and BLAKE256 (Both will ...
0
votes
0answers
17 views

Prove that if $k$ was the $(i+1)$st key to be inserted into the hash table, then $E[probes(k)]=\frac{1}{1-\frac{i}{m}}$

Theorem: Inserting an element into an open-address hash table with load factor α requires at most $1/(1 − α)$ probes on average, assuming uniform hashing. By following unsuccessful search strategy, we ...
1
vote
1answer
56 views

Prove that the expected length $E [n_{h(k)}]$ of the list containing key $k $ is at most $1 + \alpha$

Theorem: Suppose that a hash function $h$ is chosen from a universal collection of hash functions and is used to hash n keys into a table $ T$ of size $m$, using chaining to resolve collisions. If key ...
2
votes
0answers
55 views

Proving that a successful search of hash function is $\Theta(1+\alpha)$

Question: Prove that successful search of hash function with chaining (list at each slot) takes $\Theta(1+\alpha)$. Given a dictionary or hash table that has a chain at each slot in case we have a ...
2
votes
2answers
236 views

Implement a dictionary by using direct addressing on a huge array

For the following question from Introduction to Algorithms book, "We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage,...
1
vote
1answer
44 views

Why we get at most $N^2$ probe sequences using double hash function

Question:Given the following double hash function: $$h(k,i) = (h_1(k) + i\times h_2(k)) \bmod{N}$$, where $h_1(k): key \to \mathbb{Z}$. $h(k,i)$ can generate $N^2$ probe sequences at most and $h_2(k)$ ...
0
votes
0answers
34 views

Prove that Horner's method produce only 6 collisions on 50000 English words

Polynomial for producing hash values: $p(z)=a_0+a_1z+\cdots, a_{n-1}z^{n-1}$ Honor's method for that polynomial: $$ p_0(z)=a_{n-1} \\ p_i(z)=a_{n-i-1}+zp_{i-1}(z), (i=1, \cdots, n-1)\\ $$ Problem: For ...
4
votes
1answer
552 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
4answers
242 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 ...
4
votes
3answers
159 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 ...
6
votes
1answer
261 views

Hashing using Horner’s Rule

When hashing a (key, value) pair where the key is a string, I have seen the following hash function in use: E.g. $c_n + 256c_{n-1}+ 256^2c_{n-2}+...256^{n-1}c_1$, where this represents the string $...
0
votes
1answer
67 views

Shuffling Bits For Uniform Distribution

I am writing a hashing algorithm to be used in the key-value data store. That is for each key the location of the data is determined. The structure of the data store is given a key, a value needs to ...
2
votes
0answers
18 views

Does there exist a locality sensitive hashing for $\ell_p$-norm distance where $p>2$?

It is well known that the $p$-stable distribution can be used to generate locality sensitive hash code for $\ell_p$-norm distance measure where $p \le 2$. However, it seems that the situation for $p&...
1
vote
1answer
33 views

Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to ...
4
votes
1answer
154 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
1
vote
1answer
16 views

Universal hash function for strings of unbounded length

Is there a (weakly) universal hash function for strings without any assumption of the string length? I did not find one on Google / Wikipedia.
2
votes
1answer
1k views

Sequential numbers to unique-looking numbers

I'm not sure how to word this because I'm not familiar with this, but I'm sure a process like this is rather common. Basically, I've got members signing up for our website, and each one is assigned a ...
2
votes
0answers
30 views

Finding the longest power subsequence

A power sequence is a sequence containing consecutive powers of a number starting from power one. for example $3^1, 3^2, 3^3$ is a power sequence. The question is to find the length of the longest ...
0
votes
0answers
17 views

Propose a family of hash functions with $mod p^2$ for some prime number $p$

I need to define a family H of universal functions $\{0,1, ..., p^k−1\} →\{0,1, ..., p^2−1\}$. Now based on a similar example I was thinking of something like: Given some $a= (a1, a2, ..., ak)∈\{0, ......
0
votes
0answers
19 views

Hash tables for storing data in an application that supports partial search

Is a hash table a good data structure for storing data in an application that support partial search such as "select * from MyTable where name like 'John%'. If not, what is? I would have thought ...
2
votes
1answer
116 views

Constructing 2-Universal Families

Let H be a class of all functions, mapping M possible keys to N integers. Is it true that H is a 2-universal family? Is it a good idea to use H in applications? I don't even know where and how to ...
0
votes
0answers
21 views

What is the order of magnitude of bitwise operations involved in a SHA-256 hash?

Specifically, how many bitwise operations (approximately, could be just order of magnitude) occur each time a Bitcoin ASIC miner performs a SHA-256 hash in typical mining computation, i.e. as it ...
0
votes
0answers
26 views

If the load factor is a decimal (say 3.6), what is the length of each chain in a hash table that utilizes separate chaining?

I understand that if the load factor were 2, then the length of the chain would be 2 for each index in the array, but what happens if the load factor is a decimal? Do we round up or down?
0
votes
2answers
547 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 ...
3
votes
2answers
78 views

Information on Tavori and Dreizin ranged hash function?

While doing some digging around in the GNU implementation of the C++ standard library I came across a section in bits/hashtabe.h that refers to a hash function "in ...
1
vote
1answer
50 views

How 'Avalanche Effect' got its name?

I wonder how or why Avalanche Effect got its name. Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (...
1
vote
1answer
50 views

Why mod operation can be used as hash function

I'm new here, and I'm currently trying to understand why mod operation can be used as a hash function. For example, consider the function $h(x)=x\mod 2^{256}$, where $x$ can be a string of any length. ...
1
vote
1answer
53 views

How to show independence and uniform distribution of hash codes from k-wise independent hash functions?

Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x_1, x_2,\...
4
votes
3answers
96 views

Integer set disjointness query on sketches with something like homomorphic hashing

Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. ...
1
vote
2answers
145 views

Hash functions producing uniform outputs

I've seen this question in a past exam paper, and I know that the answer given is (b), but I'm not sure why. Which one of the following hash functions on integers will distribute keys most ...
1
vote
2answers
225 views

Constraint on Universal set of hash functions

I was reading hashing from CLRS. In it author says: Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a ...

1
2 3 4 5 6