CSE 100 Study Guide - Quiz Guide: Pseudorandom Number Generator, Hash Table, Linear Probing

• School: UCSD
• Department: Computer Science & Engineering
• Course: CSE 100
• Professor: Nuno Bandeira

Document Summary

A hash function can be described by the following two properties. Property of equality: given two keys k and l, if k and l are equal, h(k) must equal h(l). Property of inequality: given two keys k and l, if k and l are not equal, it is best if h(k) was not equal to h(l). The running time of the hash function must be independent of the number of elements in the hash table, but might might not be independent of the size of the data you are hashing. Hash tables in general have and average-case time complexity of o(1) Analysing the probability of collisions: p(event) = 1 - p(no event) Load factor = number of keys store (n)/ number of slots in the hash table (m) Can avoid collisions by choosing the capacity of the hash table to be a prime number. For tst, the order of insertion affects the structure of the tree.