JetBrains Academy: Hash table in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki
Rehashing:
One limitation of the described hash table is that it can store only a fixed number of entries. Your task here is to address the limitation and implement a rehash method. It should work as follows: when a current table is full, it allocates a new array of a larger size, iterates through the old array and puts each element to the new array. Then, the new array is used to insert new entries. Assume that the initial size of a table is 5 and the scaling factor is 2.
Input: the first line contains an integer n, the number of insertions. Each of the following lines contains an entry: an integer key and a string value.
Output: the state of the table after all insertions. Use the toString method to produce an output.
import java.io.*;
public class Main {
private static class TableEntry<T> {
private final int key;
private final T value;
public TableEntry(int key, T value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public T getValue() {
return value;
}
}
private static class HashTable<T> {
private static final int DEFAULT_INITIAL_CAPACITY = 5;
private static final int SCALING_FACTOR = 2;
private int size;
private TableEntry[] table;
public HashTable() {
this.size = 0;
table = new TableEntry[DEFAULT_INITIAL_CAPACITY];
}
public boolean put(int key, T value) {
rehash();
int idx = findKey(key);
if (idx == -1) {
return false;
}
table[idx] = new TableEntry(key, value);
size++;
return true;
}
public T get(int key) {
int idx = findKey(key);
if (idx == -1 || table[idx] == null) {
return null;
}
return (T) table[idx].getValue();
}
private int findKey(int key) {
int hash = key % table.length;
while (!(table[hash] == null || table[hash].getKey() == key)) {
hash = (hash + 1) % table.length;
if (hash == key % table.length) {
return -1;
}
}
return hash;
}
private void rehash() {
if (table.length == size) {
TableEntry[] old = table;
table = new TableEntry[SCALING_FACTOR * size];
size = 0;
for (TableEntry entry : old) {
this.put(entry.getKey(), (T) entry.getValue());
}
}
}
@Override
public String toString() {
StringBuilder tableStringBuilder = new StringBuilder();
for (int i = 0; i < table.length; i++) {
if (table[i] == null) {
tableStringBuilder.append(i + ": null");
} else {
tableStringBuilder.append(i + ": key=" + table[i].getKey()
+ ", value=" + table[i].getValue());
}
if (i < table.length - 1) {
tableStringBuilder.append("\n");
}
}
return tableStringBuilder.toString();
}
}
public static void main(String[] args) {
HashTable<String> table = new HashTable<>();
try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
int puttingLines = Integer.parseInt(reader.readLine());
for (int i = 0; i < puttingLines; i++) {
String[] line = reader.readLine().split("\\s+");
int key = Integer.parseInt(line[0]);
String name = line[1];
table.put(key, name);
}
System.out.println(table.toString());
} catch (IOException e) {
e.printStackTrace();
}
}
}Removing:
Another limitation of the described hash table is that it does not support removing data. Your task here is to implement a remove method that removes an element with a specified key from a hash table.
Input: the first line contains two numbers n and m separated by a space. Each of the next n lines contains an entry: an integer key and a string value. Each of the following m lines contains an integer key to remove.
Output: A state of a hash table after n insertions and m removings. Assume that the initial size of a table is 5, the scaling factor is 2. Use the toString method to produce an output.
import java.io.*;
public class Main {
private static class TableEntry<T> {
private final int key;
private final T value;
private boolean removed;
public TableEntry(int key, T value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public T getValue() {
return value;
}
public void remove() {
removed = true;
}
public boolean isRemoved() {
return removed;
}
}
private static class HashTable<T> {
private static final int DEFAULT_INITIAL_CAPACITY = 5;
private static final int SCALING_FACTOR = 2;
private int size;
private TableEntry[] table;
public HashTable() {
this.size = 0;
table = new TableEntry[DEFAULT_INITIAL_CAPACITY];
}
public boolean put(int key, T value) {
ensureCapacity();
int idx = findKey(key);
if (idx == -1) {
return false;
}
table[idx] = new TableEntry(key, value);
size++;
return true;
}
private void ensureCapacity() {
if (table.length == size) {
TableEntry[] old = table;
table = new TableEntry[SCALING_FACTOR * size];
size = 0;
for (TableEntry entry : old) {
this.put(entry.getKey(), (T) entry.getValue());
}
}
}
public T get(int key) {
int idx = findKey(key);
if (idx == -1 || table[idx] == null) {
return null;
}
return (T) table[idx].getValue();
}
public void remove(int key) {
int idx = findKey(key);
if (idx != -1 && table[idx] != null) {
table[idx].remove();
}
}
private int findKey(int key) {
int hash = key % table.length;
while (!(table[hash] == null || table[hash].getKey() == key)) {
hash = (hash + 1) % table.length;
if (hash == key % table.length) {
return -1;
}
}
return hash;
}
@Override
public String toString() {
StringBuilder tableStringBuilder = new StringBuilder();
for (int i = 0; i < table.length; i++) {
if (table[i] == null) {
tableStringBuilder.append(i + ": null");
} else {
tableStringBuilder.append(i + ": key=" + table[i].getKey()
+ ", value=" + table[i].getValue()
+ ", removed=" + table[i].isRemoved());
}
if (i < table.length - 1) {
tableStringBuilder.append("\n");
}
}
return tableStringBuilder.toString();
}
}
public static void main(String[] args) {
HashTable<String> table = new HashTable<>();
String splitter = "\\s+";
try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
String[] parameters = reader.readLine().split(splitter);
int puttingLines = Integer.parseInt(parameters[0]);
int removingLines = Integer.parseInt(parameters[1]);
for (int i = 0; i < puttingLines; i++) {
String[] line = reader.readLine().split(splitter);
int key = Integer.parseInt(line[0]);
String name = line[1];
table.put(key, name);
}
for (int i = 0; i < removingLines; i++) {
String[] line = reader.readLine().split(splitter);
int key = Integer.parseInt(line[0]);
table.remove(key);
}
System.out.println(table.toString());
} catch (IOException e) {
e.printStackTrace();
}
}
}Phone Book:
Let's sum up and put all the implementation details together. The task is to use the described hash table to implement a simple phone book.
Input: the first line contains an integer n, the number of queries. Each of the next n lines contains a query in one of the following formats:
putid number — put an entry (id, number) to a table;getid — get a phone number with a specified id;removeid — remove a phone number with a specified id.
Output: for each get query, print either the phone number that corresponds to the id or -1 if no number with the given id exists.
import java.io.*;
public class Main {
private static class TableEntry<T> {
private final int key;
private final T value;
private boolean removed;
public TableEntry(int key, T value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public T getValue() {
return value;
}
public void remove() {
removed = true;
}
public boolean isRemoved() {
return removed;
}
}
private static class HashTable<T> {
private final int size;
private final TableEntry[] table;
public HashTable(int size) {
this.size = size;
table = new TableEntry[size];
}
public boolean put(int key, T value) {
int idx = findKey(key);
if (idx == -1) {
return false;
}
table[idx] = new TableEntry(key, value);
return true;
}
public T get(int key) {
int idx = findKey(key);
if (idx == -1 || table[idx] == null) {
return null;
}
return (T) table[idx].getValue();
}
public void remove(int key) {
int idx = findKey(key);
if (idx != -1 && table[idx] != null) {
table[idx].remove();
table[idx] = null;
}
}
public boolean isRemoved(int key) {
int idx = findKey(key);
if (idx == -1 || table[idx] == null) {
return true;
}
return table[idx].isRemoved();
}
private int findKey(int key) {
int hash = key % size;
while (!(table[hash] == null || table[hash].getKey() == key)) {
hash = (hash + 1) % size;
if (hash == key % size) {
return -1;
}
}
return hash;
}
}
private static class InputUtils {
private static Command analyze(String command) {
if ("put".equals(command)) {
return Command.PUT;
} else if ("get".equals(command)) {
return Command.GET;
} else if ("remove".equals(command)) {
return Command.REMOVE;
} else {
throw new AssertionError("Unsupported operation: " + command + ", provide: put / get / remove");
}
}
public static <T> void run(String inputLine, HashTable<T> table) {
String[] entry = inputLine.split("\\s+");
String command = entry[0];
int key = Integer.parseInt(entry[1]);
T number = (T) (entry.length > 2 ? entry[2] : "");
Command cmd = analyze(command);
cmd.apply(key, number, table);
}
}
private enum Command {
PUT {
@Override
public <T> void apply(int key, T number, HashTable<T> table) {
table.put(key, number);
}
}, GET {
@Override
public <T> void apply(int key, T number, HashTable<T> table) {
System.out.println(table.get(key) == null ? -1 : table.get(key));
}
}, REMOVE {
@Override
public <T> void apply(int key, T number, HashTable<T> table) {
table.remove(key);
}
};
public abstract <T> void apply(int key, T number, HashTable<T> table);
}
public static void main(String[] args) {
int lines;
try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
lines = Integer.parseInt(reader.readLine());
HashTable<String> table = new HashTable<>(lines);
for (int i = 0; i < lines; i++) {
String entry = reader.readLine();
InputUtils.run(entry, table);
}
} catch (IOException e) {
e.printStackTrace();
}
}
}Implementing the EntrySet method:
The Java standard Hashtable class has a method called entrySet that allows users to iterate over the entries of a table. Your task here is to implement a simplified version of the method for the described hash table.
Input: the first line contains an integer n - the number of queries. Each of the next n lines contains two records separates by space: the first represents an integer key, the other corresponds to a string value.
Output: for each unique id, print all entries associated with the id. All ids can be printed in arbitrary order, entries should be printed in the same order as they were inserted into a table.
import java.util.stream.Collectors;
import java.util.*;
import java.io.*;
public class Main {
private static class TableEntry<T> {
private final int key;
private final T value;
public TableEntry(int key, T value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public T getValue() {
return value;
}
@Override
public String toString() {
return key + ": " + value;
}
}
private static class HashTable<T> {
private final int size;
private final TableEntry[] table;
public HashTable(int size) {
this.size = size;
table = new TableEntry[size];
}
private int findKey(int key) {
int hash = key % size;
while (!(table[hash] == null || table[hash].getKey() == key)) {
hash = (hash + 1) % size;
if (hash == key % size) {
return -1;
}
}
return hash;
}
private int rehash(int key) {
return key % size;
}
public boolean put(int key, T value) {
int idx = rehash(key);
if (idx == -1) {
return false;
}
if (table[idx] != null && table[idx].getKey() == key) {
List<T> set = (List<T>) table[idx].getValue();
set.add(value);
} else {
List<T> valueSet = new ArrayList<>();
valueSet.add(value);
table[idx] = new TableEntry<>(key, valueSet);
}
return true;
}
public T get(int key) {
int idx = findKey(key);
if (idx == -1 || table[idx] == null) {
return null;
}
return (T) table[idx].getValue();
}
public Set<TableEntry<T>> entrySet() {
Set<TableEntry<T>> entries = new HashSet<>();
for (TableEntry<T> tableEntry : table) {
if (tableEntry != null) {
entries.add(tableEntry);
}
}
return entries;
}
}
public static void main(String[] args) {
int lines;
int key;
String value;
try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
lines = Integer.parseInt(reader.readLine());
HashTable<String> table = new HashTable<>(lines);
for (int i = 0; i < lines; i++) {
String[] entry = reader.readLine().split("\\s+");
key = Integer.parseInt(entry[0]);
value = entry[1];
table.put(key, value);
}
for (TableEntry entry : table.entrySet()) {
int k = entry.getKey();
System.out.printf("%d: ", k);
List<String> entries = (List) entry.getValue();
String names = entries.stream().collect(Collectors.joining(" "));
System.out.println(names);
}
} catch (IOException e) {
e.printStackTrace();
}
}
}