Last active
June 28, 2022 03:55
-
-
Save amadamala/3cdd53cb5a6b1c1df540981ab0245479 to your computer and use it in GitHub Desktop.
HashTable implementation in Java
This file contains 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 HashTable { | |
private static int INITIAL_SIZE = 16; | |
private HashEntry[] entries = new HashEntry[INITIAL_SIZE]; | |
public void put(String key, String value) { | |
int hash = getHash(key); | |
final HashEntry hashEntry = new HashEntry(key, value); | |
if(entries[hash] == null) { | |
entries[hash] = hashEntry; | |
} | |
// If there is already an entry at current hash | |
// position, add entry to the linked list. | |
else { | |
HashEntry temp = entries[hash]; | |
while(temp.next != null) { | |
temp = temp.next; | |
} | |
temp.next = hashEntry; | |
} | |
} | |
/** | |
* Returns 'null' if the element is not found. | |
*/ | |
public String get(String key) { | |
int hash = getHash(key); | |
if(entries[hash] != null) { | |
HashEntry temp = entries[hash]; | |
// Check the entry linked list for march | |
// for the given 'key' | |
while( !temp.key.equals(key) | |
&& temp.next != null ) { | |
temp = temp.next; | |
} | |
return temp.value; | |
} | |
return null; | |
} | |
private int getHash(String key) { | |
// piggy backing on java string | |
// hashcode implementation. | |
return key.hashCode() % INITIAL_SIZE; | |
} | |
public static class HashEntry { | |
String key; | |
String value; | |
// Linked list of same hash entries. | |
HashEntry next; | |
public HashEntry(String key, String value) { | |
this.key = key; | |
this.value = value; | |
this.next = null; | |
} | |
@Override | |
public String toString() { | |
return "[" + key + ", " + value + "]"; | |
} | |
} | |
@Override | |
public String toString() { | |
int bucket = 0; | |
StringBuilder hashTableStr = new StringBuilder(); | |
for (HashEntry entry : entries) { | |
if(entry == null) { | |
continue; | |
} | |
hashTableStr.append("\n bucket[") | |
.append(bucket) | |
.append("] = ") | |
.append(entry.toString()); | |
bucket++; | |
HashEntry temp = entry.next; | |
while(temp != null) { | |
hashTableStr.append(" -> "); | |
hashTableStr.append(temp.toString()); | |
temp = temp.next; | |
} | |
} | |
return hashTableStr.toString(); | |
} | |
public static void main(String[] args) { | |
HashTable hashTable = new HashTable(); | |
// Put some key values. | |
for(int i=0; i<30; i++) { | |
final String key = String.valueOf(i); | |
hashTable.put(key, key); | |
} | |
// Print the HashTable structure | |
log("**** HashTable ***"); | |
log(hashTable.toString()); | |
log("\nValue for key(20) : " + hashTable.get("20") ); | |
} | |
private static void log(String msg) { | |
System.out.println(msg); | |
} | |
} |
Pay attention to the hash function. It may return negative values. For example, getHash("carina") = -8
You need to impl remove as well.
package hashtable;
import java.util.ArrayList;
import java.util.List;
public class CustomHashTable {
int size = 16;
Entry entries[] = new Entry[size];
public void put(String key,String value){
Entry<String,String> entry = new Entry<>(key, value);
Integer hasCode = hashCode(key);
if(entries[hasCode] == null){
entries[hasCode] = entry;
return;
}
Entry<String,String> temp = entries[hasCode];
while(temp != null) {
if(temp.key.equalsIgnoreCase(key)){
temp.value = value;
return;
}
temp = temp.next;
}
temp.next = entry;
}
public String get(String key){
Integer hasCode = hashCode(key);
if(entries[hasCode] == null){
return null;
}
if(entries[hasCode].next != null && ((String)entries[hasCode].key).equalsIgnoreCase(key))
return (String)entries[hasCode].value;
Entry<String,String> temp = entries[hasCode];
while(temp!=null){
if(temp.key.equalsIgnoreCase(key))
return temp.value;
temp=temp.next;
}
return null;
}
public boolean contains(String key){
Integer hasCode = hashCode(key);
if(entries[hasCode] == null){
return false;
}
if(entries[hasCode].next != null && ((String)entries[hasCode].key).equalsIgnoreCase(key))
return true;
Entry<String,String> temp = entries[hasCode];
while(temp!=null){
if(temp.key.equalsIgnoreCase(key))
return true;
temp = temp.next;
}
return false;
}
public boolean remove(String key){
Integer hasCode = hashCode(key);
if(entries[hasCode] == null){
return false;
}
if(entries[hasCode] != null && ((String)entries[hasCode].key).equalsIgnoreCase(key)) {
entries[hasCode] = entries[hasCode].next;
return true;
}
Entry<String,String> temp = entries[hasCode];
Entry<String,String> prevTemp = entries[hasCode];
while(temp!=null){
if(temp.key.equalsIgnoreCase(key)) {
prevTemp.next = temp.next;
return true;
}
prevTemp = temp;
temp = temp.next;
}
return false;
}
public Integer size(){
Integer count = 0;
for(Entry entry:entries){
while (entry!=null){
entry=entry.next;
count++;
}
}
return count;
}
public void print(){
for(Entry entry:entries){
while (entry!=null){
System.out.println("Key "+entry.key+"- value:"+entry.value);
entry = entry.next;
}
}
}
private Integer hashCode(String key){
Integer hash = key.hashCode()>0?key.hashCode()%size:((-1)*key.hashCode())%size;
// System.out.println("HashCode of "+key+" is "+ hash);
return hash;
}
}
class Entry<K,V>{
K key;
V value;
Entry<K,V> next;
public Entry(K key,V value){
this.key = key;
this.value = value;
}
}
Ok, but after this remove method, still can get the removed cell value.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Your get() will not work for a key that doesn't exist. For example:
1 : (a, A) -> (b, B) ->(c, C) -> null
Search get("e") -> hash(e) = 1 -> get(1) => C