1

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.

  1. But Hashtables store Key,Value pair. So how it is achieved?
  2. 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)
  3. A bit more practical example for Hash Table than map.put("Rocket", 01111111111).
3
  • 1
    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 Commented May 3, 2018 at 14:01
  • 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!! Commented May 3, 2018 at 15:28
  • 1
    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. Commented May 3, 2018 at 15:37

1 Answer 1

1
  1. 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;

}
  1. 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.

  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...
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks a lot!! Also just noticed your constructor name seems to have typo..but I get the point. so our key is PersonIdentifer, with 2 attributes id and ssn, if we were to extract details out of the map then we will need exact combination of id and ssn..right?? would it not be better to keep only ssn as key, that way we can extract the person details just by knowing the ssn and not worry about the id..please do let me know if I am missing something?? and by the way excellent example to demonstrate a practical use..this is what I was looking for.. Thanks!!
Sorry, typo fixed. Yes, we need the combination of both components, id and field. I designed it like that because you said "A bit more practical example for Hash Table than map.put("Rocket", 01111111111)." so that's one to go for, just an example of how to use a map when there are multiple fields to identify your data. You may simplify this example using Map<String, Person> peopleMap and using the SSN as the only key.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.