--- a/dom/animation/AnimValuesStyleRule.cpp
+++ b/dom/animation/AnimValuesStyleRule.cpp
@@ -27,25 +27,24 @@ AnimValuesStyleRule::MapRuleInfoInto(nsR
     // a pseudo-element.  Note that nsRuleNode::GetStyle##name_ and GetStyleData
     // will never look at cached structs when we're animating things inside
     // a pseduo-element, so that we don't incorrectly return a struct that
     // is only appropriate for non-pseudo-elements.
     aRuleData->mConditions.SetUncacheable();
     return;
   }
 
-  for (uint32_t i = 0, i_end = mPropertyValuePairs.Length(); i < i_end; ++i) {
-    PropertyStyleAnimationValuePair& pair = mPropertyValuePairs[i];
-    if (aRuleData->mSIDs & nsCachedStyleData::GetBitForSID(
-                             nsCSSProps::kSIDTable[pair.mProperty]))
-    {
-      nsCSSValue *prop = aRuleData->ValueFor(pair.mProperty);
+  for (auto iter = mAnimationValues.ConstIter(); !iter.Done(); iter.Next()) {
+    nsCSSPropertyID property = static_cast<nsCSSPropertyID>(iter.Key());
+    if (aRuleData->mSIDs &
+        nsCachedStyleData::GetBitForSID(nsCSSProps::kSIDTable[property])) {
+      nsCSSValue *prop = aRuleData->ValueFor(property);
       if (prop->GetUnit() == eCSSUnit_Null) {
         DebugOnly<bool> ok =
-          StyleAnimationValue::UncomputeValue(pair.mProperty, pair.mValue,
+          StyleAnimationValue::UncomputeValue(property, iter.Data(),
                                               *prop);
         MOZ_ASSERT(ok, "could not store computed value");
       }
     }
   }
 }
 
 bool
@@ -57,32 +56,50 @@ AnimValuesStyleRule::MightMapInheritedSt
 bool
 AnimValuesStyleRule::GetDiscretelyAnimatedCSSValue(nsCSSPropertyID aProperty,
                                                    nsCSSValue* aValue)
 {
   MOZ_ASSERT(false, "GetDiscretelyAnimatedCSSValue is not implemented yet");
   return false;
 }
 
+void
+AnimValuesStyleRule::AddValue(nsCSSPropertyID aProperty,
+                              const StyleAnimationValue &aValue)
+{
+  mAnimationValues.Put(aProperty, aValue);
+  mStyleBits |=
+    nsCachedStyleData::GetBitForSID(nsCSSProps::kSIDTable[aProperty]);
+}
+
+void
+AnimValuesStyleRule::AddValue(nsCSSPropertyID aProperty,
+                              StyleAnimationValue&& aValue)
+{
+  mAnimationValues.Put(aProperty, Move(aValue));
+  mStyleBits |=
+    nsCachedStyleData::GetBitForSID(nsCSSProps::kSIDTable[aProperty]);
+}
+
 #ifdef DEBUG
 void
 AnimValuesStyleRule::List(FILE* out, int32_t aIndent) const
 {
   nsAutoCString str;
   for (int32_t index = aIndent; --index >= 0; ) {
     str.AppendLiteral("  ");
   }
   str.AppendLiteral("[anim values] { ");
-  for (uint32_t i = 0, i_end = mPropertyValuePairs.Length(); i < i_end; ++i) {
-    const PropertyStyleAnimationValuePair& pair = mPropertyValuePairs[i];
-    str.Append(nsCSSProps::GetStringValue(pair.mProperty));
+  for (auto iter = mAnimationValues.ConstIter(); !iter.Done(); iter.Next()) {
+    nsCSSPropertyID property = static_cast<nsCSSPropertyID>(iter.Key());
+    str.Append(nsCSSProps::GetStringValue(property));
     str.AppendLiteral(": ");
     nsAutoString value;
     Unused <<
-      StyleAnimationValue::UncomputeValue(pair.mProperty, pair.mValue, value);
+      StyleAnimationValue::UncomputeValue(property, iter.Data(), value);
     AppendUTF16toUTF8(value, str);
     str.AppendLiteral("; ");
   }
   str.AppendLiteral("}\n");
   fprintf_stderr(out, "%s", str.get());
 }
 #endif
 

--- a/dom/animation/AnimValuesStyleRule.h
+++ b/dom/animation/AnimValuesStyleRule.h
@@ -5,16 +5,18 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef mozilla_AnimValuesStyleRule_h
 #define mozilla_AnimValuesStyleRule_h
 
 #include "mozilla/StyleAnimationValue.h"
 #include "nsCSSPropertyID.h"
 #include "nsCSSPropertyIDSet.h"
+#include "nsDataHashtable.h"
+#include "nsHashKeys.h" // For nsUint32HashKey
 #include "nsIStyleRule.h"
 #include "nsISupportsImpl.h" // For NS_DECL_ISUPPORTS
 #include "nsRuleNode.h" // For nsCachedStyleData
 #include "nsTArray.h" // For nsTArray
 
 namespace mozilla {
 
 /**
@@ -33,35 +35,24 @@ public:
   void MapRuleInfoInto(nsRuleData* aRuleData) override;
   bool MightMapInheritedStyleData() override;
   bool GetDiscretelyAnimatedCSSValue(nsCSSPropertyID aProperty,
                                      nsCSSValue* aValue) override;
 #ifdef DEBUG
   void List(FILE* out = stdout, int32_t aIndent = 0) const override;
 #endif
 
-  void AddValue(nsCSSPropertyID aProperty, const StyleAnimationValue &aStartValue)
-  {
-    PropertyStyleAnimationValuePair pair = { aProperty, aStartValue };
-    mPropertyValuePairs.AppendElement(pair);
-    mStyleBits |=
-      nsCachedStyleData::GetBitForSID(nsCSSProps::kSIDTable[aProperty]);
-  }
-
-  void AddValue(nsCSSPropertyID aProperty, StyleAnimationValue&& aStartValue)
-  {
-    PropertyStyleAnimationValuePair* pair = mPropertyValuePairs.AppendElement();
-    pair->mProperty = aProperty;
-    pair->mValue = Move(aStartValue);
-    mStyleBits |=
-      nsCachedStyleData::GetBitForSID(nsCSSProps::kSIDTable[aProperty]);
-  }
+  // NOTE: Both of below functions replace the existence entry's mValue
+  // if there is already an entry for |aProperty|.
+  void AddValue(nsCSSPropertyID aProperty, const StyleAnimationValue &aValue);
+  void AddValue(nsCSSPropertyID aProperty, StyleAnimationValue&& aValue);
 
 private:
   ~AnimValuesStyleRule() {}
 
-  InfallibleTArray<PropertyStyleAnimationValuePair> mPropertyValuePairs;
+  nsDataHashtable<nsUint32HashKey, StyleAnimationValue> mAnimationValues;
+
   uint32_t mStyleBits;
 };
 
 } // namespace mozilla
 
 #endif // mozilla_AnimValuesStyleRule_h