Index: src/ooxml/java/org/apache/poi/xssf/model/StylesTable.java
===================================================================
--- src/ooxml/java/org/apache/poi/xssf/model/StylesTable.java	(revision 1721943)
+++ src/ooxml/java/org/apache/poi/xssf/model/StylesTable.java	(working copy)
@@ -25,6 +25,7 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
+import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
@@ -76,7 +77,14 @@
     private final List<CTXf> xfs = new ArrayList<CTXf>();
 
     private final List<CTDxf> dxfs = new ArrayList<CTDxf>();
-
+    
+    // Use DualBidiMap
+    //http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/bidimap/DualHashBidiMap.html
+    private final Map<XSSFFont, Integer> fontsInverse = new HashMap<XSSFFont, Integer>();
+    private final Map<XSSFCellFill, Integer> fillsInverse = new HashMap<XSSFCellFill, Integer>();
+    private final Map<XSSFCellBorder, Integer> bordersInverse = new HashMap<XSSFCellBorder, Integer>();
+    private final Map<CTXf, Integer> xfsInverse = new HashMap<CTXf, Integer>();
+    
     /**
      * The first style id available for use as a custom style
      */
@@ -174,6 +182,7 @@
                 for (CTFont font : ctfonts.getFontArray()) {
                     // Create the font and save it. Themes Table supplied later
                     XSSFFont f = new XSSFFont(font, idx);
+                    fontsInverse.put(f, fonts.size());
                     fonts.add(f);
                     idx++;
                 }
@@ -181,7 +190,9 @@
             CTFills ctfills = styleSheet.getFills();
             if(ctfills != null){
                 for (CTFill fill : ctfills.getFillArray()) {
-                    fills.add(new XSSFCellFill(fill));
+                    XSSFCellFill xfill = new XSSFCellFill(fill);
+                    fillsInverse.put(xfill, fills.size());
+                    fills.add(xfill);
                 }
             }
 
@@ -188,12 +199,19 @@
             CTBorders ctborders = styleSheet.getBorders();
             if(ctborders != null) {
                 for (CTBorder border : ctborders.getBorderArray()) {
-                    borders.add(new XSSFCellBorder(border));
+                    XSSFCellBorder xborder = new XSSFCellBorder(border);
+                    bordersInverse.put(xborder, borders.size());
+                    borders.add(xborder);
                 }
             }
 
             CTCellXfs cellXfs = styleSheet.getCellXfs();
-            if(cellXfs != null) xfs.addAll(Arrays.asList(cellXfs.getXfArray()));
+            if(cellXfs != null) {
+                for (CTXf ctxf : cellXfs.getXfArray()) {
+                    xfsInverse.put(ctxf, xfs.size());
+                    xfs.add(ctxf);
+                }
+            }
 
             CTCellStyleXfs cellStyleXfs = styleSheet.getCellStyleXfs();
             if(cellStyleXfs != null) styleXfs.addAll(Arrays.asList(cellStyleXfs.getXfArray()));
@@ -272,16 +290,13 @@
      *  {@link XSSFFont#registerTo(StylesTable)}
      */
     public int putFont(XSSFFont font, boolean forceRegistration) {
-        int idx = -1;
-        if(!forceRegistration) {
-            idx = fonts.indexOf(font);
+        if (!forceRegistration) {
+            Integer idx = fontsInverse.get(font);
+            if (idx != null)
+                return idx;
         }
-
-        if (idx != -1) {
-            return idx;
-        }
-
-        idx = fonts.size();
+        int idx = fonts.size();
+        fontsInverse.put(font, idx);
         fonts.add(font);
         return idx;
     }
@@ -300,12 +315,7 @@
         return new XSSFCellStyle(idx, styleXfId, this, theme);
     }
     public int putStyle(XSSFCellStyle style) {
-        CTXf mainXF = style.getCoreXf();
-
-        if(! xfs.contains(mainXF)) {
-            xfs.add(mainXF);
-        }
-        return xfs.indexOf(mainXF);
+        return this.putCellXf(style.getCoreXf());
     }
 
     public XSSFCellBorder getBorderAt(int idx) {
@@ -320,10 +330,11 @@
      * @return the index of the added border
      */
     public int putBorder(XSSFCellBorder border) {
-        int idx = borders.indexOf(border);
-        if (idx != -1) {
+        Integer idx = bordersInverse.get(border);
+        if (idx != null) {
             return idx;
         }
+        bordersInverse.put(border, borders.size());
         borders.add(border);
         border.setThemesTable(theme);
         return borders.size() - 1;
@@ -357,10 +368,11 @@
      * @return the index of the added fill
      */
     public int putFill(XSSFCellFill fill) {
-        int idx = fills.indexOf(fill);
-        if (idx != -1) {
+        Integer idx = fillsInverse.get(fill);
+        if (idx != null) {
             return idx;
         }
+        fillsInverse.put(fill, fills.size());
         fills.add(fill);
         return fills.size() - 1;
     }
@@ -574,19 +586,27 @@
     private void initialize() {
         //CTFont ctFont = createDefaultFont();
         XSSFFont xssfFont = createDefaultFont();
+        fontsInverse.put(xssfFont, fonts.size());
         fonts.add(xssfFont);
 
         CTFill[] ctFill = createDefaultFills();
-        fills.add(new XSSFCellFill(ctFill[0]));
-        fills.add(new XSSFCellFill(ctFill[1]));
+        XSSFCellFill xfill = new XSSFCellFill(ctFill[0]);
+        fillsInverse.put(xfill, fills.size());
+        fills.add(xfill);
+        xfill = new XSSFCellFill(ctFill[1]);
+        fillsInverse.put(xfill, fills.size());
+        fills.add(xfill);
 
         CTBorder ctBorder = createDefaultBorder();
-        borders.add(new XSSFCellBorder(ctBorder));
+        XSSFCellBorder xborder = new XSSFCellBorder(ctBorder);
+        bordersInverse.put(xborder, borders.size());
+        borders.add(xborder);
 
         CTXf styleXf = createDefaultXf();
         styleXfs.add(styleXf);
         CTXf xf = createDefaultXf();
         xf.setXfId(0);
+        xfsInverse.put(xf, xfs.size());
         xfs.add(xf);
     }