--- a/servo/components/hashglobe/src/fake.rs
+++ b/servo/components/hashglobe/src/fake.rs
@@ -38,34 +38,16 @@ impl<K, V, S> Deref for HashMap<K, V, S>
 }
 
 impl<K, V, S> DerefMut for HashMap<K, V, S> {
     fn deref_mut(&mut self) -> &mut Self::Target {
         &mut self.0
     }
 }
 
-impl<K: Hash + Eq, V> HashMap<K, V, RandomState> {
-    #[inline]
-    pub fn new() -> HashMap<K, V, RandomState> {
-        HashMap(StdMap::new())
-    }
-
-    #[inline]
-    pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
-        HashMap(StdMap::with_capacity(capacity))
-    }
-
-    #[inline]
-    pub fn try_with_capacity(capacity: usize) -> Result<HashMap<K, V, RandomState>, FailedAllocationError> {
-        Ok(HashMap(StdMap::with_capacity(capacity)))
-    }
-}
-
-
 impl<K, V, S> HashMap<K, V, S>
     where K: Eq + Hash,
           S: BuildHasher
 {
     #[inline]
     pub fn try_with_hasher(hash_builder: S) -> Result<HashMap<K, V, S>, FailedAllocationError> {
         Ok(HashMap(StdMap::with_hasher(hash_builder)))
     }

--- a/servo/components/hashglobe/src/hash_map.rs
+++ b/servo/components/hashglobe/src/hash_map.rs
@@ -578,52 +578,16 @@ impl<K, V, S> HashMap<K, V, S>
                 Full(b) => b.into_bucket(),
             };
             buckets.next();
             debug_assert!(buckets.index() != start_index);
         }
     }
 }
 
-impl<K: Hash + Eq, V> HashMap<K, V, RandomState> {
-    /// Creates an empty `HashMap`.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use std::collections::HashMap;
-    /// let mut map: HashMap<&str, isize> = HashMap::new();
-    /// ```
-    #[inline]
-    pub fn new() -> HashMap<K, V, RandomState> {
-        Default::default()
-    }
-
-    /// Creates an empty `HashMap` with the specified capacity.
-    ///
-    /// The hash map will be able to hold at least `capacity` elements without
-    /// reallocating. If `capacity` is 0, the hash map will not allocate.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use std::collections::HashMap;
-    /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
-    /// ```
-    #[inline]
-    pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
-        HashMap::with_capacity_and_hasher(capacity, Default::default())
-    }
-
-    #[inline]
-    pub fn try_with_capacity(capacity: usize) -> Result<HashMap<K, V, RandomState>, FailedAllocationError> {
-        HashMap::try_with_capacity_and_hasher(capacity, Default::default())
-    }
-}
-
 impl<K, V, S> HashMap<K, V, S>
     where K: Eq + Hash,
           S: BuildHasher
 {
     /// Creates an empty `HashMap` which will use the given hash builder to hash
     /// keys.
     ///
     /// The created map has the default initial capacity.

--- a/servo/components/hashglobe/src/hash_set.rs
+++ b/servo/components/hashglobe/src/hash_set.rs
@@ -116,48 +116,16 @@ use super::hash_map::{self, HashMap, Key
 /// [`HashMap`]: struct.HashMap.html
 /// [`PartialEq`]: ../../std/cmp/trait.PartialEq.html
 /// [`RefCell`]: ../../std/cell/struct.RefCell.html
 #[derive(Clone)]
 pub struct HashSet<T, S = RandomState> {
     map: HashMap<T, (), S>,
 }
 
-impl<T: Hash + Eq> HashSet<T, RandomState> {
-    /// Creates an empty `HashSet`.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use std::collections::HashSet;
-    /// let set: HashSet<i32> = HashSet::new();
-    /// ```
-    #[inline]
-    pub fn new() -> HashSet<T, RandomState> {
-        HashSet { map: HashMap::new() }
-    }
-
-    /// Creates an empty `HashSet` with the specified capacity.
-    ///
-    /// The hash set will be able to hold at least `capacity` elements without
-    /// reallocating. If `capacity` is 0, the hash set will not allocate.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use std::collections::HashSet;
-    /// let set: HashSet<i32> = HashSet::with_capacity(10);
-    /// assert!(set.capacity() >= 10);
-    /// ```
-    #[inline]
-    pub fn with_capacity(capacity: usize) -> HashSet<T, RandomState> {
-        HashSet { map: HashMap::with_capacity(capacity) }
-    }
-}
-
 impl<T, S> HashSet<T, S>
     where T: Eq + Hash,
           S: BuildHasher
 {
     /// Creates a new empty hash set which will use the given hasher to hash
     /// keys.
     ///
     /// The hash set is also created with the default initial capacity.

--- a/servo/components/hashglobe/src/protected.rs
+++ b/servo/components/hashglobe/src/protected.rs
@@ -159,35 +159,16 @@ impl<K: Hash + Eq, V, S: BuildHasher> Pr
             return;
         }
         unsafe {
             Gecko_UnprotectBuffer(buff.0 as *mut _, buff.1);
         }
     }
 }
 
-impl<K, V> ProtectedHashMap<K, V, RandomState>
-    where K: Eq + Hash,
-{
-    pub fn new() -> Self {
-        Self {
-            map: HashMap::new(),
-            readonly: true,
-        }
-    }
-
-    pub fn with_capacity(capacity: usize) -> Self {
-        let mut result = Self {
-            map: HashMap::with_capacity(capacity),
-            readonly: true,
-        };
-        result.protect();
-        result
-    }
-}
 
 impl<K, V, S> PartialEq for ProtectedHashMap<K, V, S>
     where K: Eq + Hash,
           V: PartialEq,
           S: BuildHasher
 {
     fn eq(&self, other: &Self) -> bool {
         self.map.eq(&other.map)

--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -23,17 +23,17 @@ use properties::{AnimationRules, Compute
 use rule_tree::CascadeLevel;
 use selector_parser::{AttrValue, ElementExt};
 use selector_parser::{PseudoClassStringArg, PseudoElement};
 use selectors::matching::{ElementSelectorFlags, VisitedHandlingMode};
 use selectors::sink::Push;
 use servo_arc::{Arc, ArcBorrow};
 use shared_lock::Locked;
 use std::fmt;
-#[cfg(feature = "gecko")] use hash::HashMap;
+#[cfg(feature = "gecko")] use hash::FnvHashMap;
 use std::fmt::Debug;
 use std::hash::Hash;
 use std::ops::Deref;
 use stylist::Stylist;
 use traversal_flags::{TraversalFlags, self};
 
 /// An opaque handle to a node, which, unlike UnsafeNode, cannot be transformed
 /// back into a non-opaque representation. The only safe operation that can be
@@ -643,20 +643,20 @@ pub trait TElement : Eq + PartialEq + De
     /// Returns whether to cut off the inheritance.
     fn each_xbl_stylist<F>(&self, _: F) -> bool
     where
         F: FnMut(&Stylist),
     {
         false
     }
 
-    /// Gets the current existing CSS transitions, by |property, end value| pairs in a HashMap.
+    /// Gets the current existing CSS transitions, by |property, end value| pairs in a FnvHashMap.
     #[cfg(feature = "gecko")]
     fn get_css_transitions_info(&self)
-                                -> HashMap<TransitionProperty, Arc<AnimationValue>>;
+                                -> FnvHashMap<TransitionProperty, Arc<AnimationValue>>;
 
     /// Does a rough (and cheap) check for whether or not transitions might need to be updated that
     /// will quickly return false for the common case of no transitions specified or running. If
     /// this returns false, we definitely don't need to update transitions but if it returns true
     /// we can perform the more thoroughgoing check, needs_transitions_update, to further
     /// reduce the possibility of false positives.
     #[cfg(feature = "gecko")]
     fn might_need_transitions_update(
@@ -679,17 +679,17 @@ pub trait TElement : Eq + PartialEq + De
     /// Returns true if we need to update transitions for the specified property on this element.
     #[cfg(feature = "gecko")]
     fn needs_transitions_update_per_property(
         &self,
         property: &LonghandId,
         combined_duration: f32,
         before_change_style: &ComputedValues,
         after_change_style: &ComputedValues,
-        existing_transitions: &HashMap<TransitionProperty, Arc<AnimationValue>>
+        existing_transitions: &FnvHashMap<TransitionProperty, Arc<AnimationValue>>
     ) -> bool;
 
     /// Returns the value of the `xml:lang=""` attribute (or, if appropriate,
     /// the `lang=""` attribute) on this element.
     fn lang_attr(&self) -> Option<AttrValue>;
 
     /// Returns whether this element's language matches the language tag
     /// `value`.  If `override_lang` is not `None`, it specifies the value

--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -61,17 +61,17 @@ use gecko_bindings::structs::ELEMENT_HAS
 use gecko_bindings::structs::ELEMENT_HAS_SNAPSHOT;
 use gecko_bindings::structs::EffectCompositor_CascadeLevel as CascadeLevel;
 use gecko_bindings::structs::NODE_DESCENDANTS_NEED_FRAMES;
 use gecko_bindings::structs::NODE_NEEDS_FRAME;
 use gecko_bindings::structs::nsChangeHint;
 use gecko_bindings::structs::nsIDocument_DocumentTheme as DocumentTheme;
 use gecko_bindings::structs::nsRestyleHint;
 use gecko_bindings::sugar::ownership::{HasArcFFI, HasSimpleFFI};
-use hash::HashMap;
+use hash::FnvHashMap;
 use logical_geometry::WritingMode;
 use media_queries::Device;
 use properties::{ComputedValues, LonghandId, parse_style_attribute};
 use properties::{Importance, PropertyDeclaration, PropertyDeclarationBlock};
 use properties::animated_properties::{AnimationValue, AnimationValueMap};
 use properties::animated_properties::TransitionProperty;
 use properties::style_structs::Font;
 use rule_tree::CascadeLevel as ServoCascadeLevel;
@@ -1298,24 +1298,24 @@ impl<'le> TElement for GeckoElement<'le>
     fn xbl_binding_anonymous_content(&self) -> Option<GeckoNode<'le>> {
         self.get_xbl_binding_with_content()
             .map(|b| unsafe { b.anon_content().as_ref() }.unwrap())
             .map(GeckoNode::from_content)
     }
 
     fn get_css_transitions_info(
         &self,
-    ) -> HashMap<TransitionProperty, Arc<AnimationValue>> {
+    ) -> FnvHashMap<TransitionProperty, Arc<AnimationValue>> {
         use gecko_bindings::bindings::Gecko_ElementTransitions_EndValueAt;
         use gecko_bindings::bindings::Gecko_ElementTransitions_Length;
         use gecko_bindings::bindings::Gecko_ElementTransitions_PropertyAt;
 
         let collection_length =
             unsafe { Gecko_ElementTransitions_Length(self.0) };
-        let mut map = HashMap::with_capacity(collection_length);
+        let mut map = FnvHashMap::with_capacity_and_hasher(collection_length, Default::default());
         for i in 0..collection_length {
             let (property, raw_end_value) = unsafe {
                 (Gecko_ElementTransitions_PropertyAt(self.0, i as usize).into(),
                  Gecko_ElementTransitions_EndValueAt(self.0, i as usize))
             };
             let end_value = AnimationValue::arc_from_borrowed(&raw_end_value);
             debug_assert!(end_value.is_some());
             map.insert(property, end_value.unwrap().clone_arc());
@@ -1442,17 +1442,17 @@ impl<'le> TElement for GeckoElement<'le>
     }
 
     fn needs_transitions_update_per_property(
         &self,
         longhand_id: &LonghandId,
         combined_duration: f32,
         before_change_style: &ComputedValues,
         after_change_style: &ComputedValues,
-        existing_transitions: &HashMap<TransitionProperty, Arc<AnimationValue>>,
+        existing_transitions: &FnvHashMap<TransitionProperty, Arc<AnimationValue>>,
     ) -> bool {
         use values::animated::{Animate, Procedure};
 
         // If there is an existing transition, update only if the end value
         // differs.
         //
         // If the end value has not changed, we should leave the currently
         // running transition as-is since we don't want to interrupt its timing

--- a/servo/components/style/properties/longhand/position.mako.rs
+++ b/servo/components/style/properties/longhand/position.mako.rs
@@ -409,17 +409,17 @@ macro_rules! impl_align_conversions {
     }
 </%helpers:longhand>
 
 <%helpers:longhand name="grid-template-areas"
         spec="https://drafts.csswg.org/css-grid/#propdef-grid-template-areas"
         products="gecko"
         animation_value_type="discrete"
         boxed="True">
-    use hash::HashMap;
+    use hash::FnvHashMap;
     use std::fmt;
     use std::ops::Range;
     use str::HTML_SPACE_CHARACTERS;
     use style_traits::ToCss;
 
     pub mod computed_value {
         pub use super::SpecifiedValue as T;
     }
@@ -473,17 +473,17 @@ macro_rules! impl_align_conversions {
         pub fn from_vec(strings: Vec<Box<str>>) -> Result<TemplateAreas, ()> {
             if strings.is_empty() {
                 return Err(());
             }
             let mut areas: Vec<NamedArea> = vec![];
             let mut width = 0;
             {
                 let mut row = 0u32;
-                let mut area_indices = HashMap::<(&str), usize>::new();
+                let mut area_indices = FnvHashMap::<(&str), usize>::default();
                 for string in &strings {
                     let mut current_area_index: Option<usize> = None;
                     row += 1;
                     let mut column = 0u32;
                     for token in Tokenizer(string) {
                         column += 1;
                         let token = if let Some(token) = token? {
                             token

--- a/servo/components/style/rule_tree/mod.rs
+++ b/servo/components/style/rule_tree/mod.rs
@@ -1011,23 +1011,23 @@ impl StrongRuleNode {
 
         debug!("Popping from free list: cur: {:?}, next: {:?}", current, next);
 
         Some(WeakRuleNode::from_ptr(current))
     }
 
     unsafe fn assert_free_list_has_no_duplicates_or_null(&self) {
         assert!(cfg!(debug_assertions), "This is an expensive check!");
-        use hash::HashSet;
+        use hash::FnvHashSet;
 
         let me = &*self.ptr();
         assert!(me.is_root());
 
         let mut current = self.ptr();
-        let mut seen = HashSet::new();
+        let mut seen = FnvHashSet::default();
         while current != FREE_LIST_SENTINEL {
             let next = (*current).next_free.load(Ordering::Relaxed);
             assert!(!next.is_null());
             assert!(!seen.contains(&next));
             seen.insert(next);
 
             current = next;
         }