Fastest way to restructure a HashMap
<p>I have a HashMap that maps companies to an ArrayList of the products they sell, like so:</p>

<pre><code>thiscompany --&gt; [productA, productB...]
thatcompany --&gt; [productC, productA...]
</code></pre>

<p>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. </p>

<p>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? </p>
