Home > OS >  Java data structure with multiple keys and not allows duplicate keys
Java data structure with multiple keys and not allows duplicate keys

Time:11-06

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

CodePudding user response:

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.

CodePudding user response:

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>.
  •  Tags:  
  • java
  • Related