Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- SquareHash(S, u)
- Input: A set S of N items, an integer u such that
- each item is in {0,1, ... , u-1}
- Output: A hash table of size N*N and a corresponding hash function
- 1. Initialize a table T of size N*N
- 2. While true
- 3. Pick a function h uniformly at random from a universal family H
- that maps {0,1, ... , u-1} to {0,1, ... , N*N-1}
- // Assume that this can be done in O(1) time
- 4. Insert all the elements of S into T using h as the hash function
- 5. If T has no collisions, return (T,h). Otherwise empty T
Add Comment
Please, Sign In to add comment