Applications of Congruences
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
February 11, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 4d MdH W22 February 11, 2022 1 / 9
Hashing Functions
Hashing Functions
A hashing function h assigns memory location h(k) to the record that has
k as its key.
• Assigns memory locations to computer files.
• A common hashing function is h(k) = k mod m, where m is the number of memory locations.
• As this hashing function is onto, all memory locations are possible. • If there is a collision, next available location is assigned.
• This linear probing function can be used to look for the first free memory location.
h(k, i) = h(k) + i mod m, where 0 ≤ i ≤ (m − 1).
Md. Hasan (uOttawa) Discrete Structures 4d MdH W22 February 11, 2022 2 / 9
Pseudorandom Numbers
Pseudorandom Numbers
The linear congruential method is one commonly used procedure for generating pseudorandom numbers. Four integers are needed: the modulus m, the multiplier a, the increment c, and seed x0, with 2≤a