summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorHaidong Ji2019-03-10 22:15:07 -0500
committerHaidong Ji2019-03-10 22:15:07 -0500
commit8fdeec331c424f2a7cfc98619e98a0d2420ddf7c (patch)
treecae12ff61f2e8b9d09c44b1d94041793b5911d30 /src
parent8e0d78c1b52e84dfbdb2765d9c4183ab2116c2d1 (diff)
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...
Diffstat (limited to 'src')
-rw-r--r--src/main/HashChains.java125
-rw-r--r--src/test/HashChainsTest.java19
-rw-r--r--src/test/PhoneBookTest.java26
3 files changed, 144 insertions, 26 deletions
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());
+ }
+ }
+}
+
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