University:
Kentucky State University
Course:
COS 232 | Programming I
Academic year:

2022
Views:

144

Pages:

10
Author:

Nesbyenvkk

Set Implementation II – Hash Tables and Hashing Big Ideas • Hash Tables • Description • Implementation • Set implementation using a Hash Table Hash Tables • Maps and Sets have two implementations • HashMap and HashSet • TreeMap and TreeSet • The names describe their underlying implementations • A HashSet has a hash table as its underlying implementation • A TreeSet has a binary tree as its underlying implementation • What is a hash table? Searching a list • Recall – searching an unsorted list is O(n) • Linear search – check each element until we find the value • Worst case – item not in the list or item is the last element in list • Have to inspect all items • Imagine a Set/Map implemented on a list • Linear search to find items • Poor performance as the Set/Map size increases Splitting up the list N N/4 N/4 N/4 • Imagine we could split the list up into smaller lists • • • • Have some way to identify which list an element "belongs" to When you add it, add it to that list When you go to find it, search only the list it "belongs" to Only need to search ¼*n items in the worst case instead of n! N/4 Splitting up the list N N/4 N/4 N/4 • We can't quite get this "perfect" distribution • But we can come close with hashing • This "list of lists" is known as a hashtable N/4 Hashtable – add N/4 N/4 N/4 N/4 0 1 2 3 • Suppose we want to add an element to a hashtable • First figure out which list it belongs to 1. Determine the hashcode of the element to add • For numeric values use their integer value • For reference types, use their hashCode function 2. Take the hashcode modulo the number of lists to get the list index • The modulo function gives us a positive value between 0 and the number of lists – 1 • It is the same as the % operator for positive numbers • For negative numbers it guarantees a positive value (hashCode can return a negative value) 3. Add the element to the end of the list given by the list index add Header & Requirements /** * Add an element to its correct place in a hashtable * @param table the hash table to add the element to * @param value value to be added * @precond element is not in the hashtable * @postcond element will be in the correct place in the hashtab */ public static void add(List> table, int element) Hashtable – add public static void add(List> table, int element) { int code = element; // integer values are their own hashCode int index = Math.floorMod(code, table.size()); table.get(index).add(element); } 1. Get the hashCode value for the element • int values are their own hashCode 2. Use the mod function to find the index of the list to use • The size of the table is the number of lists • index will be between 0 and the number of lists – 1 3. Add the element to the end of the list Hashtable – find N/4 N/4 N/4 N/4 0 1 2 3 • Suppose we want to find an element in a hashtable • Return true if it is in one of the lists, false otherwise • First figure out which list it belongs to 1. Determine the hashcode of the element to look for • For numeric values use their integer value • For reference types, use their hashCode function 2. Take the hashcode modulo the number of lists to get the list index • The modulo function gives us a positive value between 0 and the number of lists – 1 • It is the same as the % operator for positive numbers • For negative numbers it guarantees a positive value (hashCode can return a negative value) 3. Search for the element only in the list given by the list index

Hash Tables and Hashing Lecture 1

Related Documents

Recommended Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock