Chapter 11 Hash TablesIntroductionMore…Introduction to HashingIntroduction to Hashing - ExampleHashing: Exception CasesIntroduction Hashing AlgorithmsHashing: Converting Words to NumbersIntroduction Hashing AlgorithmsIntroduction Hashing Algorithms (Collisions and Synonyms – Terminology)Slide 11Slide 12Hashing and Collision ExampleSlide 14Slide 15Slide 16Organization of Chapter 11Examples of Collision Algorithms1. Open Addressing – Linear ProbeOpen Addressing – Linear ProbeSlide 21ExamplePowerPoint PresentationSlide 24Slide 25Searching Hash TableLet’s look at find() (next slide)Slide 28Let’s look at delete()Slide 30Slide 31Slide 32Slide 3311Chapter 11 Chapter 11 Hash TablesHash TablesPart 122//4848IntroductionVery VERY fast way to build and access tables (and records in files too).Provide nearly O(1) performance.Simple to do too.Extremely fast; significantly faster than trees, which are O(log2n)!33//4848More…More…Similar to arrays – which is a disadvantage.Do need to have some idea how many items will populate the hash table so table size can be determines.Also quite difficult (makes no sense) to access sequentially (as you will see).But you will know the size of the table and hence the size of your ‘database.’44//4848Introduction to HashingIntroduction to HashingOften called Randomizing…We will have a range of (input) values (e.g. state names, account numbers, String value, etc.) that will be mapped into a range of array values.The function that will map the key values of these records, objects, etc. to table locations (or relative file locations) is called a hash function.So, items (objects, records, attribute, etc.) will ‘hash’ to locations in the hash table based on a value within a record / object.Then, the record / object will be moved into and occupy those locations.55//4848Introduction to Hashing - Introduction to Hashing - ExampleExampleLet’s take objects of type Person that have an SSAN attribute (field) in it.We may take the last four digits, like 1234, and divide (mod) that by some prime number, say 47, such that ALL objects will hash to values between, say, 0 and 46.So, given an input object, we will access this key value, hash to an index between 0 and 46 and then move the entire object (or whatever it is…) into this location (indexed by the hashed-to value (0 to 46).66//4848Hashing: Exception CasesHashing: Exception CasesExisting Key: Sometimes there is an attribute within an object that can be directly used as an index into the hash table without invoking a hashing function.Examples: e.g. (from your book) employee number in an object or record, or, in a laboratory, an ‘experiment’ number attribute, which might start with a lab number or experiment number 0 or 1. In these cases, the index number into the hash table is the same as the key value, and we don’t have to actually ‘hash’ to a table value.We can use this integer as the index into the table we are building.77//4848Introduction Hashing Introduction Hashing AlgorithmsAlgorithmsSo to ultimately store an object into a hash table (or to a location on disk), we need to arrive at a number, an integer that will be an index into the hash table or the address of the record on disk.We can start with numbers and restrict the range of acceptable values by using the mod function (remainder method).We discussed this a couple of slides back.But sometimes our input into the hashing algorithm may not be a number.88//4848Hashing: Converting Words to Hashing: Converting Words to NumbersNumbersOur input into a hashing algorithm may sometimes be characters or a String. So we may want to convert them to numeric form to facilitate randomizing.One way to convert letters to numbers is to translate: a = 1; b = 2, t = 20, s = 19. Add the total for a word such as cats, which yields a 43.So ‘cats’ would be stored in location 43. Unfortunately, it may be that many words might ‘hash’ to 43. These are called ‘synonyms.’But synonyms cannot all occupy the same single space…So what to do? (Coming soon!)99//4848 Introduction Hashing Introduction Hashing Algorithms Algorithms Given a key (attribute) in an object (or record), we need a hash function that will map all possible keys in the input space into a specific location within the bounds of the hash table.What we’d like is to hash to a table location and discover this location is unoccupied and then move the object into the table at the hashed-to location. It just doesn’t always work that way in practice.1010//4848 Introduction Hashing Algorithms Introduction Hashing Algorithms (Collisions and Synonyms – (Collisions and Synonyms – TerminologyTerminology))When one or more keys hash to the same hash table location, we call this situation a collision.Those elements (objects, records, …) that do hash to this location are called synonyms.So, we need a mechanism (algorithm) to deal with synonyms.1111//4848Introduction Hashing Introduction Hashing AlgorithmsAlgorithmsSo, practical considerations require us to map key values (including synonyms) into hash table locations that may NOT be one-to-one.Also, all input values themselves must map to the range of hash table entries (the table size) either directly or via a hashing algorithm. Thus, we may have something like:Arrayindex = someNumber % arraySize or Arrayindex = someKeyConvertedToANumber % arraySize1212//4848Introduction Hashing Introduction Hashing AlgorithmsAlgorithmsArrayindex = someNumber % arraySize  classic example of a hashing function! Called Division-Remainder Method.This algorithm hashes (converts) a ‘number’ in a large range (naturally occurring values – say social security numbers) into a number in a much smaller range (the table size). (As one might expect, there is a very large number of hashing functions available. (See Donald Knuth))1313//4848Hashing and Collision Hashing and Collision ExampleExampleSo, we have: Arrayindex = someNumber % arraySizeSo, any integer mod arraySize results in an Arrayindex range of 0 to arraySize-1.5280 (number of feet in a mile) mod 51 yields a number between 0 (if 51 divides 5280 evenly) and 50.Any number mod 51 yields a number between 0 and 50. Period!Again, this particular hashing algorithm is called the Division Remainder method!Consider the following exercise:1414//4848Hashing and