Skip to content

Instantly share code, notes, and snippets.

@kuzemkon
Created June 13, 2016 15:02
Show Gist options
  • Save kuzemkon/e6aa11688dc35b9f9da6aa20710aee7f to your computer and use it in GitHub Desktop.
Save kuzemkon/e6aa11688dc35b9f9da6aa20710aee7f to your computer and use it in GitHub Desktop.
Hash tables open addressing
public class OpenAdressing {
private int length;
private int[] result;
private int c1, c2;
private String method;
OpenAdressing(int length){
this.length = length;
result = new int[length];
this.method = "linear";
arrayIni();
}
OpenAdressing(int length, String method){
this.length = length;
result = new int[length];
this.method = method;
arrayIni();
}
OpenAdressing(int length, int c1, int c2){
this.length = length;
result = new int[length];
this.c1 = c1;
this.c2 = c2;
this.method = "quadratic";
arrayIni();
}
public int insert(int key){
int i=0;
int j;
do{
switch (this.method){
case "linear":
j = linearHash(key,i);
break;
case "quadratic":
j = quadraticHash(key,i);
break;
case "double":
j = doubleHash(key,i);
break;
default:
j = linearHash(key,i);
break;
}
if(this.result[j]==-1){
this.result[j] = key;
return j;
} else {
i++;
}
}while (i!=this.length);
return -2;
}
public void delete(int key){
for (int i=0; i<this.result.length; i++){
if(this.result[i]==key){
this.result[i]=-1;
break;
}
}
}
public int search(int key){
int i=0;
int j;
do {
switch (this.method){
case "linear":
j = linearHash(key,i);
break;
case "quadratic":
j = quadraticHash(key,i);
break;
case "double":
j = doubleHash(key,i);
break;
default:
j = linearHash(key,i);
break;
}
if(this.result[j]==key){
return j;
} else {
i++;
}
}while (this.result[j]!=-1 || i!=this.length);
return -1;
}
public int[] getResult(){
return this.result;
}
private int hash(int key){
return key%this.length;
}
private int hash1(int key){
return (1+(key%(this.length-2)));
}
private int linearHash(int key, int i){
return (hash(key) + i)%this.length;
}
private int quadraticHash(int key, int i){
return (int) ((hash(key) + this.c1*i + this.c2*Math.pow(i,2))%this.length);
}
private int doubleHash(int key, int i){
return (hash(key) + i*hash1(key))%this.length;
}
private void arrayIni(){
for (int i=0; i<result.length; i++){
result[i] = -1;
}
}
}
//Menu
OpenAdressing table = new OpenAdressing(10);
int[] keys = {10,22,31,4,15,28,17,88,59};
for (int key : keys) {
System.out.print(table.insert(key)+" ");
}
int[] result = table.getResult();
// table.delete(10);
System.out.println();
for (int aResult : result) {
System.out.print(aResult+" ");
}
System.out.println();
DataInputStream d = new DataInputStream(System.in);
loop: while (true){
System.out.println("Select function: 0 - insert, 1 - find, 2 - delete, 3 - exit");
int o=-1;
try {
o = Integer.parseInt(d.readLine());
} catch (Exception e){
System.out.println(e);
}
switch (o){
case 0:
System.out.println("Which value do you want to insert?");
try {
o = Integer.parseInt(d.readLine());
System.out.println(table.insert(o));
result = table.getResult();
for (int aResult : result) {
System.out.print(aResult+" ");
}
System.out.println();
} catch (Exception e){
System.out.println(e);
}
break;
case 1:
System.out.println("Which value do you want to find?");
try {
o = Integer.parseInt(d.readLine());
System.out.println(table.search(o));
} catch (Exception e){
System.out.println(e);
}
break;
case 2:
System.out.println("Which value do you want to delete?");
try {
o = Integer.parseInt(d.readLine());
table.delete(o);
result = table.getResult();
for (int aResult : result) {
System.out.print(aResult+" ");
}
System.out.println();
} catch (Exception e){
System.out.println(e);
}
break;
case 3:
break loop;
default:
System.out.println("SOSATY");
break;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment