HashMap in Java

[BuckGup]

I am trying to make a simple hashmap but am having trouble doing two things. I have a constructor 

  public HashMap(){
        elementData =  new HashEntry[10];
        size = 0;
        REMOVED = new HashEntry(null, null);
        HashMap<K, V> hMap = new HashMap<K, V>();

    }

elementData = new HashEntry[10] says Generic array creation. How do I fix that or properly handle generic arrays. Secondly where I create the HashMap I can't use hMap anywhere else so I don't think I am doing it right.

 

All the code

Spoiler

public class HashMap<K, V> {

    private final double MAX_LOAD_FACTOR = 0.75;
    private HashEntry[] elementData;
    private final HashEntry REMOVED;
    private int size;



    public HashMap(){
        elementData =  new HashEntry[10];
        size = 0;
        REMOVED = new HashEntry(null, null);
        HashMap<K, V> hMap = new HashMap<K, V>();

    }


    public void put(K key, V value){

    }

    public void clear(){

    }

    public boolean containsKey(K key){

    }

    public boolean isEmpty(){

        hMa
    }

    public V remove(Object key){

    }

    public int size(){
        this.size = size;
        return size;

    }

    public String toString(){

    }

    private int hashFunction(Object key){

    }

    private double loadFactor(){

    }

    private void rehash(){

    }



    public class HashEntry{
        private K key;
        private V value;

        public HashEntry(K key, V value){

        }

        public K getKey(){
            this.key = key;
            return key;
        }

        public V getValue(){
            this.value = value;
            return value;
        }
    }

}

 

 

[Bartholomew]

2 minutes ago, BuckGup said:

I am trying to make a simple hashmap but am having trouble doing two things. I have a constructor 

  public HashMap(){
        elementData =  new HashEntry[10];
        size = 0;
        REMOVED = new HashEntry(null, null);
        HashMap<K, V> hMap = new HashMap<K, V>();

    }

elementData = new HashEntry[10] says Generic array creation. How do I fix that or properly handle generic arrays. Secondly where I create the HashMap I can't use hMap anywhere else so I don't think I am doing it right.

 

All the code

  Hide contents

public class HashMap<K, V> {

    private final double MAX_LOAD_FACTOR = 0.75;
    private HashEntry[] elementData;
    private final HashEntry REMOVED;
    private int size;



    public HashMap(){
        elementData =  new HashEntry[10];
        size = 0;
        REMOVED = new HashEntry(null, null);
        HashMap<K, V> hMap = new HashMap<K, V>();

    }


    public void put(K key, V value){

    }

    public void clear(){

    }

    public boolean containsKey(K key){

    }

    public boolean isEmpty(){

        hMa
    }

    public V remove(Object key){

    }

    public int size(){
        this.size = size;
        return size;

    }

    public String toString(){

    }

    private int hashFunction(Object key){

    }

    private double loadFactor(){

    }

    private void rehash(){

    }



    public class HashEntry{
        private K key;
        private V value;

        public HashEntry(K key, V value){

        }

        public K getKey(){
            this.key = key;
            return key;
        }

        public V getValue(){
            this.value = value;
            return value;
        }
    }

}

 

 

HashMap hMap is now a local var in the constructor; not a classmember. Thats why you cant use it anywhere else.

 

Are you trying to "make" (as in, imolement yourself) or "use" (as in use the standard already provideded hashmap implementation)?

 

Reason I ask is that now in constructor you new HashMap() but its the same class name as you are defining...

 

To make a hashmap mapping strings to trucks (trucks being a fictional example) do:

 

Map<String, Truck> trucksMapSampleInstance = new HashMap<>();

 

If implementing one yourself: if for study of programing, good!, if for needing hashmap: bad.., use the standard java classes.

 

Notice 2 thjngs in the sample above:

- Diamond syntax for brevity

- variable is of type Map (the abstracter map interface) intentionally (always use the most abstract interface the use case allows, this allows swapping out the more concrete types later if need be). 

 

[BuckGup]

2 minutes ago, Bartholomew said:

HashMap hMap is now a local var in the constructor; not a classmember. Thats why you cant use it anywhere else.

 

Are you trying to "make" (as in, imolement yourself) or "use" (as in use the standard already provideded hashmap implementation)?

 

Reason I ask is that now in constructor you new HashMap() but its the same class name as you are defining...

 

To make a hashmap mapping strings to trucks (trucks being a fictional example) do:

 

Map<String, Truck> trucksMapSampleInstance = new HashMap<>();

 

If implementing one yourself: if for study of programing, good!, if for needing hashmap: bad.., use the standard java classes.

 

Notice 2 thjngs in the sample above:

- Diamond syntax for brevity

- variable is of type Map (the abstracter map interface) intentionally (always use the most abstract interface the use case allows, this allows swapping out the more concrete types later if need be). 

 

I am trying to make a hashMap myself to learn about it. 

[Bartholomew]

19 minutes ago, BuckGup said:

I am trying to make a hashMap myself to learn about it. 

Kudos! Thats a nice way to learn  

 

On the generic array error, you new hashentry, but it needs two types, so hashentry<keyclass, valueclass>

However since your implementing hashmap which is a generic type (think of it as a compile time template), you can carry over the "unkown" (generic) types like:

 

class HashEntry<k, v> {

 

 

new HashEntry<k, v>[10]; // k and v come in from the outer class

 

Possibly compiler wont like k and v same identifyer for nested class, so might need x and z (or kk and vv) for the nested classes declaration, not sure.

 

To avoid handling the fixed array resize handling can use the standard collection classes like either linkedlist or ArrayList etc. (These are generic classes as well).

 

 

[colonel_mortis]

The problem is that arrays aren't properly type safe,¹ so they can't be used safely with generics. Unfortunately, to solve that, you need to reduce the compiler safety guarantees, and enforce the guarantees manually.

 

If you change your HashEntry class from an inner class to a regular class, you will need to parameterise it by K and V, so you have

    public class HashEntry<K, V> {
        private K key;
        private V value;
        // ...
    }

The inner class that you have in your version is mostly just syntactic sugar for this.

 

When the code is compiled, K and V get erased, which means the code that is produced actually looks like

    public class HashEntry {
        private Object key;
        private Object value;
        // ...
    }

This is a limitation of how generics work in Java. The K and V are just checked at compile time, but not at runtime.

 

When you want to construct an array of HashEntrys, you would normally try to do it like

HashEntry<K, V>[] entries = new HashEntry<K, V>[10];

Because of type erasure though, at runtime this is the same as

HashEntry[] entries = new HashEntry[10];

This means that (by doing stuff that is allowed at compile time due to the limitations in footnote 1), it can become possible to do

entries[3] = new HashEntry<SomethingOtherThanK, SomethingOtherThanV>(...);

which would succeed at runtime (because at runtime it doesn't know about K, V, SomethingOtherThanK or SomethingOtherThanV), violating the guarantees about your data structure. This is very bad, so Java gives you an error when you try to construct an array of things that are generic.
 

You can work around this limitation though, but the onus is on you to verify that your code is correct, because the compiler will no longer be able to check it. If you write

HashEntry<K, V>[] entries = (HashEntry<K, V>[]) new HashEntry[10];

you are telling the compiler to make you an array of HashEntrys that don't have any restrictions on K and V (K and V are considered to be Object, just like the erased version above), then you assert that it is actually an array of HashEntry<K, V>. As long as you only ever put HashEntry<K, V> into the array, and no other type of HashEntry, this is a safe thing to do. However, the compiler will not be able to check for you to make sure that you're not putting anything else in there.

 

When you run this code, you'll find that it produces a warning about an Unchecked Assignment. This is because you're trying to do things that the compiler isn't able to check. You can suppress the warnings by adding

@SuppressWarnings("unchecked")

just before the method where you do the (HashEntry<K, V>[]) cast. This will suppress all "unchecked" warnings in that method. Before you do this, you need to be really sure that your code is correct and safe.

 

---

¹ Arrays are considered to be covariant, so you can pass an Integer[] to a function wanting Object[] and it will work (Object[] <: Integer[]), but fail at runtime when you try to add an Object to the array. For proper type safety they would need to be invariant, so Integer[] </: Object[] and Object[] </: Integer[] (where <: effectively means "assignable to" and </: means "not assignable to").

Edited May 4, 2019 by colonel_mortis
I missed a pair of brackets in the HashEntry<K, V>[] cast

[BuckGup]

1 hour ago, colonel_mortis said:

 

Wow thank you so much. Once again great info