CODEWITHSUNDEEP
java
providence
providence

Reputation: 29463

Fastest way to restructure a HashMap

I have a HashMap that maps companies to an ArrayList of the products they sell, like so:

thiscompany --> [productA, productB...]
thatcompany --> [productC, productA...]

Hence it is very easy to generate a list of products given a specific company. Note that multiple companies may sell the same product. The issue is that I also need to, given a specific product, find all the companies that sell it. And quickly. This sort of lookup may happen once, or multiple times. I am wondering the most efficient way to provide this functionality.

Currently I am generating a new data structure by iterating through each ArrayList and mapping each product to its vendor. This is expensive though, because I have to check to see whether the HashMap I am creating contains that product as a key each time before adding, plus it requires me to get the each ArrayList, add the new vendor, delete the old ArrayList then map the new one for each entry. I simply cannot see a faster way of doing this though, perhaps someone can provide me with some insight?

Upvotes: 3

Views: 657

Answers (4)

Emil
Emil

Reputation: 13789

Try MultiMaps.invertFrom,

Example:

    Multimap<String, Integer> map = HashMultimap.create();
    map.put("a", 3);
    map.put("a", 4);
    map.put("a", 5);
    map.put("b", 5);
    map.put("b", 3);
    map.put("b", 6);
    Multimap<Integer,String> mapInverse=HashMultimap.create();
    Multimaps.invertFrom(map, mapInverse);
    System.out.println(mapInverse);

Output:

{3=[b, a], 4=[a], 5=[b, a], 6=[b]}

Alternative Solution:

Here I'm creating a 2D boolean array representing the company and their products for easy lookup.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.google.common.collect.Multimap;
import com.google.common.collect.Sets;
import com.google.common.collect.TreeMultimap;

public class ProductCompanyMap {
    private Multimap<String, String> companyProducts = TreeMultimap.create();
    private boolean[][] ProductCompanyTable;
    private Map<String,Integer> productIndexMap = new HashMap<String, Integer>();;
    private Map<String,Integer> companyIndexMap = new HashMap<String, Integer>();
    private String[] productArray;
    private String[] companyArray;;


    {
        companyProducts.put("Britania","Biscuts");
        companyProducts.put("Britania","Soap");
        companyProducts.put("Britania","Cloths");
        companyProducts.put("MicroSoft","Software");
        companyProducts.put("Birla","Cloths");
        companyProducts.put("Birla","Software");
    }
    public ProductCompanyMap(){

        Set<String> companyNames=companyProducts.keySet();
        Set<String> productNames= Sets.newTreeSet(companyProducts.values());
        companyArray = companyNames.toArray(new String[companyNames.size()]);
        createIndexMap(companyIndexMap, companyArray);
        productArray = productNames.toArray(new String[productNames.size()]);
        createIndexMap(productIndexMap,productArray);

        ProductCompanyTable = new boolean[companyArray.length][productArray.length];
        for(int i=0;i<companyArray.length;i++)
            for(int j=0;j<productArray.length;j++){
                if(companyProducts.containsEntry(companyArray[i],productArray[j]))
                    ProductCompanyTable[i][j] = true;
            }

    }

    private void createIndexMap(Map<String,Integer> map,String[] arr){
        for(int i=0;i<arr.length;i++)
            map.put(arr[i], i);
    }

    public List<String> getProductsOfCompany(String companyName){
        List<String> productsOfCompany = new ArrayList<String>();
        Integer companyIndex = null;
        if((companyIndex=companyIndexMap.get(companyName))!=null)
        {
            for(int i=0;i<ProductCompanyTable[companyIndex].length;i++)
                if(ProductCompanyTable[companyIndex][i])
                    productsOfCompany.add(productArray[i]);
        }
        return productsOfCompany;
    }
    public List<String> getCompanysWithProduct(String productName){
        List<String> companysWithProduct = new ArrayList<String>();
        Integer productIndex = null;
        if((productIndex=productIndexMap.get(productName))!=null)
        {
            for(int i=0;i<ProductCompanyTable.length;i++)
                if(ProductCompanyTable[i][productIndex])
                    companysWithProduct.add(companyArray[i]);
        }
        return companysWithProduct;
    }
    public static void main(String[] args) {
        ProductCompanyMap mm=new ProductCompanyMap();
        System.out.println("Products of Birla : " +mm.getProductsOfCompany("Birla"));
        System.out.println("Company's producing cloths : "+mm.getCompanysWithProduct("Cloths"));
    }
}

Upvotes: 1

objects
objects

Reputation: 8677

Why don't you create the map of companies that sell a products at the same time you build the map of products for company

Map<Product, Set<Company>> companiesByProduct
Map<Company, Set<Product>> productsByCompany

public void add(Company company, Product product) {
    Set<Company> companies = companiesByProduct.get(product);
    if (companies==null) {
        companies = new HashSet<Company>();
        companiesByProduct.put(product, companies);
    }
    companies.add(company);

    // do the same for 
    Set<Product> products = productsByCompany.get(product);
    ....

Or to create new companiesByProduct Map from the map received by the server you could use (you may need to adjust depending on the exactly type of your original map):

for (Company company : originalMap.keySet()) {
  for (Product product : originalMap.get(company)) {
    Set<Company> companies = companiesByProduct.get(product);
    if (companies==null) {
        companies = new HashSet<Company>();
        companiesByProduct.put(product, companies);
    }
    companies.add(company);
   }
}

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234795

Maintain two data structures—the HashMap you maintain now and another one that maps products to companies:

productA --> [thiscompany, thatcompany...]
productC --> [thatcompany, othercompany...]

Upvotes: 0

Tom
Tom

Reputation: 44821

How about changing the ArrayList to a HashSet.

List<String> findCompanies(Map<String,Set<String>> companyToProducts, String product) {
    List<String> companies = new ArrayList<String>();
    for (Map.Entry<String,Set<String>> entry : companyToProducts) {
        Set<String> products = entry.getValue();
        if (products.contains(product)) {
            companies.add(entry.getKey());
        }
    }
    return companies;
}

Another common approach would be to use a table in a database with a column for product and a column for company and then do a:

select distinct company from companyToProduct where product = 'cheese';

Upvotes: 2

Related Questions