Objectives
HashMap is array of buckets to store linkedList's simple structure. Each linkedList consists of agregated in key-value ernty objects with additional references to next entry object. Very important is to create method to point correct Bucket.
Below is diagram which shows inserting entries to HashMap process.
Entry structure
Below is entry structure which implements Map.Entry interface.
static class Entry<K,V> implements Map.Entry<K,V> {
private K key;
private V value;
private Entry<K,V> next;
public Entry(K key, V value){
this.key = key;
this.value = value;
}
public Entry(K key, V value, Entry<K,V> next){
this.key = key;
this.value = value;
this.next = next;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V v) {
this.value = v;
return this.value;
}
public Entry<K, V> getNext() {
return next;
}
public void setNext(Entry<K, V> next) {
this.next = next;
}
}
Bucket
Very important aspect is to create appropriate method to calculate bucket. The method has only one incoming parameter - the calculated hashCode base on key.public static int calculateIndex(int hash) {
return hash & (capacity-1);
}
Main Class
Below is full source code.
package artsci.pl;
import java.util.Map;
/**
*
* @author Artur
*/
public class MyHashMap <K, V> {
private Entry<K,V>[] table;
private final static int capacity = 16;
public MyHashMap(){
table = new Entry[capacity];
}
public void put(K key, V value){
if(key==null)
return;
int hash=key.hashCode();
int index = calculateIndex(hash);
if(table[index] == null){
table[index] = new Entry(key, value);
}else{
boolean isNodeExists = true;
Entry currentNode = table[index];
while (currentNode != null && isNodeExists) {
if(currentNode.getKey().hashCode() == hash && key.equals(currentNode.getKey())){
currentNode.setValue(value);
break;
}
if(currentNode.getNext() != null){
currentNode = currentNode.getNext();
}else{
isNodeExists = false;
table[index] = new Entry(key, value, table[index]);
}
}
}
}
public V get(K key){
if(key==null)
return null;
int hash=key.hashCode();
int index = calculateIndex(hash);
boolean isNodeExists = true;
V out = null;
if(table[index] != null){
Entry currentNode = table[index];
while (currentNode != null && isNodeExists) {
if(currentNode.getKey().hashCode() == hash && key.equals(currentNode.getKey())){
out = (V)currentNode.getValue();
}
if(currentNode.getNext() != null){
currentNode = currentNode.getNext();
}else{
isNodeExists = false;
}
}
}
return out;
}
public static int calculateIndex(int hash) {
return hash & (capacity-1);
}
public String toString(){
String out = "";
for(Entry currentNode : table){
boolean isNodeExists = true;
while (currentNode != null && isNodeExists) {
out += "["+currentNode.getKey()+";"+currentNode.getValue()+"]";
if(currentNode.getNext() != null){
currentNode = currentNode.getNext();
}else{
isNodeExists = false;
}
}
}
return out;
}
public int size(){
int out = 0;
for(Entry currentNode : table){
boolean isNodeExists = true;
while (currentNode != null && isNodeExists) {
out++;
if(currentNode.getNext() != null){
currentNode = currentNode.getNext();
}else{
isNodeExists = false;
}
}
}
return out;
}
static class Entry<K,V> implements Map.Entry<K,V> {
private K key;
private V value;
private Entry<K,V> next;
public Entry(K key, V value){
this.key = key;
this.value = value;
}
public Entry(K key, V value, Entry<K,V> next){
this.key = key;
this.value = value;
this.next = next;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V v) {
this.value = v;
return this.value;
}
public Entry<K, V> getNext() {
return next;
}
public void setNext(Entry<K, V> next) {
this.next = next;
}
}
}
Test Class
package artsci.pl;
import org.junit.Test;
import static org.junit.Assert.*;
/**
*
* @author Artur
*/
public class MyHashMapTest {
public MyHashMapTest() {
}
@Test
public void testMethod() {
MyHashMap <String, String> map = new MyHashMap <String, String>();
for(int i = 0; i< 30; i++){
String key = "KEY_"+i;
map.put(key, "VALUE_".concat(String.valueOf(i)));
System.out.println("Key: "+key+" is in bucket: "+MyHashMap.calculateIndex(key.hashCode()) );
}
System.out.println("Size: "+map.size());
assertTrue(map.size() == 30);
}
}
And the result is below:
Testsuite: artsci.pl.MyHashMapTest
Key: KEY_0 is in bucket: 0
Key: KEY_1 is in bucket: 1
Key: KEY_2 is in bucket: 2
Key: KEY_3 is in bucket: 3
Key: KEY_4 is in bucket: 4
Key: KEY_5 is in bucket: 5
Key: KEY_6 is in bucket: 6
Key: KEY_7 is in bucket: 7
Key: KEY_8 is in bucket: 8
Key: KEY_9 is in bucket: 9
Key: KEY_10 is in bucket: 15
Key: KEY_11 is in bucket: 0
Key: KEY_12 is in bucket: 1
Key: KEY_13 is in bucket: 2
Key: KEY_14 is in bucket: 3
Key: KEY_15 is in bucket: 4
Key: KEY_16 is in bucket: 5
Key: KEY_17 is in bucket: 6
Key: KEY_18 is in bucket: 7
Key: KEY_19 is in bucket: 8
Key: KEY_20 is in bucket: 14
Key: KEY_21 is in bucket: 15
Key: KEY_22 is in bucket: 0
Key: KEY_23 is in bucket: 1
Key: KEY_24 is in bucket: 2
Key: KEY_25 is in bucket: 3
Key: KEY_26 is in bucket: 4
Key: KEY_27 is in bucket: 5
Key: KEY_28 is in bucket: 6
Key: KEY_29 is in bucket: 7
Size: 30
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0,071 sec