11.1 Hash Tables

11.1 Hash tables Hash table overview A hash table is a data structure that stores unordered items by mapping (or hashing) item 12:26 to a location ©zyBookseach 10/31/25 2201896in an Willian Amado array (or vector). Ex: Given an array with indices 0..9 to store integers from 0..500, the modulo (remainder) operator RIOHONDOCIT128HarlowFall2025 can be used to map 25 to index 5 (25 % 10 = 5), and 149 to index 9 (149 % 10 = 9). A hash table's main advantage is that searching (or inserting / removing) an item may require only O(1), in contrast to O(N) for searching a list or to O(log N) for binary search. In a hash table, an item's key is the value used to map to an index. For all items that might possibly be stored in the hash table, every key is ideally unique, so that the hash table's algorithms can search for a specific item by that key. Each hash table array element is called a bucket. A hash function computes a bucket index from the item's key. PARTICIPATION ACTIVITY 11.1.1: Hash table data structure. Start 2x speed Empty Occupied playerNums = new HashTable(10) HashInsert(playerNums, 116) HashInsert(playerNums, 12) HashInsert(playerNums, 23) HashSearch(playerNums, 23) playerNums: 0 1 2 12 3 23 23 == 23 4 5 Hash function: key % 10 6 23 % 10 = 3 7 116 8 9 Captions keyboard_arrow_down PARTICIPATION ACTIVITY 11.1.2: Hash tables. 1) A 100 element hash table has 100 _____. items buckets ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 2) A hash function computes a bucket index from an item's _____. integer value key 3) For a well-designed hash table, searching requires _____ on average. O(1) O(N) ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 O(log N) 4) A company will store all employees in a hash table. Each employee item consists of a name, department, and employee ID number. Which is the most appropriate key? Name Department Employee ID number Item representation Normally, each item being stored is an object with several fields, such as a person object having a name, age, and ID number, with the ID number used as the key. For simplicity, this section represents an item just by the item's key. Ex: Item 64 represents a person object with a key of 64, which is the person's ID. HashInsert(hashTable, item 64) inserts item 64 in bucket 4, representing item 64 in the hash table just by the key 64. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Hash table operations A common hash function uses the modulo operator %, which computes the integer remainder when dividing two numbers. Ex: For a 20 element hash table, a hash function of key % 20 will map keys to bucket indices 0 to 19. A hash table's operations of insert, remove, and search each use the hash function to determine an item's bucket. Ex: Inserting 113 first determines the bucket to be 113 % 10 = 3. PARTICIPATION ACTIVITY 11.1.3: Hash tables. 1) A modulo hash function for a 50 entry hash table ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 is: key % _____ Check Show answer 2) key % 1000 maps to indices 0 to ____. Check Show answer 3) A modulo hash function is used to map to indices 0 to 9. The hash function should be: key % _____ Check Show answer 4) Given a hash table with 100 buckets and modulo hash function, in which bucket will HashInsert(table, item 334) insert item 334? Check Show answer 5) Given a hash table with 50 buckets and modulo hash function, in which bucket will HashSearch(table, 201) search for the item? Check PARTICIPATION ACTIVITY Show answer 11.1.4: Hash table search efficiency. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Consider a modulo hash function (key % 10) and the following hash table. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 1) How many buckets will be checked for HashSearch(numsTable, 45)? 1 6 10 2) If item keys range from 0 to 49, how many keys may map to the same bucket? 1 5 50 3) If a linear search were applied to the array, how many array elements would be checked to find item 45? 1 6 10 Empty cells ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 The approach for a hash table algorithm determining whether a cell is empty depends on the implementation. For example, if items are simply non-negative integers, empty can be represented as -1. More commonly, items are each an object with multiple fields (name, age, etc.), in which case each hash table array element may be a pointer. Using pointers, empty can be represented as null. Collisions A collision occurs when an item being inserted into a hash table maps to the same bucket as an existing item in the hash table. Ex: For a hash function of key % 10, 55 would be inserted in bucket 55 % 10 = 5; later inserting 75 would yield a collision because 75 % 10 is also 5. Various techniques are used to handle collisions during insertions, such as chaining or open addressing. Chaining is a collision resolution technique where each bucket 10/31/25 12:26 technique 2201896 has a list of items (so bucket 5's list would become 55, 75). Open addressing ©zyBooks is a collision resolution Willian Amado RIOHONDOCIT128HarlowFall2025 where collisions are resolved by looking for an empty bucket elsewhere in the table (so 75 might be stored in bucket 6). Such techniques are discussed later in this material. PARTICIPATION 11.1.5: Hash table collisions. ACTIVITY 1) A hash table's items will be positive integers, and -1 will represent empty. A 5-bucket hash table is: -1, -1, 72, 93, -1. How many items are in the table? 0 2 5 2) A hash table has buckets 0 to 9 and uses a hash function of key % 10. If the table is initially empty and the following inserts are applied in the order shown, the insert of which item results in a collision? HashInsert(hashTable, item 55) HashInsert(hashTable, item 90) HashInsert(hashTable, item 95) Item 55 Item 90 Item 95 CHALLENGE ACTIVITY 11.1.1: Hash tables with modulo hash function. 656220.4403792.qx3zqy7 Start ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 A hash table with non-negative integer keys has a modulo hash function of key % 15. Hash function index range: 0 to Ex: 5 Item 119 will go in bucket Ex: 26 1 Check ©zyBooks 10/31/25 12:26 2201896 Willian Amado 3 RIOHONDOCIT128HarlowFall2025 2 Next 11.2 Chaining Chaining handles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket. The insert operation first uses the item's key to determine the bucket, and then inserts the item in that bucket's list. Searching also first determines the bucket, and then searches the bucket's list. Likewise for removes. PARTICIPATION ACTIVITY Start 11.2.1: Hash table with chaining. 2x speed Empty Occupied HashInsert(hashTable, item) { if (HashSearch(hashTable, item⇢key) == null) { bucketList = hashTable[Hash(item⇢key)] node = Allocate new linked list node node⇢next = null node⇢data = item ListAppend(bucketList, node) } } hashTable: 0 1 2 3 4 5 6 HashSearch(hashTable, key) { bucketList = hashTable[Hash(key)] itemNode = ListSearch(bucketList, key) if (itemNode is not null) return itemNode⇢data else return null } HashInsert(table, item 77) HashInsert(table, item 8) HashInsert(table, item 17) HashSearch(table, 17) // Returns item 17 7 77 8 8 17 9 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Captions keyboard_arrow_down Figure 11.2.1: Hash table with chaining: Each bucket contains a list of items. HashInsert(hashTable, item) { if (HashSearch(hashTable, item⇢key) == null) { bucketList = hashTable[Hash(item⇢key)] node = Allocate new linked list node node⇢next = null node⇢data = item ListAppend(bucketList, node) } } ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 HashRemove(hashTable, item) { bucketList = hashTable[Hash(item⇢key)] itemNode = ListSearch(bucketList, item⇢key) if (itemNode is not null) { ListRemove(bucketList, itemNode) } } HashSearch(hashTable, key) { bucketList = hashTable[Hash(key)] itemNode = ListSearch(bucketList, key) if (itemNode is not null) return itemNode⇢data else return null } PARTICIPATION ACTIVITY 11.2.2: Hash table with chaining: Inserting items. Given hash function of key % 10, type the specified bucket's list after the indicated operation(s). Assume items are inserted at the end of a bucket's list. Type the bucket list as: 5, 7, 9 (or type: Empty). ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 1) HashInsert(valsTable, item 20) Bucket 0's list: _____ Check Show answer 2) HashInsert(valsTable, item 23) HashInsert(valsTable, item 99) Bucket 3's list: _____ Check ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Show answer 3) HashRemove(valsTable, 46) Bucket 6's list: _____ Check Show answer 4) HashRemove(valsTable, 218) Bucket 8's list: _____ Check PARTICIPATION ACTIVITY Show answer 11.2.3: Hash table with chaining: Search. Consider the following hash table, and a hash function of key % 10. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 1) How many list elements are compared for HashSearch(valsTable, 62)? Check Show answer 2) How many list elements are compared for HashSearch(valsTable, 40)? Check ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Show answer 3) What does HashSearch(valsTable, 186) return? Check Show answer 4) How many list elements are compared for HashSearch(valsTable, 837)? Check CHALLENGE ACTIVITY Show answer 11.2.1: Chaining. 656220.4403792.qx3zqy7 Start Hash table valsTable is shown below. The hash function is key % 5. Assume items are inserted at the end of a bucket's list. valsTable: 25 22 29 After the operations HashInsert(valsTable, item 72) HashInsert(valsTable, item 76) ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Select the bucket containing the following items: 76 Select 22 Select 72 Select 1 Check 2 3 4 5 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Next 11.3 Linear probing Linear probing overview A hash table with linear probing handles a collision by starting at the key's mapped bucket, and then linearly searches subsequent buckets until an empty bucket is found. PARTICIPATION ACTIVITY 11.3.1: Hash table with linear probing. Start 2x speed Empty 1) Insert (77, "Item 1") Hash(77) % 7 = 77 % 7 = 0 Occupied Hash table: 2) Insert (88, "Item 2") Hash(88) % 7 = 88 % 7 = 4 0 (77, "Item 1") 1 (49, "Item 3") 3) Insert (49, "Item 3") Hash(49) % 7 = 49 % 7 = 0 Bucket 0 occupied Bucket 1 empty 2 3 4 (88, "Item 2") 5 4) Contains key 49? True Hash(49) % 7 = 49 % 7 = 0 Not found in bucket 0 Found in bucket 1 5) Contains key 21? False Hash(21) % 7 = 21 % 7 = 0 Not found in bucket 0 Not found in bucket 1 Bucket 2 is empty 6 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Captions keyboard_arrow_down PARTICIPATION ACTIVITY 11.3.2: Hash table with linear probing: Insert. Given hash function of key % 5, determine the insert location for each item. 1) HashInsert(numsTable, item 13) ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 bucket = Check Show answer 2) HashInsert(numsTable, item 41) bucket = Check Show answer 3) HashInsert(numsTable, item 90) bucket = Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 4) HashInsert(numsTable, item 74) bucket = Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Empty bucket types Actually, linear probing distinguishes two types of empty buckets. An empty-since-start bucket has been empty since the hash table was created. An empty-after-removal bucket had an item removed that caused the bucket to now be empty. The distinction will be important during searches, since searching only stops for empty-since-start, not for empty-after-removal. PARTICIPATION ACTIVITY 11.3.3: Hash with linear probing: Bucket status. Given hash function of key % 10, determine the bucket status after the following operations have been executed. HashInsert(valsTable, item 64) HashInsert(valsTable, item 20) HashInsert(valsTable, item 51) HashRemove(valsTable, 51) 1) Bucket 2 empty-since-start empty-after-removal 2) Bucket 1 empty-since-start empty-after-removal 3) Bucket 4 occupied empty-after-removal Inserts using linear probing ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Using linear probing, a hash table insert algorithm uses the item's key to determine the initial bucket, linearly probes (or checks) each bucket, and inserts the item in the next empty bucket (the empty kind doesn't matter). If the probing reaches the last bucket, the probing continues at bucket 0. The insert algorithm returns true if the item was inserted, and returns false if all buckets are occupied. PARTICIPATION 11.3.4: Insert with linear probing. ACTIVITY Start ©zyBooks 10/31/25 12:26 2201896 Willian Amado Empty-since-start RIOHONDOCIT128HarlowFall2025 2x speed Empty-after-removal HashInsert(hashTable, item) { // Hash function determines initial bucket bucket = Hash(item.key) 19 % 10 = 9 bucketsProbed = 0 N = hashTable's size while (bucketsProbed < N) { // Insert item in next empty bucket if (hashTable[bucket] is Empty) { hashTable[bucket] = item return true } Occupied hashTable: bucket: 0 10 Occupied 1 19 Empty Occupied 2 202 3 42 4 // Increment bucket index bucket = (bucket + 1) % N 5 85 6 // Increment number of buckets probed ++bucketsProbed 7 } 8 return false 9 } 89 Occupied bucketsProbed: 2 Captions HashInsert(hashTable, item 42) // Returns true HashInsert(hashTable, item 19) // Returns true N: 10 keyboard_arrow_down PARTICIPATION ACTIVITY 11.3.5: Hash table with linear probing: Insert with empty-after-removal buckets. For the given hash table and hash function of key % 5, what are the contents for each bucket after the following operations? ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 HashInsert(numsTable, item 43) HashInsert(numsTable, item 300) HashInsert(numsTable, item 71) How to use this tool keyboard_arrow_down Empty-since-start Item 20 Item 300 Item 43 Item 71 numsTable[0] numsTable[1] ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 numsTable[2] numsTable[3] numsTable[4] Reset Removals using linear probing Using linear probing, a hash table remove algorithm uses the sought item's key to determine the initial bucket. The algorithm probes each bucket until either a matching item is found, an empty-since-start bucket is found, or all buckets have been probed. If the item is found, the item is removed, and the bucket is marked empty-afterremoval. PARTICIPATION ACTIVITY Start 11.3.6: Remove with linear probing. 2x speed Empty-since-start Empty-after-removal HashRemove(hashTable, key) { // Hash function determines initial bucket bucket = Hash(key) bucketsProbed = 0 while ((hashTable[bucket] is not EmptySinceStart) and (bucketsProbed < N)) { if ((hashTable[bucket] is not Empty) and (hashTable[bucket]⇢key == key)) { hashTable[bucket] = EmptyAfterRemoval return } // Increment bucket index bucket = (bucket + 1) % N // Increment number of buckets probed ++bucketsProbed } } HashRemove(hashTable, 202) HashRemove(hashTable, 19) Occupied hashTable: 0 10 1 2 3 42 4 ©zyBooks 10/31/25 12:26 2201896 5 85Willian Amado RIOHONDOCIT128HarlowFall2025 6 7 8 9 89 Captions keyboard_arrow_down Note that if the algorithm encounters an empty-after-removal bucket, the algorithm keeps probing, because the sought item may have been placed in a subsequent bucket before this bucket's item was removed. Ex: Removing ©zyBooks 10/31/25 12:26 2201896 Willian Amado item 42 above would start at bucket 2. Because bucket 2 is empty-after-removal, the algorithm would proceed to bucket 3, where item 42 would be found and removed. PARTICIPATION ACTIVITY RIOHONDOCIT128HarlowFall2025 11.3.7: Hash table with linear probing: Remove. Consider the following hash table and a hash function of key % 10. 1) HashRemove(idsTable, 65) probes _____ buckets. Check Show answer 2) HashRemove(idsTable, 10) probes _____ buckets. Check Show answer 3) HashRemove(idsTable, 68) probes _____ buckets. Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Searching using linear probing In linear probing, a hash table search algorithm uses the sought item's key to determine the initial bucket. The algorithm probes each bucket until either the matching item is found (returning the item), an empty-since-start bucket is found (returning null), or all buckets are probed without a match (returning null). If an empty-afterremoval bucket is found, the search algorithm continues to probe the next bucket. PARTICIPATION ACTIVITY 11.3.8: Search with linear probing. 2x speed Start Empty-since-start HashSearch(hashTable, key) { // Hash function determines initial bucket bucket = Hash(key) bucketsProbed = 0 while ((hashTable[bucket] is not EmptySinceStart) and (bucketsProbed < N)) { if ((hashTable[bucket] is not Empty) and (hashTable[bucket]⇢key == key)) { return hashTable[bucket] } ©zyBooks 10/31/25Empty-after-removal 12:26 2201896 Occupied Willian Amado RIOHONDOCIT128HarlowFall2025 hashTable: 0 1 19 2 202 3 42 4 // Increment bucket index bucket = (bucket + 1) % N 5 // Increment number of buckets probed ++bucketsProbed 7 85 6 8 } return null // Item not found 9 89 } HashSearch(hashTable, 42) // Returns item 42 HashSearch(hashTable, 19) // Returns item 19 HashSearch(hashTable, 115) // Returns null Captions keyboard_arrow_down PARTICIPATION ACTIVITY 11.3.9: Hash table with linear probing: Search. Consider the following hash table and a hash function of key % 10. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 1) HashSearch(valsTable, 75) probes _____ buckets. Check Show answer 2) HashSearch(valsTable, 110) probes _____ buckets. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Check Show answer 3) What does HashSearch(valsTable, 112) return? Check Show answer 4) HashSearch(valsTable, 207) probes _____ buckets. Check CHALLENGE ACTIVITY Show answer 11.3.1: Linear probing. 656220.4403792.qx3zqy7 Start valsTable: Empty-since-start 21, "WI" Empty-after-removal Hash table valsTable uses linear probing. Keys are integers and values are strings. Assume all keys are non-negative integers, and so the hash function returns the key itself. Occupied HashInsert(valsTable, 31, "KS") inserts item (31, "KS") into bucket Ex: 10 96, "MD" 27, "ME" 12:26 2201896 HashInsert(valsTable, 33, "PA") inserts©zyBooks item (33,10/31/25 "PA") into bucket Willian Amado RIOHONDOCIT128HarlowFall2025 HashInsert(valsTable, 16, "VA") inserts item (16, "VA") into bucket 1 Check Next 2 3 4 11.4 Quadratic probing Overview and insertion ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 A hash table with quadratic probing handles a collision by starting at the key's mapped bucket, and then quadratically searches subsequent buckets until an empty bucket is found. If an item's mapped bucket is H, the formula is used to determine the item's index in the hash table. c1 and c2 are programmer-defined constants for quadratic probing. Inserting a key uses the formula, starting with i = 0, to repeatedly search the hash table until an empty bucket is found. Each time an empty bucket is not found, i is incremented by 1. Iterating through sequential i values to obtain the desired table index is called the probing sequence. PARTICIPATION ACTIVITY 11.4.1: Hash table insertion using quadratic probing: c1 = 1 and c2 = 1. Start 2x speed Empty hashTable: Hash function: key % 10 Quadratic probing sequence: (H + i + i * i) % 10 i Bucket index Occupied 0 1 H(key) Insert key 55 55 % 10 = 5 0 (5 + 0 + 0 * 0) % 10 = 5 Yes 4 Insert key 66 66 % 10 = 6 0 (6 + 0 + 0 * 0) % 10 = 6 Yes 5 55 Insert key 25 25 % 10 = 5 0 (5 + 0 + 0 * 0) % 10 = 5 No 6 66 Yes 7 25 1 (5 + 1 + 1 * 1) % 10 = 7 Bucket empty? 2 Operation 3 8 9 Captions keyboard_arrow_down Figure 11.4.1: HashInsert with quadratic probing. HashInsert(hashTable, item) { i = 0 bucketsProbed = 0 // Hash function determines initial bucket bucket = Hash(item⇢key) % N while (bucketsProbed < N) { // Insert item in next empty bucket if (hashTable[bucket] is Empty) { ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 hashTable[bucket] = item return true } // Increment i and recompute bucket index // c1 and c2 are programmer-defined constants for quadratic probing i = i + 1 bucket = (Hash(item⇢key) + c1 * i + c2 * i * i) % N // Increment number of buckets probed bucketsProbed = bucketsProbed + 1 } return false ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 } PARTICIPATION ACTIVITY 11.4.2: Insertion using quadratic probing. Assume a hash function returns key % 16 and quadratic probing is used with c1 = 1 and c2 = 1. Refer to the table below. 1) 32 was inserted before 16 True False 2) Which value was inserted without collision? 99 64 23 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 3) What is the probing sequence when inserting 48 into the table? 8 0, 8 0, 2, 6, 12 4) How many bucket index computations were necessary to insert 64 into the table? 1 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 2 3 5) If 21 is inserted into the hash table, what would be the insertion index? 5 9 11 Search and removal The search algorithm uses the probing sequence until the key being searched for is found or an empty-since-start bucket is found. The removal algorithm searches for the key to remove and, if found, marks the bucket as emptyafter-removal. PARTICIPATION ACTIVITY 11.4.3: Search and removal with quadratic probing: c1 = 1 and c2 = 1. 2x speed Start 0 1 49 2 16 3 3 4 5 99 6 64 7 23 10 42 11 11 12 13 14 15 Empty-since-start Occupied 1. HashRemove(table, 32) 2. HashSearch(table, 64): Hash(64): (64 % 16) = 0 i = 0: index = (0 + 0 + 0) = 0 8 9 Empty-after-removal Hash(key): key % 16 Quadratic probing sequence: (H + i + i * i) % 16 ©zyBooks 10/31/25 12:26 2201896 Bucket is empty-after-removal, so search continues. Willian Amado RIOHONDOCIT128HarlowFall2025 i = 1: index = (0 + 1 + 1) = 2 Bucket does not contain 64, so search continues. i = 2: index = (0 + 2 + 4) = 6 64 is found Captions keyboard_arrow_down Figure 11.4.2: HashRemove and HashSearch with quadratic probing. HashRemove(hashTable, key) { i = 0 bucketsProbed = 0 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 // Hash function determines initial bucket bucket = Hash(key) % N while ((hashTable[bucket] is not EmptySinceStart) and (bucketsProbed < N)) { if ((hashTable[bucket] is Occupied) and (hashTable[bucket]⇢key == key)) { hashTable[bucket] = EmptyAfterRemoval return true } // Increment i and recompute bucket index // c1 and c2 are programmer-defined constants for quadratic probing i = i + 1 bucket = (Hash(key) + c1 * i + c2 * i * i) % N // Increment number of buckets probed bucketsProbed = bucketsProbed + 1 } return false // key not found } HashSearch(hashTable, key) { i = 0 bucketsProbed = 0 // Hash function determines initial bucket bucket = Hash(key) % N while ((hashTable[bucket] is not EmptySinceStart) and (bucketsProbed < N)) { if ((hashTable[bucket] is Occupied) and (hashTable[bucket]⇢key == key)) { return hashTable[bucket] } // Increment i and recompute bucket index // c1 and c2 are programmer-defined constants for quadratic probing i = i + 1 bucket = (Hash(key) + c1 * i + c2 * i * i) % N // Increment number of buckets probed bucketsProbed = bucketsProbed + 1 } return null ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 // key not found } PARTICIPATION ACTIVITY 11.4.4: Hash table with quadratic probing: search and remove. Consider the following hash table, a hash function of key % 10, and quadratic probing with c1 = 1 and c2 = 1. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 1) HashSearch(valsTable, 75) probes _____ buckets. Check Show answer 2) HashSearch(valsTable, 110) probes _____ buckets. Check Show answer 3) After removing 66 via HashRemove(valsTable, 66), HashSearch(valsTable, 66) probes _____ buckets. Check PARTICIPATION ACTIVITY Show answer 11.4.5: Using empty buckets during search, insertion, and removal. 1) When a hash table is initialized, all entries must be empty-after-removal. True False 2) The insertion algorithm can only insert into empty-since-start buckets. True False ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 3) The search algorithm stops only when encountering a bucket containing the key being searched for. True False 4) The removal algorithm searches for the bucket ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 containing the key to remove. If found, the bucket is marked as empty-after-removal. True False CHALLENGE ACTIVITY 11.4.1: Quadratic probing. 656220.4403792.qx3zqy7 Start valsTable: Empty-since-start Empty-after-removal Occupied 23 25 1 Check Hash table valsTable uses quadratic probing, a hash function of key % 10, c1 = 1, and c2 = 1. HashInsert(valsTable, item 45) inserts item 45 into bucket Ex: 10 . HashInsert(valsTable, item 24) inserts item 24 into bucket . HashInsert(valsTable, item 83) inserts item 83 into bucket . 2 3 Next 11.5 Double hashing Overview 4 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Double hashing is an open-addressing collision resolution technique that uses 2 different hash functions to compute bucket indices. Using hash functions h1 and h2, a key's index in the table is computed with the formula . Inserting a key uses the formula, starting with i = 0, to repeatedly search hash table buckets until an empty bucket is found. Each time an empty bucket is not found, i is incremented by 1. Iterating through sequential i values to obtain the desired table index is called the probing sequence. PARTICIPATION ACTIVITY 11.5.1: Hash table insertion using double hashing. Start 0 2x speed Empty 60 Hash1(key): key % 10 Hash2(key): 11 - key % 11 Occupied 1 2 72 3 55 4 5 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Double hashing probing sequence: (Hash1(key) + i * Hash2(key)) % 13 1. Insert items 72, 60, 45, 18, and 39 45 2. HashInsert(table, item 55): 6 7 8 18 9 39 10 23 11 i = 0: (55 % 10 + 0 * (11 - 55 % 11)) % 13 = 5 Bucket 5 is occupied i = 1: (55 % 10 + 1 * (11 - 55 % 11)) % 13 = 3 Bucket 3 is available 3. HashInsert(table, item 23): 12 i = 0: (23 % 10 + 0 * (11 - 23 % 11)) % 13 = 3 Bucket 3 is occupied i = 1: (23 % 10 + 1 * (11 - 23 % 11)) % 13 = 0 Bucket 0 is occupied i = 2: (23 % 10 + 2 * (11 - 23 % 11)) % 13 = 10 Bucket 10 is available Captions keyboard_arrow_down PARTICIPATION ACTIVITY 11.5.2: Double hashing. Given: hash1(key) = key % 11 ©zyBooks 10/31/25 12:26 2201896 Willian Amado and a hash table with a size of 11. Determine the index for each item after the following operations have been RIOHONDOCIT128HarlowFall2025 hash2(key) = 5 - key % 5 executed. HashInsert(valsTable, item 16) HashInsert(valsTable, item 77) HashInsert(valsTable, item 55) HashInsert(valsTable, item 41) HashInsert(valsTable, item 63) 1) Item 16 Check Show answer 2) Item 55 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Check Show answer 3) Item 63 Check Show answer Insertion, search, and removal Using double hashing, a hash table search algorithm probes (or checks) each bucket using the probing sequence defined by the two hash functions. The search continues until either the matching item is found (returning the item), an empty-since-start bucket is found (returning null), or all buckets are probed without a match (returning null). A hash table insert algorithm probes each bucket using the probing sequence, and inserts the item in the next empty bucket (the empty kind doesn't matter). A hash table removal algorithm first searches for the item's key. If the item is found, the item is removed, and the bucket is marked empty-after-removal. PARTICIPATION ACTIVITY 11.5.3: Hash table insertion, search, and removal using double hashing. Start 2x speed 0 32 Empty-after-removal 1 49 Empty-since-start 2 3 Occupied 88 4 1. HashRemove(table, 3): 5 6 16 7 23 8 24 11 12 i = 0: (3 % 16 + 0 * (11 - 3 % 11)) % 16 = 3 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Found key 3 at index 3 Mark bucket as empty-after-removal 2. HashRemove(table, 19): 9 10 Hash1(key): key % 16 Hash2(key): 11 - key % 11 Double hashing probing sequence: (Hash1(key) + i * Hash2(key)) % 16 42 i = 0: (19 % 16 + 0 * (11 - 19 % 11)) % 16 = 3 Empty-after-removal bucket at index 3, search continues... 13 99 14 15 i = 1: (19 % 16 + 1 * (11 - 19 % 11)) % 16 = 6 Item 16, not 19, at index 6, search continues ... i = 2: (19 % 16 + 2 * (11 - 19 % 11)) % 16 = 9 Found 19 at index 9, mark bucket as empty-after-removal 3. HashInsert(table, item 88): i = 0: (88 % 16 + 0 * (11 - 88 % 11)) % 16 = 8 Occupied i = 1: (88 % 16 + 1 * (11 - 88 % 11)) % 16 = 3 Available ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Captions keyboard_arrow_down PARTICIPATION ACTIVITY 11.5.4: Hash table with double hashing: search, insert, and remove. Consider the following hash table, a first hash function of key % 10, and a second hash function of 7 - key % 7. 1) HashSearch(valsTable, 110) probes _____ buckets. Check Show answer 2) HashInsert(valsTable, item 24) probes _____ buckets. Check Show answer 3) After removing 66 via HashRemove(valsTable, 66), HashSearch(valsTable, 66) probes _____ buckets. Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 PARTICIPATION 11.5.5: Hash table insertion, search, and removal with double hashing. ACTIVITY 1) When the removal algorithm finds the bucket containing the key to be removed, the bucket is marked as empty-since-start. True ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 False 2) Double hashing would never resolve collisions if the second hash function always returned 0. True False CHALLENGE ACTIVITY 11.5.1: Double hashing. 656220.4403792.qx3zqy7 Start valsTable: 11 Empty-since-start Empty-after-removal Occupied Hash table valsTable uses double probing with the hash functions hash1(key): key % 11 hash2(key): 7 - key % 7 and a table size of 11. HashInsert(valsTable, item 22) inserts item 22 into bucket Ex: 10 . HashInsert(valsTable, item 76) inserts item 76 into bucket . HashInsert(valsTable, item 31) inserts item 31 into bucket . 43 1 Check 2 Next 3 4 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 11.6 Hash table resizing Resize operation A hash table resize operation increases the number of buckets, while preserving all existing items. A hash table with N buckets is commonly resized to the next prime number ≥ N * 2. A new array is allocated, and all items from the old array are re-inserted into the new array, making the resize operation's time complexity PARTICIPATION 11.6.1: Hash table resize operation. ACTIVITY Start . ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 2x speed newArray: HashResize(hashTable, currentSize) { newSize = nextPrime(currentSize * 2) newArray = Allocate new array of size newSize Set all entries in newArray to EmptySinceStart bucket = 0 while (bucket < currentSize) { if (hashTable[bucket] is not Empty) { key = hashTable[bucket] HashInsert(newArray, key) } bucket = bucket + 1 } return newArray } Hash(key, tableSize) { return key % tableSize } Empty-since-start 0 Empty-after-removal 1 Occupied 2 hashTable: 3 88 4 0 71 5 1 2 79 6 3 91 7 7 4 8 54 5 9 71 10 6 7 7 79 11 12 8 9 64 13 10 54 14 15 16 HashResize(hashTable, 11) 17 18 64 19 88 20 21 22 Captions keyboard_arrow_down PARTICIPATION ACTIVITY 91 11.6.2: Resizing a hash table. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Suppose the hash table below is resized. The hash function used both before and after resizing is: hash(key) = key % N, where N is the table size. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 1) What is the most likely allocated size for the resized hash table? 7 14 17 2) How many elements are in the hash table after resizing? 0 4 7 3) At what index does 99 reside in the resized table? 1 9 14 When to resize A hash table's load factor is the number of items in the hash table divided by the number of buckets. Ex: A hash table with 18 items and 31 buckets has a load factor of . The load factor may be used to decide when to resize the hash table. An implementation may choose to resize the hash table when one or more of the following values exceeds a certain threshold: Load factor When using open-addressing, the number of collisions during an insertion When using chaining, the size of a bucket's linked-list PARTICIPATION ACTIVITY ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 11.6.3: Resizing when a chaining bucket is too large. Start 2x speed 0 10 95 1 86 46 15 Resize criteria Resize if any bucket 2 length is >= 4 78 3 63 58 33 4 Resize 0 33 1 78 2 46 3 58 4 15 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 5 6 Captions 7 95 8 63 9 86 10 10 keyboard_arrow_down PARTICIPATION ACTIVITY 11.6.4: Resizing when the load factor is ≥ 0.6. 2x speed Start 0 1 0 81 Insert 22 2 3 4 0 1 81 2 22 Resize Load factor: 0.4 Occupied 2 3 54 4 Load factor: 0.6 5 4 Empty-since-start Empty-after-removal 1 3 54 22 81 6 7 Resize criteria 8 Resize if load factor is ≥ 0.6 9 10 54 Load factor: 0.27 Captions keyboard_arrow_down PARTICIPATION ACTIVITY ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 11.6.5: Resizing when an insertion causes more than N / 3 collisions. 2x speed Start table: 0 77 Empty-since-start resized table: 0 Empty-after-removal 1 1 2 2 3 3 4 4 27 51 5 27 5 6 83 6 7 51 7 8 19 8 9 64 10 Occupied ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 77 9 10 11 12 HashInsert(table, 38) More than 3 collisions Resize criteria: Resize if N / 3 or more collisions during insertion HashInsert causes table to resize 13 14 83 15 38 16 17 18 64 19 19 20 21 22 Captions keyboard_arrow_down PARTICIPATION ACTIVITY 11.6.6: Resize criteria and load factors. 1) A hash table implementation must use only one criteria for resizing. True False 2) In a hash table using open addressing, the load factor cannot exceed 1.0. True False ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 3) In a hash table using chaining, the load factor cannot exceed 1.0. True False 4) When resizing to a larger size, the load factor is guaranteed to decrease. True False PARTICIPATION ACTIVITY ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 11.6.7: Resizing a hash table with 101 buckets. Suppose a hash table has 101 buckets. 1) If the hash table was using chaining, the load factor could be ≤ 0.1, but an individual bucket could still contain 10 items. True False 2) If the hash table was using open addressing, a load factor < 0.25 guarantees that no more than 25 collisions will occur during insertion. True False 3) If the hash table was using open addressing, a load factor > 0.9 guarantees a collision during insertion. True False 11.7 Common hash functions A good hash function minimizes collisions ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 A hash table is fast if the hash function minimizes collisions. A perfect hash function maps items to buckets with no collisions. A perfect hash function can be created if the number of items and all possible item keys are known beforehand. The runtime for insert, search, and remove is O(1) with a perfect hash function. A good hash function should uniformly distribute items into buckets. With chaining, a good hash function results in short bucket lists and thus fast inserts, searches, and removes. With linear probing, a good hash function will avoid hashing multiple items to consecutive buckets and thus minimize the average linear probing length to achieve fast inserts, searches, and removes. On average, a good hash function will achieve O(1) inserts, searches, and removes, but in the worst-case may require O(N). A hash function's performance depends on the hash table size and knowledge of the expected keys. Ex: The hash function key % 10 will perform poorly if the expected keys are all multiples of 10, because inserting 10, 20, 30, ..., 90, and 100 will all collide at bucket 0. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Modulo hash function A modulo hash uses the remainder from division of the key by hash table size N. Figure 11.7.1: Modulo hash function. HashRemainder(int key) { return key % N } PARTICIPATION ACTIVITY 11.7.1: Good hash functions and keys. Will the hash function and expected key likely work well for the following scenarios? 1) Hash function: key % 1000 Key: 6-digit employee ID Hash table size: 20000 Yes No 2) Hash function: key % 250 Key: 5-digit customer ID Hash table size: 250 Yes No 3) Hash function: key % 1000 Key: Selling price of a house. Hash table size: 1000 Yes No ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 4) Hash function: key % 40 Key: 4-digit even numbers Hash table size: 40 Yes No 5) Hash function: key % 1000 Key: Customer's 3-digit U.S. phone number area code, of which about 300 exist. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Hash table size: 1000 Yes No Mid-square hash function A mid-square hash squares the key, extracts R digits from the result's middle, and returns the remainder of the middle digits divided by hash table size N. Ex: For a hash table with 100 entries and a key of 453, the decimal (base 10) mid-square hash function computes 453 * 453 = 205209, and returns the middle two digits 52. For N buckets, R must be greater than or equal to to index all buckets. The process of squaring and extracting middle digits reduces the likelihood of keys mapping to just a few buckets. PARTICIPATION ACTIVITY 11.7.2: Decimal mid-square hash function. 1) For a decimal mid-square hash function, what are the middle digits for key = 40, N = 100, and R = 2? Check Show answer 2) For a decimal mid-square hash function, what is the bucket index for key = 110, N = 200, and R = 3? Check Show answer 3) For a decimal mid-square hash function, what is the bucket index for key = 112, N = 1000, and R = 3? Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Mid-square hash function base 2 implementation The mid-square hash function is typically implemented using binary (base 2), and not decimal, because a binary implementation is faster. A decimal implementation requires converting the square of the key to a string, extracting a substring for the middle digits, and converting that substring to an integer. A binary implementation only requires a few shift and bitwise AND operations. A binary mid-square hash function extracts the middle R bits, and returns the remainder of the middle bits divided by hash table size N, where R is greater than or equal to ©zyBooks 10/31/25 12:26 2201896 . Ex: For a hash tableWillian size of 200, R = 8, then 8 Amado bits are needed for indices 0 to 199. RIOHONDOCIT128HarlowFall2025 Figure 11.7.2: Mid-square hash function (base 2). HashMidSquare(int key) { squaredKey = key * key lowBitsToRemove = (32 - R) / 2 extractedBits = squaredKey >> lowBitsToRemove extractedBits = extractedBits & (0xFFFFFFFF >> (32 - R)) return extractedBits % N } The extracted middle bits depend on the maximum key. Ex: A key with a value of 4000 requires 12 bits. A 12-bit number squared requires up to 24 bits. For R = 10, the middle 10 bits of the 24-bit squared key are bits 7 to 16. PARTICIPATION ACTIVITY 11.7.3: Binary mid-square hash function. 1) For a binary mid-square hash function, how many bits are needed for an 80 entry hash table? Check Show answer 2) For R = 3, what are the middle bits for a key of 9? 9 * 9 = 81; 81 in binary is 1010001. Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Multiplicative string hash function A multiplicative string hash repeatedly multiplies the hash value and adds the ASCII (or Unicode) value of each character in the string. A multiplicative hash function for strings starts with a large initial value. For each character, the hash function multiplies the current hash value by a multiplier (often prime) and adds the character's value. Finally, the function returns the remainder of the sum divided by the hash table size N. Figure 11.7.3: Multiplicative string hash function. HashMultiplicative(string key) { stringHash = InitialValue for (each character strChar in key) { stringHash = (stringHash * HashMultiplier) + strChar } ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 return stringHash % N } Daniel J. Bernstein created a popular version of a multiplicative string hash function that uses an initial value of 5381 and a multiplier of 33. Bernstein's hash function performs well for hashing short English strings. PARTICIPATION ACTIVITY 11.7.4: Multiplicative string hash function. For a 1000-entry hash table, compute the multiplicative hash for the following strings using the specific initial value and hash multiplier. The decimal ASCII value for each character is shown below. Character Decimal value Character Decimal value A 65 N 78 B 66 O 79 C 67 P 80 D 68 Q 81 E 69 R 82 F 70 S 83 G 71 T 84 H 72 U 85 I 73 V 86 J 74 W 87 K 75 X 88 L 76 Y 89 M 77 Z 90 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 1) Initial value = 0 Hash multiplier = 1 String = BAT Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 2) Initial value = 0 Hash multiplier = 1 String = TAB Check Show answer 3) Initial value = 17 Hash multiplier = 3 String = WE Check Show answer Exploring further: The following provide resources that summarize, discuss, and analyze numerous hash functions. Hash Functions: An Empirical Comparison by Peter Kankowski. Hash Functions and Block Ciphers by Bob Jenkins. 11.8 Direct hashing Direct hashing overview ©zyBooks 10/31/25 12:26 2201896 Willian Amado A direct hash function uses the item's key as the bucket index. Ex: If the key is RIOHONDOCIT128HarlowFall2025 937, the index is 937. A hash table with a direct hash function is called a direct access table. Given a key, a direct access table search algorithm returns the item at index key if the bucket is not empty, and returns null (indicating item not found) if empty. PARTICIPATION ACTIVITY 11.8.1: Direct hash function. Start 2x speed Empty Occupied HashSearch(hashTable, key) { if (hashTable[key] is not Empty) { return hashTable[key] } else { return null } } HashSearch(table, 6) HashSearch(table, 3) hashTable: // Returns item 6 // Returns null 0 1 1 2 3 4 4 5 6 ©zyBooks 6 10/31/25 12:26 2201896 Willian Amado 7 RIOHONDOCIT128HarlowFall2025 8 8 9 Captions keyboard_arrow_down Figure 11.8.1: Direct hashing: Insert, remove, and search operations use item's key as bucket index. HashInsert(hashTable, item) { hashTable[item⇢key] = item } HashRemove(hashTable, item) { hashTable[item⇢key] = Empty } HashSearch(hashTable, key) { if (hashTable[key] is not Empty) { return hashTable[key] } else { return null } } PARTICIPATION ACTIVITY 11.8.2: Direct access table search, insert, and remove. ©zyBooks 10/31/25 12:26empty). 2201896 Type the hash table after the given operations. Type the hash table as: E, 1, 2, E, E (where E means Willian Amado RIOHONDOCIT128HarlowFall2025 1) HashInsert(numsTable, item 0) numsTable: Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 2) HashRemove(numsTable, 0) HashInsert(numsTable, item 4) numsTable: Check Show answer Limitations of direct hashing A direct access table has the advantage of no collisions: Each key is unique (by definition of a key), and each gets a unique bucket, so no collisions can occur. However, a direct access table has two main limitations. 1. All keys must be non-negative integers, but for some applications keys may be negative. 2. The hash table's size equals the largest key value plus 1, which may be very large. PARTICIPATION ACTIVITY 11.8.3: Direct hashing limitations. 1) For a 1000-entry direct access table, type the bucket number for the inserted item, or type: None HashInsert(hashIndex, item 734) Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 2) For a 1000-entry direct access table, type the bucket number for the inserted item, or type: None HashInsert(hashIndex, item 1034) Check Show answer ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 3) For a 1000-entry direct access table, type the bucket number for the inserted item, or type: None HashInsert(hashIndex, item -45) Check Show answer 4) How many direct access table buckets are needed for items with keys ranging from 100 to 200 (inclusive)? Check Show answer 5) A class has 100 students. Student ID numbers range from 10000 to 99999. Using the ID number as key, how many buckets will a direct access table require? Check Show answer 11.9 Hashing Algorithms: Cryptography, Password ©zyBooks 10/31/25 12:26 2201896 Hashing Willian Amado RIOHONDOCIT128HarlowFall2025 Cryptography Cryptography is a field of study focused on transmitting data securely. Secure data transmission commonly starts with encryption: alteration of data to hide the original meaning. The counterpart to encryption is decryption: reconstruction of original data from encrypted data. PARTICIPATION ACTIVITY Start 11.9.1: Basic encryption: Caesar cipher. 2x speed Original message Shift amount New product release tomorrow 4 right Willian Amado Ri{$tvshygx$vipiewi$xsqsvvs{ New product release tomorrow 3 left Kbt|molar`q|obib^pb|qljloolt Ri{$tvshygx$vipiewi$xsqsvvs{ 4 left New product release tomorrow Kbt|molar`q|obib^pb|qljloolt 3 right New product release tomorrow Captions Encrypted message ©zyBooks 10/31/25 12:26 2201896 RIOHONDOCIT128HarlowFall2025 keyboard_arrow_down PARTICIPATION ACTIVITY 11.9.2: Caesar cipher. 1) What is the result of applying the Caesar cipher with a left shift of 1 to the string "computer"? eqorwvgt dpnqvufs bnlotsdq 2) If a message is encrypted with a left shift of X, what shift is needed to decrypt? left shift of X right shift of X 3) If the Caesar cipher were implemented such that strings were restricted to only lower-case alphabet characters, how many distinct ways could a message be encrypted? ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 25 50 Length of the message PARTICIPATION ACTIVITY 11.9.3: Cryptography. 1) Encryption and decryption are synonymous. True False 2) Cryptography is used heavily in internet communications. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 True False 3) The Caesar cipher is an encryption algorithm that works well to secure data for modern digital communications. True False Hashing functions for data A hash function can be used to produce a hash value for data in contexts other than inserting the data into a hash table. Such a function is commonly used for the purpose of verifying data integrity. Ex: A hashing algorithm called MD5 produces a 128-bit hash value for any input data. The hash value cannot be used to reconstruct the original data, but can be used to help verify that data isn't corrupt and hasn't been altered. PARTICIPATION ACTIVITY Start 11.9.4: A hash value can help identify corrupted data downloaded from the internet. 2x speed Computer A Computer B Message: This is some data that must be transmitted accurately, although not necessarily securely. MD5 hash: 1ca19fb44509e66dddc6b30eda65fbd9 Downloaded message: This is so^e data t!@t must*(e tra@&%!tted ac&^%$&#ly, although not necessarily @@@@&ely. Internet Hash values ≠ implies downloaded data is corrupt [ Downloaded MD5 hash: 1ca19fb44509e66dddc6b30eda65fbd9 Computed MD5 hash: 0cc7c65b9f2b29e9e1cb56c31e288637 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Captions keyboard_arrow_down PARTICIPATION ACTIVITY 11.9.5: Hashing functions for data. 1) MD5 produces larger hash values for larger input data sizes. True False 2) A hash value can be used to reconstruct the original data. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 True False 3) If computer B in the above example computed a hash value identical to the downloaded hash value, then the downloaded message would be guaranteed to be uncorrupted. True False Cryptographic hashing A cryptographic hash function is a hash function designed specifically for cryptography. Such a function is commonly used for encrypting and decrypting data. A password hashing function is a cryptographic hashing function that produces a hash value for a password. Databases for online services commonly store a user's password hash as opposed to the actual password. When the user attempts a login, the supplied password is hashed, and the hash is compared against the database's hash value. Because the passwords are not stored, if a database with password hashes is breached, attackers may still have a difficult time determining a user's password. PARTICIPATION ACTIVITY 11.9.6: Password hashing function. Start 2x speed Password hash function Goal: Extremely difficult to convert from output hash value back to original password. Password Input Goal: No 2 different passwords have the same hash value. Optional: Extra random data is computed 1 time and stored alongside the password hash value. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Password hash value Output Captions keyboard_arrow_down PARTICIPATION ACTIVITY 11.9.7: Password hashing function. 1) Which is not an advantage of storing password hash values, instead of actual passwords, in a database? ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Database administrators cannot see users' passwords. Database storage space is saved. Attackers who gain access to database contents still may not be able to determine users' passwords. 2) A user could login with an incorrect password if a password hashing function produced the same hash value for two different passwords. True False 3) Generating and storing random data alongside each password hash in a database, and using (password + random_data) to generate the hash value, can help increase security. True False 11.10 Python: Hash tables HashTable base class HashTable is a base class that declares methods for hashKey(), insert(), remove(), and 10/31/25 search().12:26 The hashKey() ©zyBooks 2201896 Willian method returns a non-negative integer hash code for a key. Each of the insert(), remove(), andAmado search() methods has only a pass statement and will be overridden in a derived class. RIOHONDOCIT128HarlowFall2025 HashTable's hashKey() method uses Python's built-in hash() function. hash() may return a negative integer, but a non-negative integer is needed to compute a bucket index. So hashKey() returns the absolute value of the integer returned from hash(). Figure 11.10.1: HashTable base class. # Base class for a hash table that supports the insert, remove, and search # operations. class HashTable: # Returns a non-negative hash code for the specified key. def hashKey(self, key): return abs(hash(key)) # Inserts the specified key/value pair. If the key already exists, the # corresponding value is updated. If inserted or updated, ©zyBooks True is 10/31/25 returned. 12:26 2201896 # If not inserted, then False is returned. Willian Amado def insert(self, key, value): RIOHONDOCIT128HarlowFall2025 pass # Searches for the specified key. If found, the key/value pair is removed # from the hash table and True is returned. If not found, False is returned. def remove(self, key): pass # Searches for the key, returning the corresponding value if found, None if # not found. def search(self, key): pass PARTICIPATION ACTIVITY 11.10.1: HashTable base class. 1) Classes that derive from HashTable must override hashKey(). True False 2) Classes that derive from HashTable should override insert(), remove(), and search(). True False 3) hashKey() may return a negative integer. True False Chaining ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 The ChainingHashTableItem class represents an item with a key, a value, and a reference to the next item in the chain. ChainingHashTable derives from the HashTable class, and uses a list of ChainingHashTableItem objects for the table attribute. Initially each item in the table list is None, indicating an empty bucket. ChainingHashTable's insert() method computes the key's bucket index, then searches the bucket's linked list for a matching key. If found, the corresponding value is updated. If not found, a new ChainingHashTableItem is appended to the linked list. ChainingHashTable's remove() method computes the key's bucket index, then searches the bucket's linked list for a matching key. If found, the ChainingHashTableItem object with the key is removed from the bucket's linked list. ChainingHashTable's search() method computes the key's bucket index, then searches the bucket's linked list for a matching key. If found, the key's corresponding value is returned. If not found, None is returned. Figure 11.10.2: ChainingHashTableItem and ChainingHashTable classes. class ChainingHashTableItem: def __init__(self, itemKey, itemValue): self.key = itemKey self.value = itemValue self.next = None ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 class ChainingHashTable(HashTable): def __init__(self, initialCapacity = 11): self.table = [None] * initialCapacity # Inserts the specified key/value pair. If the key already exists, the # corresponding value is updated. If inserted or updated, True is returned. # If not inserted, then False is returned. def insert(self, key, value): # Hash the key to get the bucket index bucket_index = self.hashKey(key) % len(self.table) # Traverse the linked list, searching for the key. If the key exists in # an item, the value is replaced. Otherwise a new item is appended. item = self.table[bucket_index] previous = None while item != None: if key == item.key: item.value = value return True previous = item item = item.next # Append to the linked list if self.table[bucket_index] == None: self.table[bucket_index] = ChainingHashTableItem(key, value) else: previous.next = ChainingHashTableItem(key, value) return True # Searches for the specified key. If found, the key/value pair is removed # from the hash table and True is returned. If not found, False is returned. def remove(self, key): # Hash the key to get the bucket index ©zyBooks 10/31/25 12:26 2201896 bucket_index = self.hashKey(key) % len(self.table) # Search the bucket's linked list for the key item = self.table[bucket_index] previous = None while item != None: if key == item.key: if previous == None: # Remove linked list's first item self.table[bucket_index] = item.next else: previous.next = item.next Willian Amado RIOHONDOCIT128HarlowFall2025 return True previous = item item = item.next return False # key not found # Searches for the key, returning the corresponding value if found, None if # not found. def search(self, key): # Hash the key to get the bucket index bucket_index = self.hashKey(key) % len(self.table) # Search the bucket's linked list for the key item = self.table[bucket_index] while item != None: if key == item.key: return item.value item = item.next return None # key not found ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 insert() method variations Some hash table implementations distinguish an insert operation from an update operation. In such implementations, insert fails if the key already exists and update fails if the key doesn't already exist. The implementation of insert() in this section serves both purposes, inserting if the key doesn't exist and updating if the key does exist. PARTICIPATION ACTIVITY 11.10.2: ChainingHashTable class. How to use this tool search() keyboard_arrow_down remove() insert() Returns False and makes no change to a bucket's linked list if the key is not found. Returns None if the key is not found. ©zyBooks 10/31/25 12:26 2201896 May return True without changing the length ofAmado a Willian bucket's linked list. RIOHONDOCIT128HarlowFall2025 Reset OpenAddressingBucket class Each bucket in an open addressing hash table stores a single item, rather than a linked list of items. So the OpenAddressingBucket class has only two members: key and value. Two empty bucket types exist in open addressing hash tables, so the OpenAddressingBucket class also defines two class attributes. Each attribute is an OpenAddressingBucket object, used to mark a bucket as empty-sincestart or empty-after-removal. Figure 11.10.3: OpenAddressingBucket class. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 # OpenAddressingBucket represents a bucket with a key and a value class OpenAddressingBucket: def __init__(self, bucket_key = None, bucket_value = None): self.key = bucket_key self.value = bucket_value def isEmpty(self): if self is OpenAddressingBucket.EMPTY_SINCE_START: return True return self is OpenAddressingBucket.EMPTY_AFTER_REMOVAL # Initialize two special bucket types: empty-since-start and empty-after-removal OpenAddressingBucket.EMPTY_SINCE_START = OpenAddressingBucket() OpenAddressingBucket.EMPTY_AFTER_REMOVAL = OpenAddressingBucket() PARTICIPATION ACTIVITY 11.10.3: OpenAddressingBucket class. 1) Only one instance of EMPTY_SINCE_START exists, no matter how many OpenAddressingBucket instances are created. True False 2) An open addressing hash table implementation that has a list of OpenAddressingBucket references should initialize each to None. True False 3) To check if a bucket is empty-after-removal, the bucket's key and value attributes must be compared with EMPTY_AFTER_REMOVAL's key and value attributes. True False ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 OpenAddressingHashTable base class OpenAddressingHashTable is a base class that derives from HashTable and adds the probe() method. Each derived class implements the probing sequence via the probe() method, allowing for the insert(), remove(), and search() methods to be implemented in the OpenAddressingHashTable class. The insert() method first uses the probing sequence to search for a bucket with the key. If found, the corresponding value is updated. If not found, the probing sequence is used again to find the first empty bucket, wherein the key/value pair is inserted. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 The remove() method uses the probing sequence to search for a bucket with the key. If found, the bucket is set to EMPTY_AFTER_REMOVAL and True is returned. If not found, no change occurs and False is returned. The search() method uses the probing sequence to search for a bucket with the key. If found, the bucket's value is returned. If not found, None is returned. Figure 11.10.4: OpenAddressingHashTable class. class OpenAddressingHashTable(HashTable): def __init__(self, initialCapacity): self.table = [OpenAddressingBucket.EMPTY_SINCE_START] * initialCapacity def probe(self, key, i): # Each derived class must implement pass # Inserts the specified key/value pair. If the key already exists, the # corresponding value is updated. If inserted or updated, True is returned. # If not inserted, then False is returned. def insert(self, key, value): # Search for the key in the table. If found, update the bucket's value. for i in range(len(self.table)): bucket_index = self.probe(key, i) # An empty-since-start bucket implies the key is not in the table if self.table[bucket_index] is OpenAddressingBucket.EMPTY_SINCE_START: break if self.table[bucket_index] is not OpenAddressingBucket.EMPTY_AFTER_REMOVAL: # Check if the non-empty bucket has the key if key == self.table[bucket_index].key: # Update the value self.table[bucket_index].value = value return True # The key is not in the table, so insert into first empty bucket ©zyBooks 10/31/25 12:26 2201896 for i in range(len(self.table)): Willian Amado bucket_index = self.probe(key, i) RIOHONDOCIT128HarlowFall2025 if self.table[bucket_index].isEmpty(): self.table[bucket_index] = OpenAddressingBucket(key, value) return True return False # no empty bucket found # Searches for the specified key. If found, the key/value pair is removed # from the hash table and True is returned. If not found, False is returned. def remove(self, key): for i in range(len(self.table)): bucket_index = self.probe(key, i) # An empty-since-start bucket implies the key is not in the table if self.table[bucket_index] is OpenAddressingBucket.EMPTY_SINCE_START: return False if self.table[bucket_index] is not OpenAddressingBucket.EMPTY_AFTER_REMOVAL: # Check if the non-empty bucket has the key if key == self.table[bucket_index].key: ©zyBooks 10/31/25 12:26 2201896 # Remove by setting the bucket to empty-after-removal Willian Amado self.table[bucket_index] = OpenAddressingBucket.EMPTY_AFTER_REMOVAL RIOHONDOCIT128HarlowFall2025 return True return False # key not found # Searches for the key, returning the corresponding value if found, None if # not found. def search(self, key): for i in range(len(self.table)): bucket_index = self.probe(key, i) # An empty-since-start bucket implies the key is not in the table if self.table[bucket_index] is OpenAddressingBucket.EMPTY_SINCE_START: return None if self.table[bucket_index] is not OpenAddressingBucket.EMPTY_AFTER_REMOVAL: # Check if the non-empty bucket has the key if key == self.table[bucket_index].key: return self.table[bucket_index].value return None # key not found PARTICIPATION ACTIVITY 11.10.4: OpenAddressingHashTable class. 1) Each class that derives from the OpenAddressingHashTable class must implement the probe(), insert(), remove(), and search() methods. True False 2) The OpenAddressingHashTable class's __init()__ method initializes all pointers in the table list to: OpenAddressingBucket.EMPTY_SINCE_START True False 3) The insert(), remove(), and search() methods each call the probe() method. True False ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Linear probing, quadratic probing, and double hashing The LinearProbingHashTable, QuadraticProbingHashTable, and DoubleHashingHashTable classes each derive from OpenAddressingHashTable. Since insert(), remove(), and search() are implemented in OpenAddressingHashTable, each derived class only implements the probing sequence. Figure 11.10.5: LinearProbingHashTable class. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 class LinearProbingHashTable(OpenAddressingHashTable): def __init__(self, initial_capacity = 11): OpenAddressingHashTable.__init__(self, initial_capacity) # Returns the bucket index for the specified key and i value using the # linear probing sequence. def probe(self, key, i): return (self.hashKey(key) + i) % len(self.table) Figure 11.10.6: QuadraticProbingHashTable class. class QuadraticProbingHashTable(OpenAddressingHashTable): def __init__(self, c1 = 1, c2 = 1, initial_capacity = 11): OpenAddressingHashTable.__init__(self, initial_capacity) self.c1 = c1 self.c2 = c2 # Returns the bucket index for the specified key and i value using the # quadratic probing sequence. def probe(self, key, i): return (self.hashKey(key) + self.c1 * i + self.c2 * i * i) % len(self.table) Figure 11.10.7: DoubleHashingHashTable class. class DoubleHashingHashTable(OpenAddressingHashTable): def __init__(self, initial_capacity = 11): OpenAddressingHashTable.__init__(self, initial_capacity) def h2(self, key): return 7 - self.hashKey(key) % 7 # Returns the bucket index for the specified key and i value using the ©zyBooks 10/31/25 12:26 2201896 # double hashing probing sequence. Willian Amado def probe(self, key, i): RIOHONDOCIT128HarlowFall2025 return (self.hashKey(key) + i * self.h2(key)) % len(self.table) PARTICIPATION ACTIVITY 11.10.5: Linear probing, quadratic probing, and double hashing. 1) Which class implements an additional hash function? LinearProbingHashTable QuadraticProbingHashTable DoubleHashingHashTable 2) When 0 is passed as the second argument to the probe() method, each class's returned value equals _____. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 hash(key) self.hashKey(key) % len(self.table) c1 + c2 PARTICIPATION ACTIVITY 11.10.6: Evaluating the probe() method. Assume for each question that the same key object is used, self.hashKey(key) returns 55, and the table's length is 11. 1) probe(key, 2) returns ____ for LinearProbingHashTable. 2 7 57 2) probe(key, 1) returns ____ for QuadraticProbingHashTable when c1=2 and c2=2. 2 4 6 3) probe(key, 4) returns ____ for DoubleHashingHashTable. 4 5 6 zyDE 11.10.1: Working with the Hashtable class. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 The program below shows the bucket contents after adding and removing items to each type of hash table. The __str__() method is implemented in ChainingHashTable and OpenAddressingHashTable to create a visual representation of the buckets. Airport locations are used as keys and airport codes as corresponding values. Current HashTablesDemo.py file: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 from from from from arrow_drop_down Load default template... ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 ChainingHashTable import ChainingHashTable LinearProbingHashTable import LinearProbingHashTable QuadraticProbingHashTable import QuadraticProbingHashTable DoubleHashingHashTable import DoubleHashingHashTable  keys = [ "Los Angeles", "Houston", "Washington", "Chicago", "San Francisco", "Dallas", "Tokyo", "New York", "Vancouver" ] values = [ "LAX", "IAH", "IAD", "ORD", "SFO", "DAL", "NRT", "JFK", "YVR" ] initialCapacity = 11  Run 11.11 LAB: Course gradebook with dict Step 1: Inspect the Gradebook abstract base class The read-only Gradebook.py file has a declaration for the Gradebook abstract base class. Access Gradebook.py by clicking on the orange arrow next to main.py at the top of the coding window. The Gradebook class stores a collection of entries for a course. Conceptually, a gradebook entry is a (assignment ©zyBooks 10/31/25 2201896 name, student ID, score) triplet. Each assignment name is a string, each student ID is an integer,12:26 and each score is a float. A score is entered into the gradebook via the set_score() method. Willian Amado RIOHONDOCIT128HarlowFall2025 The Gradebook class has six abstract methods that must be implemented in an inheriting class. Step 2: Add attributes to CourseGradebook class The CourseGradebook class inherits from Gradebook and is declared in CourseGradebook.py. Inspect each method that must be implemented. Choose one or more attributes to store gradebook data and add the attributes to the CourseGradebook class. Several options exist, so grading does not analyze the choice of attributes. Step 3: Implement CourseGradebook's set_score() and get_score() methods ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Implement the set_score() method to enter a single entry into the gradebook. set_score() has parameters for the assignment name, student ID, and score. How the entry is stored depends on the attributes chosen in step 2. Implement the get_score() method to get a single score from the gradebook. get_score() has parameters for the assignment name and student ID, and returns a float for the corresponding score. None is returned if no such entry exists in the gradebook. Code in main.py calls test_get_score_and_set_score() to test both methods. Run your program in develop mode and ensure that the test passes before proceeding further. Step 4: Implement the remaining CourseGradebook methods Implement the remaining methods according to the specifications below. get_assignment_scores() takes a string for the assignment name and returns a dict that maps a student ID to the student's corresponding score for the assignment. An entry exists in the returned dict only if a score has been entered with the set_score() method. An empty dict is returned if no such assignment exists in the grade book. get_sorted_assignment_names() returns a list with all distinct assignment names, sorted in ascending order. get_sorted_student_iDs() returns a list with all distinct student IDs, sorted in ascending order. get_student_scores() gets all scores that exist in the gradebook for the student whose ID equals the method parameter. Scores are returned as a dict that maps an assignment name to the student's corresponding score for that assignment. 656220.4403792.qx3zqy7 LAB ACTIVITY 11.11.1: LAB: Course gradebook with dict 0 / 10 ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 Downloadable files main.py , Gradebook.py , CourseGradebook.py , and Download TestUtility.py Current file: main.py arrow_drop_down Load default template... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  from TestUtility import make_sample_gradebook from CourseGradebook import CourseGradebook from TestUtility import count_string def main(): result1 result2 result3 result4 result5 = = = = = test_get_score_and_set_score() test_get_assignment_scores() test_get_sorted_assignment_names() test_get_sorted_student_IDs() test_get_student_scores() ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025 print(f""" Summary: test_get_score_and_set_score(): {'PASS' if result1 else 'FAIL'} test_get_assignment_scores(): {'PASS' if result2 else 'FAIL'} test_get_sorted_assignment_names(): {'PASS' if result3 else 'FAIL'} test_get_sorted_student_IDs(): {'PASS' if result4 else 'FAIL'} test_get_student_scores(): {'PASS' if result5 else 'FAIL'}""")  Develop mode Submit mode  Run your program as often as you'd like, before submitting for grading. Below, type any needed input values in the first box, then click Run program and observe the program's output in the second box. Enter program input (optional) If your code requires input values, provide them here. Run program Input (from above) trending_flat main.py (Your program) trending_flat Output (shown below) Program output displayed here Coding trail of your work What is this? History of your effort will appear here once you begin working on this zyLab. ©zyBooks 10/31/25 12:26 2201896 Willian Amado RIOHONDOCIT128HarlowFall2025