OutlineLast time:• Review of basic ADTs• PA1 Walk ThroughToday:• Continue PA1 Walk Through• Dictionary ADT• HashingSugih Jamin ([email protected])Dictionary ADTTable lookup: look up a key in a tableThe key is associated with some other information (value)Key space is usually more structured/regular than value space,so easier to searchAn entry is a <key, value> pairFor example: <title, mp3 file>Usually the ADT stores pointers to entriesSugih Jamin ([email protected])Searching for ItemsTwo types of search:• entry search: pointer comparison• key search: value comparisonTypes of dictionary:• unordered list• ordered list• unsorted list• sorted listWhat is the difference between an ordered and a sorted list?Adding entry to an ordered (sorted)list must retain the ordered (sorted) property of the listSugih Jamin ([email protected])RuntimeUnsorted list:• insert: O()• search: O()Sorted list:• insert: O()• search: O()Sugih Jamin ([email protected])Dictionary ADT Application: Implementing Function CallConsider:10 foo(){/* does something */}20 bar(){/* does something else */}32 main(){foo();bar();}How does main() know where foo() and bar() are?Sugih Jamin ([email protected])Symbol TableExample:Symbol Memory Location“foo” 10“bar” 20“main” 32Sugih Jamin ([email protected])Symbol TableSymbol table:• constructed by the assembler• maps symbols to binary addresses• used by the linker to resolve symbol references(perhaps across different object files)• used by the debugger to find where the symbols are% g++ -g a.ccThe -g option tells g++ to save the symbol tableOtherwise it will be removed to save disk spaceSugih Jamin ([email protected])Implementing Symbol TableWhich ADT to use for symbol table?How shall we implement this ADT?As array? As linked list?Sugih Jamin ([email protected])Implementing Symbol Table (cont)What operations are used with the symbol table?Time complexity of the different implementations:• array• linked listCan we do both of these operations in O(1) time?Sugih Jamin ([email protected])Hash Table and HashingReference items in a table (the hash table) by keysUse arithmetic operations to transform keys into table addresses (buckets)Hash function (h()): transforms the search key into a bucket• hash code: t(key) → intmapmaps the key (which could be a string, etc.) into an integer (intmap)• compression map: c(intmap) → bucketmaps the intmap into an address within the table, i.e.,into the range [0, M − 1], for table of size MGiven a key: h(key) → c(t(key)) → bucket/indexSugih Jamin ([email protected])Hashing Example and ComplexityExample 1: hash table of size 5, want to insert 4, 3, 6, 22How does insert (unordered) and search on a hash table work?What would be an example hash function?What are their time complexities?Example 2: hash table of size 4, want to insert 4, 3, 6, 22What to do with keys that hash into the same bucket?Moral: Pick a table size (M) that doesn’t havecommon factors with the keyPrime numbers are good candidatesSugih Jamin ([email protected])Hash FunctionsWebster:Main Entry: hashPronunciation: ’hashFunction: transitive verbEtymology: French hacher, from Old French hachier,from hache battle-ax, of Germanic origin; akin toOld High German hAppa sickle; akin to Greekkoptein to cut – more at CAPON1a : to chop (as meat and potatoes) into small piecesCriteria for a good hash function:• easy and quick to compute:o must compute a hash for every keyo must compute the same hash for the same key• should distribute keys evenly in hash table:o minimize collisionsSugih Jamin ([email protected])Hash Functions (cont)Common parts of hashing function:• truncation (hash code): remove parts common across keys, or extractbits from keys that are more likely to be unique acros keys. Examples:o 734 763 1583o 141.213.8.193o cello.eecs.umich.edu• folding (hash code)• modulo arithmetic (compression map)What if the keys are not integers?• string: use the ASCII encoding of each char• float: treat it as a string of bits• in general, treat the representation as a bit-string and sum up orextract parts of itSugih Jamin ([email protected])String HashingExample symbol table:Bucket Symbol Memory Locationh(“foo”) = 0 “foo” 1012h(“bar”) = 3 “bar” 20456h(“main”) = 7 “main” 328What is my hash function?int hash(char *s, int M) /* s string to be hashed, M table size */Consider these strings: “stop”, “tops”,“pots”,“spot”How would they hash into my table using the above hash function?Sugih Jamin ([email protected])A Better String Hash CodePolynomial hash code (t) takes positional info into account:t(x[]) = x[0]ak−1+ x[1]ak−2+ . . . + x[k − 2]a + x[k − 1]If a = 33, the intmap’s are:• t(“tops”) =• t(“pots”) =Good choices of a for English words: {33, 37, 39, 41}What does it mean for a to be a good choice?Why are these particular values good?This is folding: partition the key into several partsand combine them in a “convenient” waySugih Jamin ([email protected])Compression Mapping• division method: |intmap| mod M, M table size (prime)• MAD (multiply and divide) method:|a ∗ intmap + b| mod M, a and b non-negative integersSugih Jamin ([email protected])Hashing: Collision ResolutionWith hashing, collision is inevitableWhat do you do when two items hash into the same bucket/bin?Methods of collision resolution:• separate chaining• scatter tableo coalesced chainingo open addressing:- linear probing- quadratic probing- double hashing• extensible hashing: dynamic hashingSugih Jamin ([email protected])Collision ResolutionSeparate chaining:let each bin points to a linked list of elements (see Fig. 8.3)Coalesced chaining:• store linked list in unused portion of the table• if item hashes to an already occupied bin, follow the linked list andadd item to the end (coalesced chaining, see Fig. 8.4)• hash table can only hold as many items as table sizeOpen addressing: if there’s a collision, apply another hash functionrepeatedly until there’s no collision. Set of hash functions:{h0, h1, h2, . . .}Sugih Jamin ([email protected])Open AddressingTo probe ::= to look at an entry and compare its key with targetLinear probing: hi(key) = (h0(key) + i) mod Mdo a linear search from h0(key) until you find an empty slot(see Fig. 8.6, compare against Fig. 8.4)Clustering: when contiguous bins are all occupiedWhy is