SE250:April 3

Minutes

Minute Taker: jpar277

Wrapped up the rest of the Linked Lists. Copy, Append are the hardest code for Linked Lists, we're expected to understand them but not expected to produce them under exam conditions. We should have a good grasp of going through a Linked List 1 by 1 and knowing when to refer to the head and when to refer to the tail. We should also be able to draw a Linked List diagram and relate it to code.

Hashing ::::

Hash Tables are basically an Array with Linked Lists as the elements in the Array.

Hashing is a technique that allows very fast access to a collection of objects indexed by a key (e.g. student ID, UPI) that is used as a unique index. No two values have the same key.

An Array is "almost" this structure, where the key is a small integer.

object array [ ] array [ key ] -- this is a mapping from key to object.

Having a small integer as the key is not always convinient.

Hashing "magically" removes the small integer restriction, at almost no additional cost.

Code Example ::::

typedef char* key_t;
typedef double value_t;

typedef struct Cell {
	key_t elt;
	value_t value;
	struct Cell* next;
} Cell;

typedef struct {
	int size;
	Cell* table;
} HashTable;

void add (HashTable* ht, key_t key, value_t value) {
	//      ^^^ we want the reference and not the whole thing - hence the star
	int i = hash(key);
	// resize the table if necessary
	ht->table[i % ht->size] = cons(key, value, ht->table[i % ht->size]);
}

value_t loopup (HashTable* ht, key_t key) {
	int i = hash(key);

	for(cp = ht-> table[i % ht->size]; cp != nil; cp = cp->next)
		if (cp->key == key)
			return cp->value;

	return 0;
}

Hash is a function that we must define and it must be fast.

Cheaper to compare 2 ints than 2 strings.