Tables in Various LanguagesCS 311 Data Structures and AlgorithmsLecture SlidesWednesday, December 2, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell2 Dec 2009 CS 311 Fall 2009 2ReviewWhere Are We? — The Big ProblemOur problem for much of the rest of the semester: Store: a collection of data items, all of the same type. Operations: Access items [one item: retrieve/find, all items: traverse]. Add new item [insert]. Eliminate existing item [delete]. All this needs to be efficient in both time and space.A solution to this problem is a container.Generic containers: those in which client code can specify the type of data stored.2 Dec 2009 CS 311 Fall 2009 3Unit OverviewTables & Priority QueuesMajor Topics Introduction to Tables Priority Queues Binary Heap algorithms Heaps & Priority Queues in the C++ STL 2-3 Trees Other balanced search trees Hash Tables Prefix Trees Tables in various languagesIdea #1: Restricted TableIdea #2: Keep a Tree BalancedIdea #3: “Magic Functions”Lots of lousy implementations2 Dec 2009 CS 311 Fall 2009 4ReviewIntroduction to TablesIdea #1: Restricted Table Perhaps we can do better if we do not implement a Table in its full generality.Idea #2: Keep a Tree Balanced Balanced Binary Search Trees look good, but how to keep them balanced efficiently?Idea #3: “Magic Functions” Use an unsorted array of key-data pairs. Allow array items to be marked as “empty”. Have a “magic function” that tells the index of an item. Retrieve/insert/delete in constant time? (Actually no, but this is still a worthwhile idea.)We will look at what results from these ideas: From idea #1: Priority Queues From idea #2: Balanced search trees (2-3 Trees, Red-Black Trees, B-Trees, etc.) From idea #3: Hash TablesLinearLinearLinearBinarySearch TreeLinearConstantLinearUnsortedLinked ListLinearLinearLinearSortedLinked ListLogarithmicLogarithmicLogarithmicBalanced (how?)BinarySearch TreeConstant???LinearInsertLinearLinearDeleteLinearLogarithmicRetrieveUnsortedArraySortedArray2 Dec 2009 CS 311 Fall 2009 5Overview of Advanced Table ImplementationsWe will cover the following advanced Table implementations. Balanced Search Trees Binary Search Trees are hard to keep balanced, so to make things easier we allow more than 2 children: 2-3 Tree Up to 3 children 2-3-4 Tree Up to 4 children Red-Black Tree Binary-tree representation of a 2-3-4 tree Or back up and try a balanced Binary Tree again: AVL Tree Alternatively, forget about trees entirely: Hash Tables Finally, “the Radix Sort of Table implementations”: Prefix TreeDONE2 Dec 2009 CS 311 Fall 2009 6ReviewHash Tables — IntroductionA Hash Table is a Table implementation that uses a hash function for key-based look-up. A Hash Table is generally implemented as an array. The index used is the output of the hash function.Needed: Hash function. Collision resolution method. Collision: hash function gives same output for different keys. This is the primary design decision involved in a Hash Table.(key, data) EMPTY (key, data) (key, data) EMPTY (key, data)(key, data) (key, data)hashfunctionkey location2 Dec 2009 CS 311 Fall 2009 7ReviewHash Tables — Collision Resolution [1/2]Collision Resolution Methods — Type 1: Open Addressing Hash Table is an array. Each location holds one key-data pair, “empty”, or “deleted”. Search in a sequence of locations (the probe sequence), beginning at the location given by the hashed key. Linear probing: t, t+1, t+2, etc. Tends to form clusters. Quadratic probing: t, t+12, t+22, etc. Double hashing: Use another hash function to help determine the probe sequence.EMPTY Non-emptyDELETEDCluster2 Dec 2009 CS 311 Fall 2009 8ReviewHash Tables — Collision Resolution [2/2]Collision Resolution Methods — Type 2: “Buckets” Hash Table is an array of data structures, each of which can hold multiple key-data pairs. Array locations are buckets. Separate chaining: Each bucket is a Linked List. This is very common.2 Dec 2009 CS 311 Fall 2009 9ReviewHash Tables — Efficiency*Priority Queue retrieve & delete are not Table operations in their full generality. Only the item with the highest priority can be retrieved/deleted.**This is logarithmic if (1) the PQ does not manage its own memory, or (2) enough memory is preallocated. Otherwise, occasional linear-time reallocate-and-copy may be required. Time per-operation, averaged over many consecutive operations, will be logarithmic. Thus, “amortized logarithmic”.***Hash Table insert is constant time in a “double average” sense: when averaged both over all possible inputs and over a large number of consecutive operations.****This is amortized constant time if both of the following are true: (1) separate chaining is used, and (2) duplicate keys are allowed.LinearLinear****LinearHash Table:worst caseConstantAmortizedconstant***ConstantHash Table:average caseLogarithmic(Amortized)**logarithmicInsertLogarithmicLogarithmic*DeleteLogarithmicConstant*RetrieveRed-Black TreePriority Queueusing HeapIdea #1 Idea #2 Idea #32 Dec 2009 CS 311 Fall 2009 10ReviewPrefix TreesA Prefix Tree (or Trie) is a Table implementation in which the keys are strings. We use “string” in a general sense,as in our discussion of Radix Sort. A nonnegative integer is a string of digits. The quintessential key type is words,as in the previous slide. A Prefix Tree is space-efficient whenkeys tend to share prefixes.A Prefix Tree is a kind of tree. Each node can have one child for eachpossible character. Each node also contains a Boolean value,indicating whether it represents a stored key. Duplicate keys are not allowed. Lastly, each node can hold the data associatedwith a key.d eigotge ignggsPrefix Tree2 Dec 2009 CS 311 Fall 2009 11Tables in Various LanguagesOverviewWe now take a brief look at Table usage in various languages, beginning with C++. C++ STL Sets: std::set. Maps: std::map. Other Tables. Set algorithms. Other Languages Python. Perl. Lisp.2 Dec 2009 CS 311 Fall 2009 12Tables in Various Languages C++ STL: Aside — std::pair [1/2]The C++ STL contains a “pair” template: std::pair, in <utility>. It acts as if it is declared roughly like this: