Java data structure with multiple keys and not allows duplicate keys

Question

I'm wondering if there are any Java data structures or libraries that would allow me to have multiple keys while not having duplicate keys?

In my use case I have two different types of keys: Personal Identification Number and Driver License. I want to use either keys to look up a value (their car in this example). When I try to add a duplicate key (pin-1), there should be an error as pin-1 is already assigned.

structure.add("pin-1", "driverLicense-1", Car.TOYOTA);
structure.add("pin-2", "driverLicense-2", Car.FORD);
structure.add("pin-1", "driverLicense-3", CAR.FORD); // invalid because pin-1 is already assigned

The only library I have encountered that does something like this is Google’s Guava and its HashBasedTable class implementing Table. The issue I have with this library is that it does not prevent duplicate keys.

Table<String, String, Car> table = HashBasedTable.create();
table.put("pin-1", "driverLicense-1", Car.TOYOTA);
table.put("pin-2", "driverLicense-2", Car.FORD);
table.put("pin-1", "driverLicense-3", Car.FORD); // is valid

map within a map? get("pin-1") returns a map. that map.get("driverLicense-3") returns a value? — Khanna111
– Khanna111, Commented Nov 6, 2021 at 0:43
Why do you claim that Guava HashBasedTable does not prevent duplicate keys? The Javadoc says the data is stored in a Map<R, Map<C, V>>. And a Map by definition cannot have duplicate keys. — Basil Bourque
– Basil Bourque, Commented Nov 6, 2021 at 0:56

tgdavies · Accepted Answer · 2021-11-06 01:35:48Z

4

I would use two Maps, wrapped in a class which handles updating them together, e.g.:

    class CarOwnership {
        private final Map<String,Car> byPin = new HashMap<>();
        private final Map<String,Car> byLicense = new HashMap<>();
        
        public void put(String pin, String licence, Car car) {
            if (byPin.containsKey(pin)) {
                throw new RuntimeException("duplicate pin " + pin);
            }
            if (byLicense.containsKey(licence)) {
                throw new RuntimeException("duplicate licence " + license);
            }
            byPin.put(pin, car);
            byLicense.put(licence, car);
        }
        
        public Car findByPin(String pin) {
            return byPin.get(pin);
        }
        ...
    }

The advantage of having a container around the actual data structure you're using is that it allows you to put your error handling in one place, and gives you somewhere to perform validation.

This is distinct from HashBasedTable, which is a Map of Maps, and so needs both components of the key to reach the value.

edited Nov 6, 2021 at 1:35

answered Nov 6, 2021 at 0:55

tgdavies

11.6k4 gold badges41 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Basil Bourque Over a year ago

This is how the mentioned Guava HashBasedTable works, a map of maps: Map<R, Map<C, V>>. So it might make more sense to use Guava rather than write you own.

tgdavies Over a year ago

Doesn't Table require both keys to retrieve a value? My interpretation of the question is that you can retrieve car with either a pin or a licence.

Basil Bourque Over a year ago

Yes, that seems to be the case with a Table & HashBasidTable in Guava, you must specify both keys ("row" & "column") to get a value. Using either key alone returns a Map rather than the desired value. So I stand corrected: You are using a pair of Map kept separate, whereas HashBasedTable is using a nested structure, with a Map leading to another Map. So your Answer does indeed provide a better solution for this Question. You might want to add a note on this distinction, since the Question specifically mentions Guava HashBasedTable.

Sree Kumar · Accepted Answer · 2021-11-06 07:06:50Z

From what I understand, this can be achieved by making an entry in a map for each key passed. So, there is only one map, but each call to put() potentially adds multiple entries (one entry for each key). Not sure if there is a built-in API in Java for this, but here is one simply implementation.

public class MultikeyMap<K, V>{
    /* Holds all the values. */
    private Map<K, V> map = new HashMap<>();
    
    /** Creates one entry in this.map for each key passed here. */
    public void put( V value, K... keys ) {
        if( keys == null || keys.length == 0 ) throw new NullPointerException();
        
        /* For every key, create an entry. */
        for( K key : keys ) map.putIfAbsent( key, value );
    }
    
    public V get( K key ) {
        if( key == null ) throw new NullPointerException();
        return map.get( key );
    }
    
    @Override
    public String toString(){
        return this.map.toString();
    }
    
    public static void main( String[] args ){
        MultikeyMap<String, Car> m = new MultikeyMap<>();
        
        m.put( Car.HONDA, "pin-1", "dl-1" );
        System.out.println( m );
        
        m.put( Car.TATA, "pin-2", "dl-2" );
        System.out.println( m );
        
        m.put( Car.TOYOTA, "pin-1", "dl-3" );
        System.out.println( m );
    }
    
    private static enum Car{
        TOYOTA, HONDA, MARUTI, TATA;
    }
}

Here's the output from running main().

{pin-1=HONDA, dl-1=HONDA}
{pin-2=TATA, pin-1=HONDA, dl-2=TATA, dl-1=HONDA}
{pin-2=TATA, dl-3=TOYOTA, pin-1=HONDA, dl-2=TATA, dl-1=HONDA}

Some points about this design:

When an existing key is encountered, it doesn't throw an exception; only ignores it.
If we need various types in the key, then we may have to use Map<Object, Car>.

Collectives™ on Stack Overflow

Java data structure with multiple keys and not allows duplicate keys

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related