The fastest way to restructure HashMap

Question

I have a HashMap that maps companies to ArrayList products that they sell, for example:

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

Therefore, it is very easy to create a list of products provided by a particular company. Please note that several companies may sell the same product. The problem is that I also need, given a specific product, to find all the companies that sell it. And fast. Such a search may occur once or several times. I am wondering how the most efficient way to provide this functionality.

I am currently creating a new data structure, iterating through each ArrayList and mapping each product to its provider. It's expensive, though, because I have to check if the HashMap that I create should include this product as a key every time before adding, plus it requires me to get every ArrayList, add a new provider, delete the old ArrayList, and then The card is new for each entry. I just don’t see a faster way to do this, although maybe someone can give me some idea?

Answer 1

How to change ArrayList to 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 the product and a column for the company, and then do:

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

Answer 2

Why don't you create a map of companies that sell products, at the same time you are building a map of products for the 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 create new ByProduct Map companies from the map received by the server that you could use (you may need to configure it depending on the 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); } } 

Answer 3

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 create a 2D Boolean array representing the company and their products for easy searching.

 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 producing cloths : "+mm.getCompanysWithProduct("Cloths")); } } 

Answer 4

Support two data structures: the HashMap that you support now, and the other that displays products for companies:

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