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

2024
Views:

50

Pages:

10
Author:

Accinkiquicpqw

find Header & Requirements /** * Indicates if a value is in a hashtable or not * @param table the hash table to add the element to * @param value value to be added * @return true if value is in the hashtable, false otherwise */ public static boolean find(List> table, int elemen Hashtable – find public static boolean find(List> table, int element) { int code = element; // integer values are their own hashCode int index = Math.floorMod(code, table.size()); return table.get(index).contains(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. Search only that list for the element Hashtable – remove N/4 N/4 N/4 N/4 0 1 2 3 • Suppose we want to remove an element from a hashtable • First figure out which list it should be in 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 and remove it when found remove Header & Requirements /** * Removes an arbitrary value from a binary search tree * @param table the hash table to add the element to * @param value value to be added * @precond value is in the hashtable * @postcond value is not in the hashtable */ public static void remove(List> table, String eleme Hashtable – remove public static void remove(List> table, int element) { int code = element; int bucket = Math.floorMod(code, table.size()); List list = table.get(bucket); int idx = 0; while (idx < list.size() && list.get(idx) != element) { idx++; } table.get(bucket).remove(idx); } 1. 2. 3. 4. Get the hashCode value for the element Use the mod function to find the index of the list to use Search only that list for the index of that element Remove the element at that index HashSet on a hashtable • With these operations we can see how we'd implement a HashSet using a hashtable: • • • • We add an element to the set by adding it to the table. We remove an element from the set by removing it from the table. We check to see if a set contains an element by finding it in the table. We could get the size of the set by counting the values • • • • But it's easier to keep a separate size private variable Whenever we add an element to the table, add 1 to the size. Whenever we remove an element from the table, subtract 1 from the size. When size is called, return the size variable instead of counting. SimpleHashSet implementation public class SimpleHashSet implements SimpleSet { private final static int DEFAULT_SIZE = 16; private List> table; private int size; public SimpleHashSet() { this.table = new ArrayList<>(); for (int i=0; i()); } this.size = 0; } … } Constructor sets the initial value of the set to be empty. A table with a default number of lists – in this case 16 The table has to be created – the list needs to be filled with the right number of empty lists size needs to be initially set to 0. SimpleHashSet implementation public class SimpleHashSet implements SimpleSet { private List> table; private int size; … public void add(E element) { this.root = add(table, element); this.size++; } public void remove(E element) { this.root = remove(table, element); this.size--; } public int size() { return this.size; } } Adding an element to the set is just adding it to the table and incrementing the size. Removing an element in the set is just a matter of removing it from the table and decrementing the size. To see if the set contains an item, use find to find it in the table. To get the size we don’t have to count the elements – just return the size we have kept track of. Modulus Arithmetic • Modulus is clock arithmetic • Similar to remainder but not quite the same • (You will often see the Java remainder operator % mistakenly referred to as the "modulus operator" in some online sources) Modulus Arithmetic • To find a mod b • Imagine a circle with the numbers between 0 and b-1 on it arranged clockwise • Take a steps along this circle clockwise if a > 0 • Wherever you stop, you are at the answer to a mod b • If a < 0, steps along this circle are counter-clockwise 0 3 1 2 9 -9 15 -15 mod mod mod mod 4 4 4 4 = = = = ? ? ? ?

Hash Tables and Hashing Lecture 2

Related Documents

Recommended Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock