Guest User

Untitled

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