Java Hash Tables and Hash Maps

Question

Have been going through the Java for sometime now and got stuck at yet another question. HashMaps or HashTables.

have gone through the basics..how a hash table is implemented..like calculating a hash value..storing data at the hash value(or probably hashvalue % maxArray) index..linear probing and chaining for collisions. Now to further, if somebody could please help with below:

Basic examples show storing Strings like "Jhon", "Lisa" , "Sam" etc in an array then going through collisions and converting the array to Linked list to store the names which is all good to understand and super fine.

But Hashtables store Key,Value pair. So how it is achieved?
The key,value pair examples show "Telephone Directory" example, but they do not show how they are stored in Arrays or linked list. It is just Map.put(k,v) and Map.get(k). Linked list store "One Data" and "Pointer".. so how can we store both Keys and Values in Linked list( A picture might help in understanding)
A bit more practical example for Hash Table than map.put("Rocket", 01111111111).

Just check source code for HashMap or check these links: coding-geek.com/how-does-a-hashmap-work-in-java, howtodoinjava.com/core-java/collections/…, geeksforgeeks.org/internal-working-of-hashmap-java — Ivan
Thanks for the links!! So if I understand correctly..all the Key, Value objects we pass are passed down to Entry/Node class object which is stored as single element in the linked list. Attributes of this object are our Key,Value and all further operations are performed on these attributes. Also, if we implement hashmaps, then is it compulsory to override obj.equals() functions, since it is developer who decide how 2 objects are equal? or java by default checks for each attribute of object for equality? Thanks!! — user1675564
Yes, in java HashMap operates with Entry objects which store key and value. It is developer who must override hashCode() and equals() to be able to use objects of his custom class as keys in HashMap. — Ivan

Luiggi Mendoza Luiggi Mendoza · Accepted Answer · 2018-05-03T14:03:48

But Hashtables store Key,Value pair. So how it is achieved?

Imagine a data structure like this:

Node<K, V>[] table;

public static class Node<K, V> {
    //voila! Key and Value stored here
    private K key;
    private V value;
    //make it a linked list
    private Node<K, V> next;

}

The key,value pair examples show "Telephone Directory" example, but they do not show how they are stored in Arrays or linked list. It is just Map.put(k,v) and Map.get(k). Linked list store "One Data" and "Pointer".. so how can we store both Keys and Values in Linked list( A picture might help in understanding)

Check point 1.

A bit more practical example for Hash Table than map.put("Rocket", 01111111111).

Here you go:

public class PersonIdentifier {
    private final int id;
    private final String ssn;

    public PersonIdentifier(int id, String ssn) {
        this.id = id;
        this.ssn = ssn;
    }
    //getters, NO setters since fields are final...

    //now the relevant methods!
    @Override
    public int hashCode() {
        //available since Java 7...
        return Objects.hash(id, ssn);
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) return null;
        if (this == o) return true;
        if (!o.getClass().equals(this.getClass())) return false;
        Person another = (Person)o;
        return another.id == this.id && another.ssn.equals(this.ssn);
    }
}

//...

Map<PersonIdentifier, Person> peopleMap = new HashMap<>();
peopleMap.put(new PersonIdentifier(1, "123456789"), new Person(/* fill with values like firstName, lastName, etc... */));
peopleMap.put(new PersonIdentifier(2, "987654321"), new Person(/* fill with values like firstName, lastName, etc... */));
//and on...

Java Hash Tables and Hash Maps

1 Answers