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
1 answer
26 views

Sampling unique records from a large dataframe

Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe? Some sort of sampling algorithm?
user avatar
0 votes
1 answer
35 views

Universal family of hash functions — dependent on table size?

Given the following family of hash functions: $$ \mathbb{H} = \{h_c(x) = (12x + c) \bmod m \mid c \in \mathbb{N} \}, $$ where $m$ is the key size. Prove that $\mathbb{H}$ is not a universal ...
user avatar
-5 votes
1 answer
74 views

Implementing Flajolet–Martin algorithm in Python

I am stuck on what to do. I am trying to create a simple implementation of the Flajolet–Martin algorithm using Python. The stream will be the contents of a text file and you will produce an ...
user avatar
1 vote
2 answers
59 views

the load factor in hash table

What is numerically the best value or range of values used as a reference for the load factor used in the hash table? What is the pseudo-code of the “rehashing” method, which is applied when many ...
user avatar
  • 11
1 vote
1 answer
42 views

Hash / Compression algorithm to shorten text?

I desperately need a hash / compression function that is suited to shorten text. The context is this: I want to bring order and sort my box with hundreds of charging adapters (duh). After I determined ...
user avatar
0 votes
1 answer
88 views

Consistent Hashing Algorithm Without Distribution / Load Balancing

I need some help finding or creating a consistent hashing algorithm with the following properties: Given N buckets, only distributes keys to bucket N. When number of buckets are increased from N to N+...
user avatar
1 vote
2 answers
56 views

Averege time complexity of open addressing

I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the ...
user avatar
1 vote
0 answers
36 views

Where does 2^32 come from with bitcoin?

Several months ago I was doing research into calculating mining revenue for several crypto currencies. When trying to calculate BTC revenue I found this value 1/2^32 which was described somewhere ...
user avatar
  • 51
2 votes
1 answer
50 views

How do these Crypto terms relate to each other and what do they all mean?

Alright this is another day of my pursuit to learn about how crypto works. I have several terms that I have found linked together. I was trying to do research on how the Target Hash is determined and ...
user avatar
  • 51
0 votes
2 answers
38 views

What happens in the event of a collision in a crypto hash function?

I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of ...
user avatar
  • 51
1 vote
0 answers
20 views

Algorithm Complexity Question

this is my first question on this site and I would like to preface this by saying I am not very savvy when it comes to Computer Science. So, I will try to ask this the best I can. I was doing some ...
user avatar
  • 51
1 vote
1 answer
22 views

Locality Sensitive Hashing for Sets

Are there locality sensitive hashes that work nicely with sets? Each set would get a hash, the order of the elements in the set does not change the hash, and sets that share more elements are closer ...
user avatar
2 votes
1 answer
37 views

Splitting the output of a wide hash in lieu of multiple independent hashes

Certain algorithms require two independent hash functions. An optimization I've seen is to split the output of a wide hash function and use the parts instead of the two independent hash functions of ...
user avatar
1 vote
1 answer
60 views

Optimal parameters for a Bloom filter

My first question here. Please do not judge me much if this is a too simple. Some text consists of $n=12\,500$ distinct words. I would like to construct a Bloom filter with $\epsilon=10^{-2}$ ...
user avatar
  • 125
0 votes
1 answer
22 views

Confused about the appropriate slot in linear probing

The following paragraph is from the book CLRS: Given an ordinary hash function $h' : U \rightarrow \{0, 1, ..., m - 1\}$, which we refer to as an auxiliary hash function, the method of linear probing ...
user avatar
  • 377
1 vote
1 answer
31 views

Fingerprint functions for set equality checks?

Given I have two sets of objects $A =\{a, b, c\}$ and $B = \{a, b, c, a\}$ Based on the set equality, I want the fingerprint of these sets to be the same $F(A) = F(B)$. Additionally I want to be able ...
user avatar
  • 123
2 votes
1 answer
53 views

Analysis of a calculation of expected number of collisions in hashing

For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...
user avatar
0 votes
0 answers
70 views

Proving a universal family of hash functions (Xor)

Problem: Let $U = \{0,1\}^d$ be all the bitstrings of length $d$. For every $a \in U$ define the function $h_a : U \to \{0,1\}$ with $$h_a(x) = (a_1 \land x_1)\oplus(a_2 \land x_2) \oplus \dots \oplus(...
user avatar
0 votes
1 answer
49 views

Finding a hash function, so that the set of hash functions is universal

Problem: Let $U = \{0,1,2,3,4,5\}$ be a universe of keys and $T = \{0,1,2\}$ we observe follwing 5 hash functions which map from $U$ to $T$ : $$h_1(x) = (x+1) \mod{3} \hspace{5mm} h_2(x) = (x+2) \mod{...
user avatar
0 votes
1 answer
71 views

How do i delete one single unequal element from an array of equal elements without using hashing?

The rules of the question state that: Only one element is different. Rest are all same. Array A size is 8. I need to find the different element and remove it (Hashing cannot be used). I have not ...
user avatar
1 vote
1 answer
50 views

How to efficiently see if a value is in a set

I was curious is there a really efficient way to see if a value is in a set? This question comes from me thinking about youtube views. As far as I understand youtube view count goes up for every ...
user avatar
  • 113
3 votes
1 answer
49 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, ...
user avatar
  • 1
1 vote
1 answer
58 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. ...
user avatar
  • 11
1 vote
0 answers
45 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 ...
user avatar
1 vote
1 answer
61 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 ...
user avatar
0 votes
1 answer
27 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 ...
user avatar
  • 35
1 vote
0 answers
44 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 ...
user avatar
  • 11
0 votes
1 answer
243 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 ...
user avatar
  • 101
1 vote
0 answers
31 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 ...
user avatar
  • 377
2 votes
1 answer
118 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-...
user avatar
  • 459
0 votes
0 answers
32 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 ...
user avatar
  • 459
1 vote
1 answer
103 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}...
user avatar
  • 459
0 votes
1 answer
28 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 ...
user avatar
  • 35
0 votes
0 answers
19 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 ...
user avatar
  • 459
1 vote
1 answer
148 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 ...
user avatar
  • 459
1 vote
1 answer
77 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....
user avatar
  • 35
1 vote
1 answer
63 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 ...
user avatar
  • 459
0 votes
2 answers
69 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 ...
user avatar
  • 35
2 votes
0 answers
79 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 ...
user avatar
  • 459
1 vote
2 answers
364 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,...
user avatar
  • 459
1 vote
1 answer
52 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)$ ...
user avatar
  • 459
0 votes
0 answers
36 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 ...
user avatar
  • 459
6 votes
1 answer
346 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 $...
user avatar
  • 63
2 votes
0 answers
23 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&...
user avatar
  • 258
0 votes
1 answer
33 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 <...
user avatar
  • 175
1 vote
1 answer
38 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 ...
user avatar
4 votes
1 answer
169 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 ...
user avatar
1 vote
1 answer
19 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.
user avatar
  • 63
2 votes
0 answers
43 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 ...
user avatar
0 votes
0 answers
20 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, ......
user avatar

1
2 3 4 5
7