Created
June 13, 2016 15:02
-
-
Save kuzemkon/e6aa11688dc35b9f9da6aa20710aee7f to your computer and use it in GitHub Desktop.
Hash tables open addressing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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