CS 201 - 10/30/14 Don't forget about advising!!!! Q1. Stacks versus Queues Q2. Grow Dynamic Array Q3. Linked List Insert in Order Q4. Delete value X from the linked list Hash Tables 2 primary apporaches 1. Open hashing, Hash Tables with chaining 2. Closed hashing We use an array to store the data items, We rely on the random access abiliy of the array to make the operations run fast. We want the array to mostly be empty We rely on a "hash function", the has function maps each data item to the location in the array. di = data time pos = array postion where this data item is to be stored pos = hashFunction (di.key) ; array[pos] = di; // hash table store operation diAccess = array[pos] // hash table access operation When two data items are hashed to the same position in the array, we get a "Collision" Collisions are BAD #collisions = 1/emptiness-of-the-array The larger the number of empty array position the lower the number of collisions. A super simple hash function. 1. we are storing integer values (or using and integer value as the key) For the Student example, the student's UIN could be the key. 2. Assume we are using a array of size M the hash function could be: UIN % M % is remainderr from integer division Assume I have a hash of size 500, struct hashTableData { int key; char name[30]; } struct hashTable { hashTableData *darr; int size; } init (hashTable* ht, int sz) { ht->darr = (hashTableData *) malloc (sz * sizeof(hashTableData) ); ht->size = sz; } /* DOES NOT HANDLE COLLISIONS */ add (hashTable *ht, hashTableData data) { int pos = data.key % ht->size; /* store the data in the array */ ht->darr[pos].key = data.key; strcpy (ht->darr[pos].name, data.name); } NOTE: when a collisions, we overwrite the first stored information with the second stored informatin. So the above is flawed. If we use an Open hash Table (Hash Table with Chaining) we have a simple solution for collisions. At each location in the array we would have a linked list of data items instead of a single data item. The add operation would just store the new item into the linked list