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 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 125 insertions(+)
 create mode 100644 src/main/HashChains.java

(limited to 'src/main')

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<List<String>> 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());
+        }
+    }
+}
+
-- 
cgit v1.2.3