Hash functions:
Remainder treats the input string (byte sequence) like a base-256 number, and then takes that modulo m. m should be a prime, not too close to a power of 2. Note that if the keys are already numbers, then you just take them mod m and you’re done.
Multiplicative multiplies the return of the remainder hash by a floating-point constant, takes the fractional portion of the result, and then multiplies that by m and rounds it down (resulting in a value between 0 and \(m-1\)). The multiplier \(A\) has an effect on how well the algorithm performs. (I don’t expect you to memorize the multiplier we used.)
If we have two different hash values then we know that their keys must be different. If we have two identical hash values then we don’t know anything, because collisions (different keys that hash to the same value) are possible.
Handling collisions:
Chaining: keep a linked list in every table entry, just add colliding entries to the list.
Open addressing: if an entry is full, look for an open entry somewhere else in the table, using a probe sequence. Linear probing looks in the next entry, quadratic probing looks in the \(a_0 i + a_1 i^2\) entry, double-hashing looks in the \(\mathrm{hash}_0(k) + i \mathrm{hash}_1(k)\) entry.
The load factor \(\alpha\) of a hash table is the ratio of elements stored \(n\) to \(m\), the size of the table. With open addresses, the maximum load factor is 1.0.
Hash functions should be
Deterministic: always hash a particular key to the same value
Fast (normally)
Well-distributed over the range m. No hash value should more dramatically more common than any other.
Amplify small differences in keys (avalanche effect)
Expression trees
Data structure for encoding the (recursive) structure of various kinds of expressions. (Each kind of expression will have its own expression tree type.) We build expression trees using inheritance: we have a base class for “all expressions of this type” and then subclasses for particular types of subexpressions. E.g., in arithmetic expressions, we have
Numbers
Variables
Unary minus
Infix operators
Parentheses
We definitely need a subclass for the first four, and maybe a fifth for parentheses, depending on what we are doing. (We might even choose to split the different infix operators into different subclasses.)
Example: A ring is a mathematical structure consisting of a set of values a, b, c, etc. together with two operations:
+a binary operation*a binary operation
and two identified elements
0, the identity for+and1, the identity for*
(Parentheses are also allowed.)
An expression tree structure for general rings would need:
A node for elements in general
A node for 0
A node for 1
A binary node for
+A binary node for
*
A sketch of this would be something like
struct ring {}; // Base class
struct ring_elem : public ring { string e; };
struct ring_zero : public ring { };
struct ring_one : public ring { };
struct ring_plus : public ring { ring* left; ring* right; };
struct ring_mult : public ring { ring* left; ring* right; };
(If I ask you to do this on a test, you don’t need to worry about constructors or methods.)