· 6 years ago · Jul 08, 2019, 04:06 PM
1// File: A4HashTable.java
2// Authors: Geoffrey Tien/ Rita Ester
3// (your name here)
4// Date: June 2019
5// Description: Hash table class for CSCI 225 assignment #4
6// Uses separate chaining with singly-linked list
7// Strings are converted using Horner's method base-26
8// a = 1, b = 2, ... , z = 26
9// Assume that we will only hash lower-case character strings
10// with no whitespace or punctuation.
11// This hash table does NOT store duplicates. Check for existence
12// before inserting any key value.
13
14public class A4HashTable {
15
16 private A4LinkedList[] table;
17 private int tableSize;
18 private final int DEFAULT_SIZE = 53; // default table size
19 private final double LOADFACTOR_MAX = 0.75; // maximum load factor
20 private int size;
21
22 ///////////////////////////////
23 // private methods
24 ///////////////////////////////
25
26 // Finds the smallest prime number larger than n
27 private int nextPrime(int n) {
28 int result = n;
29 if (result < DEFAULT_SIZE) result = DEFAULT_SIZE;
30 while (!isPrime(result)) {
31 result += 1;
32 }
33 return result;
34 }
35
36 // Checks if a number is prime
37 private boolean isPrime(int n) {
38 if (n < 2) return false;
39 if (n == 2) return true;
40 if (n % 2 == 0) return false;
41 return isPrime( n, 3 );
42 }
43
44 private boolean isPrime(int n, int divisor) {
45 if ((divisor * divisor) > n) return true;
46 if ((n % divisor) == 0) return false;
47 return isPrime( n, divisor + 2 );
48 }
49
50 // performs Horner's method on the string parameter item. Base-26
51 // Assume that we will only hash lower-case character strings
52 // with no whitespace or punctuation.
53 // Use the following values for characters: a = 1, b = 2, ... , z = 26
54 // How to calculate these values?
55 // Example for ch = 'a':
56 // char ch = 'a';
57 // int chVal = ch - 96;
58 // The character 'a' has ASCII value 97, thus subtracting 96
59 // from this value will result in 1.
60 private int hornerValue(String item) {
61 int value = 0;
62 // to be completed
63
64 for (int i=0;i<item.length();i++) {
65 char letter=item.charAt(i);
66 int letterVal=letter-96;
67 int b=item.length()-i-1;
68 int letterValue=letterVal*((int)Math.pow(26,b));
69 value+=letterValue;
70
71 }
72 return value;
73 }
74
75 // default constructor
76 // You must initialize each array element as a new A4LinkedList object
77 public A4HashTable() {
78 tableSize = DEFAULT_SIZE;
79 table = new A4LinkedList[tableSize];
80 size = 0;
81 for (int i=0; i<tableSize; i++)
82 table[i] = new A4LinkedList();
83 }
84
85 // parameterized constructor
86 // new hash table is created with array size
87 // as the next prime number larger than parameter tablesize.
88 public A4HashTable(int tablesize) {
89 // to be completed
90
91 int tableSize=nextPrime(tablesize);
92 table=new A4LinkedList[tableSize];
93
94 }
95
96
97 // Returns a (deep) copy of the linked list at index i
98 public A4LinkedList listAt(int i) {
99 A4LinkedList list = new A4LinkedList(table[i]);
100 return list;
101 }
102
103
104 // Hash function
105 // Normally this is made private, but for testing/grading purposes
106 // this is public
107 public int hash(String item) {
108 int x = hornerValue(item);
109 return (x * 17) % tableSize;
110 }
111
112
113 // Returns the number of key values in the hash table
114 public int size() {
115 return size;
116 }
117
118 // Returns the current load factor
119 public double loadFactor() {
120 return (double) size / (double) tableSize;
121 }
122
123 // Hash table search
124 // Uses linked list search after hashing
125 public boolean contains(String item) {
126 // to be completed
127 //find hash index
128 int index=hash(item);
129 A4LinkedList t=table[index];
130 //check if it contains
131 if(t.contains(item)) {
132 return true;
133 }
134 return false;
135 }
136
137 private void IncreaseTableSize() {
138
139 }
140
141 // Insert an item into the hash table.
142 // If item does not exist already, insert and return true.
143 // Otherwise, hash table is unchanged and return false.
144
145 // After the insert, check if load factor exceeds the maximum,
146 // If yes: Create a new hash table array,
147 // double the current table size, and use the next prime number
148 // for the new arraysize,
149
150 // then re-insert all items into the new array.
151 // How:
152 // For each list of the hash table, create an array of type Comparable (use toArray)
153 // and re-insert each element of this array into the new hash-table.
154 // Cast each Comparable element of the array onto String when inserting.
155 // use insert((String) array[i]).
156 public boolean insert(String item) {
157 // to be completed
158 // insert if not exists.
159
160 if(!contains(item)) {
161
162 return false;
163 }
164 else {
165
166
167 int index=hash(item);
168 A4LinkedList t=table[index];
169
170 if(t.isEmpty()) {
171 size++;
172 t.insertAtBack(item);
173 }
174 }
175
176
177 if (loadFactor() > LOADFACTOR_MAX){
178 System.out.println("RESIZE");
179 // to be completed: resize the hash table
180
181 // to be completed: re-insert every element of every list of the old hash table.
182 int newtable=tableSize*2;
183 int newtableSize=nextPrime(newtable);
184 int total=0;
185 for(int i=0;i<tableSize;i++) {
186 A4LinkedList t=table[i];
187 total+=t.size();
188 }
189 for(int j=0;j<total;j++) {
190 int n=0;
191 while(n<tableSize) {
192 A4LinkedList t=table[index];
193 Comparable[]a=t.toArray();
194 }
195
196 }
197
198 }
199 return true;
200 }
201
202 // Remove an item from the hash table.
203 // If item exists, remove and return true.
204 // Otherwise, hash table is unchanged and return false.
205 public boolean remove(String item) {
206 // to be completed
207 if(contains(item)) {
208 int index=hash(item);
209 table[index].remove(item);
210 return true;
211 }
212
213
214 return false;
215 }
216}