From 8fdeec331c424f2a7cfc98619e98a0d2420ddf7c Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Sun, 10 Mar 2019 22:15:07 -0500 Subject: Hash chain simulation done! Created test cases for the hash function. Tested the code by running the main function without writting test cases. I wish the starter code was written in a way that facilitated testing... --- src/main/HashChains.java | 125 +++++++++++++++++++++++++++++++++++++++++++ src/test/HashChainsTest.java | 19 +++++++ src/test/PhoneBookTest.java | 26 --------- 3 files changed, 144 insertions(+), 26 deletions(-) create mode 100644 src/main/HashChains.java create mode 100644 src/test/HashChainsTest.java delete mode 100644 src/test/PhoneBookTest.java diff --git a/src/main/HashChains.java b/src/main/HashChains.java new file mode 100644 index 0000000..f21d05d --- /dev/null +++ b/src/main/HashChains.java @@ -0,0 +1,125 @@ +import java.io.*; +import java.util.ArrayList; +import java.util.List; +import java.util.StringTokenizer; + +public class HashChains { + + private FastScanner in; + private PrintWriter out; + // store all strings in one list + private List> elems; + // for hash function + int bucketCount; + + public static void main(String[] args) throws IOException { + new HashChains().processQueries(); + } + + int hashFunc(String s) { + long hash = 0; + int prime = 1000000007; + int multiplier = 263; + for (int i = s.length() - 1; i >= 0; --i) + hash = (hash * multiplier + s.charAt(i)) % prime; + return (int) hash % bucketCount; + } + + private Query readQuery() throws IOException { + String type = in.next(); + if (!type.equals("check")) { + String s = in.next(); + return new Query(type, s); + } else { + int ind = in.nextInt(); + return new Query(type, ind); + } + } + + private void writeSearchResult(boolean wasFound) { + out.println(wasFound ? "yes" : "no"); + // Uncomment the following if you want to play with the program interactively. + // out.flush(); + } + + private void processQuery(Query query) { + int hashIndex; + switch (query.type) { + case "add": + hashIndex = hashFunc(query.s); + if (!elems.get(hashIndex).contains(query.s)) + elems.get(hashIndex).add(0, query.s); + break; + case "del": + hashIndex = hashFunc(query.s); + elems.get(hashIndex).remove(query.s); + break; + case "find": + hashIndex = hashFunc(query.s); + writeSearchResult(elems.get(hashIndex).contains(query.s)); + break; + case "check": + for (String cur : elems.get(query.ind)) + out.print(cur + " "); + out.println(); + // Uncomment the following if you want to play with the program interactively. + // out.flush(); + break; + default: + throw new RuntimeException("Unknown query: " + query.type); + } + } + + private void processQueries() throws IOException { + elems = new ArrayList<>(); + in = new FastScanner(); + out = new PrintWriter(new BufferedOutputStream(System.out)); + bucketCount = in.nextInt(); + for (int i = 0; i < bucketCount; i++) { + elems.add(new ArrayList<>()); + } + int queryCount = in.nextInt(); + for (int i = 0; i < queryCount; ++i) { + processQuery(readQuery()); + } + out.close(); + } + + static class Query { + String type; + String s; + int ind; + + Query(String type, String s) { + this.type = type; + this.s = s; + } + + Query(String type, int ind) { + this.type = type; + this.ind = ind; + } + } + + static class FastScanner { + private BufferedReader reader; + private StringTokenizer tokenizer; + + FastScanner() { + reader = new BufferedReader(new InputStreamReader(System.in)); + tokenizer = null; + } + + String next() throws IOException { + while (tokenizer == null || !tokenizer.hasMoreTokens()) { + tokenizer = new StringTokenizer(reader.readLine()); + } + return tokenizer.nextToken(); + } + + int nextInt() throws IOException { + return Integer.parseInt(next()); + } + } +} + diff --git a/src/test/HashChainsTest.java b/src/test/HashChainsTest.java new file mode 100644 index 0000000..9a7f192 --- /dev/null +++ b/src/test/HashChainsTest.java @@ -0,0 +1,19 @@ +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.*; + +class HashChainsTest { + @Test + void test(){ + HashChains hc = new HashChains(); + hc.bucketCount = 5; + assertEquals(4, hc.hashFunc("world")); + assertEquals(4, hc.hashFunc("HellO")); + assertEquals(2, hc.hashFunc("GooD")); + assertEquals(2, hc.hashFunc("luck")); + + hc.bucketCount = 3; + assertEquals(1, hc.hashFunc("add")); + assertEquals(1, hc.hashFunc("help")); + } +} \ No newline at end of file diff --git a/src/test/PhoneBookTest.java b/src/test/PhoneBookTest.java deleted file mode 100644 index fb898f0..0000000 --- a/src/test/PhoneBookTest.java +++ /dev/null @@ -1,26 +0,0 @@ -import org.junit.jupiter.api.Test; - -import static org.junit.jupiter.api.Assertions.*; - -class PhoneBookTest { - @Test - void test() { - PhoneBook.add(911, "police"); - PhoneBook.add(76213, "Mom"); - PhoneBook.add(17239, "Bob"); - - assertEquals("Mom", PhoneBook.find(76213)); - assertEquals("not found", PhoneBook.find(910)); - assertEquals("police", PhoneBook.find(911)); - - PhoneBook.del(910); - PhoneBook.del(911); - - assertEquals("not found", PhoneBook.find(911)); - assertEquals("Mom", PhoneBook.find(76213)); - - PhoneBook.add(76213, "daddy"); - assertEquals("daddy", PhoneBook.find(76213)); - } - -} \ No newline at end of file -- cgit v1.2.3