Skip to content

Instantly share code, notes, and snippets.

@amadamala
Last active June 28, 2022 03:55
Show Gist options
  • Save amadamala/3cdd53cb5a6b1c1df540981ab0245479 to your computer and use it in GitHub Desktop.
Save amadamala/3cdd53cb5a6b1c1df540981ab0245479 to your computer and use it in GitHub Desktop.
HashTable implementation in Java
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);
}
}
@AnghelLeonard
Copy link

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

@AnghelLeonard
Copy link

Pay attention to the hash function. It may return negative values. For example, getHash("carina") = -8

@Arkhypov
Copy link

You need to impl remove as well.

@Akash311998
Copy link

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;
}

}

@VictorHugoLeme
Copy link

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