Stack Overflow
Stack Overflow

Questions tagged [universal-hashing]

The main idea behind universal hashing is to select the hash function at random from a carefully designed class of functions at the beginning of execution

Using universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical property (see definition below). This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary. Many universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient. Universal hashing has numerous uses in computer science, for example in implementations of hash tables, randomized algorithms, and cryptography.

See more on wikipedia.com

27 questions
11
votes
2 answers

How to generate 64 bit random numbers?

I'm implementing universal hashing and using the following universal hash function : h(k)=((A*k)mod 2^64) rsh 64-r where A is a random number between 2^61 and 2^62. The rand() function in C++ has return type integer and it can't generate that…
Ahmed
  • 2,176
  • 5
  • 26
  • 40
10
votes
4 answers

Hash a Range of Values

I know that I can hash singular values as keys in a dict. For example, I can hash 5 as one of the keys in a dict. I am currently facing a problem that requires me to hash a range of values. Basically, I need a faster way to to do this: if 0 <= x <=…
inspectorG4dget
  • 110,290
  • 27
  • 149
  • 241
8
votes
1 answer

Hashtable- Rehashing

I have been told that Hashtable in .NET uses rehashing in order to reduce/avoid collision. Ie. “Rehasing works as follows: assume we have a set of hash different functions, H1 ... Hn, and when inserting or retrieving an item from the hash table,…
s_nair
  • 812
  • 4
  • 12
5
votes
2 answers

Ultra fast lookup in small sized container of 64-bit integer values using dynamic perfect hashing

I have input keys that can cheaply be converted to a uint64_t (ie, the input contains less than or equal to 64 bits). Each unique key (not yet in the map) will be assigned some data (a pointer to an object). Much like a std::map…
Carlo Wood
  • 5,648
  • 2
  • 35
  • 47
4
votes
1 answer

Basics in Universal Hashing, how to ensure accessibility

to my current understanding Universal Hashing is a method whereby the hash function is chosen randomly at runtime in order to guarantee reasonable performance for any kind of input. I understand we may do this in order to prevent manipulation by…
Beltrame
  • 147
  • 5
3
votes
1 answer

Is Universal family of hash functions only to prevent enemy attack?

If my intention is only to have a good hash function that spreads data evenly into all of the buckets, then I need not come up with a family of hash functions, I could just do with one good hash function, is that correct? The purpose of having a…
Aravind
  • 3,169
  • 3
  • 23
  • 37
3
votes
1 answer

What is the difference between consistent hashing and cone hashing?

What I know is: Consistent hashing: uniform distributed storage system Cone hashing: non uniform distributed storage system I want to know: How it works? What is the use of it? What is the difference between this two types of hashing? I am not…
Hemanth Venkatappa
  • 39
  • 1
  • 1
  • 8
2
votes
2 answers

understanding Universal hashing chapter on CLRS

Hi I am reading the chapter about universal hashing on CLRS. On page 234 Corollary 11.4 Using universal hashing and collision resolution by chaining in a table with m slots, it takes expected time Theta(n) to handle any sequence of n INSERT,…
Alfred Zhong
  • 6,773
  • 11
  • 47
  • 59
2
votes
1 answer

Confusion related to universal hashing

I was reading this video lecture related to universal hashing. It shows the example of hashing IP addresses. Each IP address consists of 4, 32 bit integers, (x1,x2,x3,x4) with any xi having the maximum value of 255. The tutorial says that the size…
user12331
  • 486
  • 7
  • 22
2
votes
2 answers

Universal hashing misunderstanding

I am trying to understand how universal hashing works. It is defined h(x) = [(a*x + b) mod p] mod m where a,b - random numbers, m - size of hash table, x - key, and p - prime number. For example, I have several different keys: 92333 23347 20313 And…
Bob
  • 10,427
  • 24
  • 63
  • 71
1
vote
0 answers

Value of K hash functions so that probability of false positive is at most 1/n

We have n elements , m=2n and k, where K is the number of hash functions, m being the size of bit array and n the number of elements. What will be the value of k such that the probability of getting a false positive will at most be 1/n I am working…
Razor
  • 89
  • 9
1
vote
1 answer

Pairwise independent hash functions in Java

I'm looking for a quick and easy way to use a (universal) family of pairwise independent hash functions in my Java projects. Ideally, I would have some object UniversalFamily (representing the Family) which would return me objects with a method…
PlsWork
  • 1,958
  • 1
  • 19
  • 31
1
vote
1 answer

cmph Minimal perfect hashing

I've spent days trying to make the library work on my system. The library has several algorithms which generate MPHFs. My understanding of minimal hash function is, that when I hash two distinct keys using the MPHF, they'll return two different…
truth_seeker
  • 345
  • 4
  • 14
1
vote
0 answers

How can I check file differences in JavaScript?

I'm using Electron, Githubs desktop framework built using JS and HTML 5. I need to check if fileA is different to fileB, and similarly with 2 strings. These files and strings could be of equal size but be different. They could be small (2-3 bytes)…
Mike
  • 8,767
  • 8
  • 49
  • 103
1
vote
0 answers

Choose the universe of keys

I need to hash a sequence S of numbers of length n^2 where each number is a sum of two numbers each of them is an element on one of the sequences: {x_1,..., x_n},{y_1,..., y_n}. I am using universal hashing so the question is how do I find the…
tmac_balla
  • 648
  • 3
  • 16
1
2