Skip to content

Instantly share code, notes, and snippets.

@kuzemkon
Created June 13, 2016 15:00
Show Gist options
  • Save kuzemkon/b666e1eec41209310c337d0c074219d8 to your computer and use it in GitHub Desktop.
Save kuzemkon/b666e1eec41209310c337d0c074219d8 to your computer and use it in GitHub Desktop.
Hash tables link collision
public class LinkCollision {
private ArrayList<Integer>[] result;
private int length;
private double hashWay;
LinkCollision(int length, double hashWay){
this.length = length;
this.hashWay = hashWay;
this.result = new ArrayList[length];
resultIn();
}
private void resultIn(){
for (int i=0; i<this.length; i++){
result[i] = new ArrayList<Integer>();
}
}
private int hashDevision(int key){
return key%this.length;
}
private int hashMultiply(int key, double k){
// System.out.println((k%1));
return (int)(this.length*((key*k)%1));
}
public void insert(int key){
int i;
if((int)hashWay==2){
i=hashDevision(key);
} else {
i=hashMultiply(key,hashWay);
}
result[i].add(key);
}
public int find(int key){
int i;
if((int)hashWay==2){
i=hashDevision(key);
} else {
i=hashMultiply(key,hashWay);
}
if(result[i].contains(key)){
return i;
} else {
return -1;
}
}
public void delete(int key){
int i;
if((int)hashWay==2){
i=hashDevision(key);
} else {
i=hashMultiply(key,hashWay);
}
if(result[i].contains(key)){
for (int j=0; j<result[i].size(); j++){
if(key==result[i].get(j)){
result[i].remove(j);
}
}
}
}
public ArrayList[] getResult(){
return this.result;
}
}
// Menu
LinkCollision link = new LinkCollision(5,2);
int[] keys = {10,22,31,4,15,28,17,88,59};
for (int key : keys) {
link.insert(key);
}
DataInputStream d = new DataInputStream(System.in);
ArrayList[] r = link.getResult();
for (int i=0; i<r.length; i++){
System.out.println(r[i].toString());
}
loop: while (true){
int o = -1;
System.out.println("Select function: 0 - insert, 1 - find, 2 - delete, 3 - exit");
try {
o = Integer.parseInt(d.readLine());
} catch (Exception e){
System.out.println(e);
}
switch (o){
case 0:
System.out.println("Input value to insert");
try {
o = Integer.parseInt(d.readLine());
link.insert(o);
r = link.getResult();
for (int i=0; i<r.length; i++){
System.out.println(r[i].toString());
}
} catch (Exception e){
System.out.println(e);
}
break;
case 1:
System.out.println("Which value you want to find?");
try {
o = Integer.parseInt(d.readLine());
System.out.println(link.find(o));
} catch (Exception e){
System.out.println(e);
}
break;
case 2:
System.out.println("Which value you want to delete?");
try {
o = Integer.parseInt(d.readLine());
link.delete(o);
r = link.getResult();
for (int i=0; i<r.length; i++){
System.out.println(r[i].toString());
}
} 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