patternjavaMinor
Simple Chaining Implementation of HashMap
Viewed 0 times
implementationsimplehashmapchaining
Problem
I'm practicing writing my own simple version of a Java HashMap. I don't have much experience with generics in Java.
public class HashMap {
private class Entry {
private K key;
private V value;
private Entry next;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
}
private final static int TABLE_SIZE = 32;
private Entry[] table;
public HashMap() {
table = new Entry[TABLE_SIZE];
}
private int hash(K key) {
return Math.abs(key.hashCode() % TABLE_SIZE);
}
public V get(K key) {
int index = hash(key);
Entry curr = table[index];
while (curr != null) {
if (curr.getKey().equals(key)) {
return (V) curr.getValue();
}
curr = curr.next;
}
return null;
}
public V remove(K key) {
int hash = hash(key);
Entry curr = table[hash];
if (curr == null) {
return null;
}
if (curr.getKey().equals(key)) {
V temp = (V) curr.getValue();
table[hash] = curr.next;
return temp;
}
while (curr.next != null) {
if (curr.next.getKey().equals(key)) {
V temp = (V) curr.next.getValue();
curr.next = curr.next.next;
return temp;
}
}
return null;
}
public void put(K key, V value) {
int hash = hash(key);
Entry curr = table[hash];
if (curr == null) {
table[hash(key)] = new Entry(key, value);
} else {
while (curr.next != null) {
curr = curr.next;
}
curr.next = new Entry(key, value);
}
}
}Solution
Choose a better value for
You should specially avoid powers of 2 for this value in the division method. Why?
Because for
Put method:
Your
But you probably want to update the value if the key is already there :
TABLE_SIZE: You should specially avoid powers of 2 for this value in the division method. Why?
Because for
TABLE_SIZE equal to the hash will simply be the p lowest-order bits. Is better to design a hash function that depends on all the bits of the key, so a prime number not too close to a power of 2 is generally a better choice. Put method:
Your
put method can be greatly simplified and also you could implement it so it doesn't depend on the load factor. By adding a constructor in Entry that also receives the next element you will have something like this: public void put(K key, V value) {
int hash = hash(key);
table[hash] = new Entry(key, value, table[hash]);
}But you probably want to update the value if the key is already there :
public void put(K key, V value) {
Entry n = get(key);
if(n != null) {
n.value = value;
}
else {
int hash = hash(key);
table[hash] = new Entry(key, value, table[hash]);
}
}Code Snippets
public void put(K key, V value) {
int hash = hash(key);
table[hash] = new Entry(key, value, table[hash]);
}public void put(K key, V value) {
Entry n = get(key);
if(n != null) {
n.value = value;
}
else {
int hash = hash(key);
table[hash] = new Entry(key, value, table[hash]);
}
}Context
StackExchange Code Review Q#136491, answer score: 2
Revisions (0)
No revisions yet.