import java.util.Random;
class hashTable {
Record[] table;
int size;
int a1, a2;
hashTable(int size)
{
this.size = size;
table = new Record[size];
for (int i=0; i<size; i++)
table[i] = null;
hashFunction();
}
public void hashFunction()
{
a1 = rand.nextInt(size);
a2 = rand.nextInt(size);
}
public void put(int key, int value)
{
System.
out.
println("*** Adding to hashtable ***"); int hash = (key*a1) % size;
if(table[hash] == null)
table[hash] = new Record(key, value);
else
{
hash = (key*a2) % size;
if(table[hash] == null)
table[hash] = new Record(key, value);
else
System.
out.
println("Collision happens"); }
}
public String searchKey
(int key
) {
System.
out.
println("**** Searching ****"); int hash = (key*a1) % size;
if(table[hash] != null)
{
getKey += table[hash].getKey() + " " + table[hash].getValue() + "\n";
hash = (key*a2) % size;
if(table[hash] != null)
getKey += table[hash].getKey() + " " + table[hash].getValue() + "\n";
return getKey;
}
else
return "No available key";
}
public void deleteKey(int key)
{
System.
out.
println("**** Deleting ****"); int hash = (key*a1) % size;
if(table[hash] != null)
{
table[hash] = null;
hash = (key*a2) % size;
if(table[hash] != null)
table[hash] = null;
System.
out.
println( "Deleted" ); }
else
System.
out.
println( "No available key" ); }
{
String hashTable
= "\nKey\t-> \tValue\n"; int i = 0;
while(i < size)
{
if(table[i] == null)
{
i++;
continue;
}
hashTable += table[i].getKey() + "\t->\t" + table[i].getValue();
if(i < this.size - 1)
hashTable += "\n";
i++;
}
return hashTable;
}
public static void main
(String[] args
) {
hashTable ht = new hashTable(512);
ht.put(5, 40);
ht.put(5, 3);
ht.put(4, 2);
ht.put(5, 5);
ht.put(9, 10);
ht.put(50, 15);
System.
out.
println(ht.
searchKey(5));
ht.deleteKey(5);
}
}
class Record
{
private int value;
private int key;
Record()
{
value = 0;
key = 0;
}
Record(int key, int value)
{
this.value = value;
this.key = key;
}
public void setKey(int key)
{
this.key = key;
}
public int getKey()
{
return key;
}
public int getValue()
{
return value;
}
}
aW1wb3J0IGphdmEudXRpbC5SYW5kb207CgoKY2xhc3MgaGFzaFRhYmxlIHsKCVJlY29yZFtdIHRhYmxlOwoJaW50IHNpemU7CglpbnQgYTEsIGEyOwoJCgloYXNoVGFibGUoaW50IHNpemUpCgl7CgkJdGhpcy5zaXplID0gc2l6ZTsKCQl0YWJsZSA9IG5ldyBSZWNvcmRbc2l6ZV07CgkJCgkJZm9yIChpbnQgaT0wOyBpPHNpemU7IGkrKykKICAgICAgICAgICAgdGFibGVbaV0gPSBudWxsOwoKCQloYXNoRnVuY3Rpb24oKTsKCX0KCQoJcHVibGljIHZvaWQgaGFzaEZ1bmN0aW9uKCkKCXsKCQlSYW5kb20gcmFuZCA9IG5ldyBSYW5kb20oKTsKCQlhMSA9IHJhbmQubmV4dEludChzaXplKTsKCQlhMiA9IHJhbmQubmV4dEludChzaXplKTsJCQoJfQoJCglwdWJsaWMgdm9pZCBwdXQoaW50IGtleSwgaW50IHZhbHVlKSAKCXsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIioqKiBBZGRpbmcgdG8gaGFzaHRhYmxlICoqKiIpOwoJCWludCBoYXNoID0gKGtleSphMSkgJSBzaXplOwoJCQoJCWlmKHRhYmxlW2hhc2hdID09IG51bGwpCgkJCXRhYmxlW2hhc2hdID0gbmV3IFJlY29yZChrZXksIHZhbHVlKTsKCQllbHNlCgkJewoJCQloYXNoID0gKGtleSphMikgJSBzaXplOwoJCQlpZih0YWJsZVtoYXNoXSA9PSBudWxsKQoJCQkJdGFibGVbaGFzaF0gPSBuZXcgUmVjb3JkKGtleSwgdmFsdWUpOwoJCQllbHNlCgkJCQlTeXN0ZW0ub3V0LnByaW50bG4oIkNvbGxpc2lvbiBoYXBwZW5zIik7CgkJfQkKCX0KCXB1YmxpYyBTdHJpbmcgc2VhcmNoS2V5KGludCBrZXkpIAoJewoJCVN5c3RlbS5vdXQucHJpbnRsbigiKioqKiBTZWFyY2hpbmcgKioqKiIpOwoJCVN0cmluZyBnZXRLZXkgPSAiIjsKCQlpbnQgaGFzaCA9IChrZXkqYTEpICUgc2l6ZTsKCQkKCQlpZih0YWJsZVtoYXNoXSAhPSBudWxsKQoJCXsKCQkJZ2V0S2V5ICs9IHRhYmxlW2hhc2hdLmdldEtleSgpICsgIiAiICsgdGFibGVbaGFzaF0uZ2V0VmFsdWUoKSArICJcbiI7CgkJCQoJCQloYXNoID0gKGtleSphMikgJSBzaXplOwoJCQkKCQkJaWYodGFibGVbaGFzaF0gIT0gbnVsbCkKCQkJCWdldEtleSArPSB0YWJsZVtoYXNoXS5nZXRLZXkoKSArICIgIiArIHRhYmxlW2hhc2hdLmdldFZhbHVlKCkgKyAiXG4iOwoJCQkKCQkJcmV0dXJuIGdldEtleTsKCQl9CgkJZWxzZQoJCQlyZXR1cm4gIk5vIGF2YWlsYWJsZSBrZXkiOwoJfQoJcHVibGljIHZvaWQgZGVsZXRlS2V5KGludCBrZXkpCgl7CgkJU3lzdGVtLm91dC5wcmludGxuKCIqKioqIERlbGV0aW5nICoqKioiKTsKCQlpbnQgaGFzaCA9IChrZXkqYTEpICUgc2l6ZTsKCQkKCQlpZih0YWJsZVtoYXNoXSAhPSBudWxsKQoJCXsKCQkJdGFibGVbaGFzaF0gPSBudWxsOwoJCQkKCQkJaGFzaCA9IChrZXkqYTIpICUgc2l6ZTsKCQkJCgkJCWlmKHRhYmxlW2hhc2hdICE9IG51bGwpCgkJCQl0YWJsZVtoYXNoXSA9IG51bGw7CgkJCQoJCQlTeXN0ZW0ub3V0LnByaW50bG4oICJEZWxldGVkIiApOwoJCX0KCQllbHNlCgkJCVN5c3RlbS5vdXQucHJpbnRsbiggIk5vIGF2YWlsYWJsZSBrZXkiICk7Cgl9CgkKCXB1YmxpYyBTdHJpbmcgdG9TdHJpbmcoKSAKCXsKCQlTdHJpbmcgaGFzaFRhYmxlID0gIlxuS2V5XHQtPiBcdFZhbHVlXG4iOwoJCWludCBpID0gMDsKCSAgIAoJCXdoaWxlKGkgPCBzaXplKSAKCQl7CgkJCWlmKHRhYmxlW2ldID09IG51bGwpIAoJCQl7CgkJCQlpKys7CgkJCQljb250aW51ZTsKCQkJfQoJICAgICAgICAKCQkJaGFzaFRhYmxlICs9IHRhYmxlW2ldLmdldEtleSgpICsgIlx0LT5cdCIgKyB0YWJsZVtpXS5nZXRWYWx1ZSgpOwoJCQkKCQkJaWYoaSA8IHRoaXMuc2l6ZSAtIDEpIAoJCQkJaGFzaFRhYmxlICs9ICJcbiI7CgoJCQlpKys7CgkJfQkgICAgCgkJcmV0dXJuIGhhc2hUYWJsZTsKCX0KCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIAoJewoJCWhhc2hUYWJsZSBodCA9IG5ldyBoYXNoVGFibGUoNTEyKTsKCQlodC5wdXQoNSwgNDApOwoJCWh0LnB1dCg1LCAzKTsKCQlodC5wdXQoNCwgMik7CgkJaHQucHV0KDUsIDUpOwoJCWh0LnB1dCg5LCAxMCk7CgkJaHQucHV0KDUwLCAxNSk7CgkJCgkJU3lzdGVtLm91dC5wcmludGxuKGh0LnNlYXJjaEtleSg1KSk7CgkJCgkJU3lzdGVtLm91dC5wcmludGxuKGh0KTsKCQkKCQlodC5kZWxldGVLZXkoNSk7CgkJCgkJU3lzdGVtLm91dC5wcmludGxuKCBodCApOwoJfQoKfQpjbGFzcyBSZWNvcmQKewoJcHJpdmF0ZQlpbnQgdmFsdWU7Cglwcml2YXRlIGludCBrZXk7CgkKCVJlY29yZCgpCgl7CgkJdmFsdWUgPSAwOyAgCgkJa2V5ID0gMDsKCX0KCVJlY29yZChpbnQga2V5LCBpbnQgdmFsdWUpCgl7CgkJdGhpcy52YWx1ZSA9IHZhbHVlOwoJCXRoaXMua2V5ID0ga2V5OwoJfQoJcHVibGljIHZvaWQgc2V0S2V5KGludCBrZXkpCgl7CgkJdGhpcy5rZXkgPSBrZXk7Cgl9CglwdWJsaWMgaW50IGdldEtleSgpCgl7CgkJcmV0dXJuIGtleTsKCX0KCXB1YmxpYyBpbnQgZ2V0VmFsdWUoKQoJewoJCXJldHVybiB2YWx1ZTsKCX0KfQ==