Skip to content

Instantly share code, notes, and snippets.

@jzaefferer
Forked from anonymous/MyHashMap.java
Created May 31, 2016 15:56
Show Gist options
  • Save jzaefferer/37113a1fcf7c39524fc935d0caf92a35 to your computer and use it in GitHub Desktop.
Save jzaefferer/37113a1fcf7c39524fc935d0caf92a35 to your computer and use it in GitHub Desktop.
/**
*
* @author Algorithm and Datastructures Team SS2016
* @version 1.0
*
*/
import java.lang.RuntimeException;
public class MyHashMap {
/**
* Use this array to store the values
* DO NOT MODIFY OR REMOVE THIS Attribute. Our tests rely on it.
*/
private Student[] array;
/**
* Tries inserting a Student into the hash map.
* Throws RunTimeException, if the student is already in the table or the table is full.
*/
public void add(Student s){
for(int k = 0; k < array.length; k++) {
if(array[k] == null) {
array[k] = s;
return;
} else if(array[k].equals(s) || array[k] != null) {
throw new RuntimeException("error");
}
}
}
/**
* Try removing a Student from the hash table.
* You should use the same implementation for remove discussed in the tutorial.
* You should NOT use the lazy deletion strategy (adding a special flag key indicating a deleted key)
* See https://en.wikipedia.org/wiki/Linear_probing#Deletion for more details about the algorithm!
* Throw RunTimeException if the hash table contained the Student
*/
public void remove(Student s){
// TO DO
for(Student m : array) {
if(m == s) {
throw new RuntimeException("error");
}
}
}
/**
* Returns true, if the hash table contains the given Student
*/
public boolean contains(Student s){
for(Student i : array) {
if(i == s) {
return true;
}
}
return false;
}
/**
* @param h Hashvalue to search for
* @return Number of Student in the hash table that have the hashvalue h
*/
public int getNumberStudentsWithHashvalue(int h){
int n = 0;
// TO DO
h = hashvalue;
array = new Student[capacity];
for(int j = 0; j < array.length; j++) {
if(array[j].equals(h)) {
n++;
}
}
return n;
}
/**
* Doubles the size of the hash table. Recomputes the position of all elements using the
* new function.
*/
public void resize(){
Student[] newtable = array;
array = new Student[array.length*2];
for(int n=0; n < array.length; n++) {
if(array[n] != null) {
newtable = new Student[array.length*2];
}
}
}
/**
* This method return the array in which the strings are stored.
* DO NOT MODIFY OR REMOVE THIS METHOD. Our tests rely on it.
*/
public Student[] getArray(){
return array;
}
/**
* DO NOT MODIFY OR REMOVE THIS METHOD. Our tests rely on it.
*/
public void setArray(Student[] array){
this.array = array;
}
/**
* Runs the hash function for Student s (dependent on the size of the hash table)
* DO NOT MODIFY OR REMOVE THIS METHOD. Our tests rely on it.
* @param s Student
* @return the hash value for a student. (The position where it would be saved given no collisions)
*/
public int hashFunction(Student s){
int hashvalue = Math.abs(s.hashCode()) % array.length;
return hashvalue;
}
/**
* Constructor to initialize the hash with a given capacity
* DO NOT MODIFY OR REMOVE THIS METHOD. Our tests rely on it.
*/
public MyHashMap(int capacity){
array = new Student[capacity];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment