Index: uspace/lib/cpp/Makefile
===================================================================
--- uspace/lib/cpp/Makefile	(revision 4727aacd63aa9f0572728927ba262a1d62871c6b)
+++ uspace/lib/cpp/Makefile	(revision f2ba4c79fa9e024ce49cbe808076a054e9cd2dd8)
@@ -64,4 +64,5 @@
 	src/internal/test/test.cpp \
 	src/internal/test/tuple.cpp \
+	src/internal/test/unordered_map.cpp \
 	src/internal/test/vector.cpp
 
Index: uspace/lib/cpp/include/internal/hash_table_iterators.hpp
===================================================================
--- uspace/lib/cpp/include/internal/hash_table_iterators.hpp	(revision 4727aacd63aa9f0572728927ba262a1d62871c6b)
+++ uspace/lib/cpp/include/internal/hash_table_iterators.hpp	(revision f2ba4c79fa9e024ce49cbe808076a054e9cd2dd8)
@@ -142,5 +142,5 @@
         using non_const_iterator_type = hash_table_iterator<
             Value, get_non_const_ref_t<ConstReference>,
-            get_non_const_ptr<ConstPointer>, Size
+            get_non_const_ptr_t<ConstPointer>, Size
         >;
 
Index: uspace/lib/cpp/include/internal/hash_table_policies.hpp
===================================================================
--- uspace/lib/cpp/include/internal/hash_table_policies.hpp	(revision 4727aacd63aa9f0572728927ba262a1d62871c6b)
+++ uspace/lib/cpp/include/internal/hash_table_policies.hpp	(revision f2ba4c79fa9e024ce49cbe808076a054e9cd2dd8)
@@ -60,4 +60,7 @@
             auto current = head;
 
+            if (!current)
+                return 0;
+
             do
             {
@@ -246,5 +249,5 @@
         static typename Table::size_type count(const Table& table, const Key& key)
         {
-            auto head = table.table_[get_bucket_idx_(key)].head;
+            auto head = table.table_[table.get_bucket_idx_(key)].head;
             if (!head)
                 return 0;
@@ -299,28 +302,34 @@
         {
             auto idx = table.get_bucket_idx_(key);
-            auto it = table.begin(it);
+            auto head = table.table_[idx].head;
+            auto current = head;
+            table.table_[idx].head = nullptr;
+
+            if (!current)
+                return 0;
+
+            /**
+             * We traverse the list and delete if the keys
+             * equal, if they don't we append the nodes back
+             * to the bucket.
+             */
             typename Table::size_type res{};
 
-            while (it != table.end(it))
-            {
-                if (table.keys_equal(key, *it))
+            do
+            {
+                auto tmp = current;
+                current = current->next;
+
+                if (!table.keys_equal(key, tmp->value))
+                    table.table_[idx].append(tmp);
+                else
                 {
-                    while (table.keys_equal(key, *it))
-                    {
-                        auto node = it.node();
-                        ++it;
-                        ++res;
-
-                        node.unlink();
-                        delete node;
-                        --table.size_;
-                    }
-
-                    // Elements with equal keys are next to each other.
-                    return res;
+                    ++res;
+                    --table.size_;
+
+                    delete tmp;
                 }
-
-                ++it;
-            }
+            }
+            while (current != head);
 
             return res;
@@ -407,5 +416,5 @@
 
             if (!bucket)
-                return make_pair(table.end(), false);
+                table.end();
 
             if (target && table.keys_equal(key, target->value))
Index: uspace/lib/cpp/include/internal/test/tests.hpp
===================================================================
--- uspace/lib/cpp/include/internal/test/tests.hpp	(revision 4727aacd63aa9f0572728927ba262a1d62871c6b)
+++ uspace/lib/cpp/include/internal/test/tests.hpp	(revision f2ba4c79fa9e024ce49cbe808076a054e9cd2dd8)
@@ -195,4 +195,77 @@
             void test_multi_bounds_and_ranges();
     };
+
+    class unordered_map_test: public test_suite
+    {
+        public:
+            bool run(bool) override;
+            const char* name() override;
+
+        private:
+            void test_constructors_and_assignment();
+            void test_histogram();
+            void test_emplace_insert();
+            void test_multi();
+
+            template<class Iterator, class Container>
+            void test_contains(const char* tname, Iterator first,
+                               Iterator last, const Container& cont)
+            {
+                if (!assert_contains(first, last, cont))
+                {
+                    report(false, tname);
+                    ++failed_;
+                    ok_ = false;
+                }
+                else
+                {
+                    report(true, tname);
+                    ++succeeded_;
+                }
+            }
+
+            template<class Iterator1, class Iterator2, class Container>
+            void test_contains_multi(const char* tname, Iterator1 first1,
+                               Iterator1 last1, Iterator2 first2,
+                               const Container& cont)
+            {
+                if (!assert_contains_multi(first1, last1, first2, cont))
+                {
+                    report(false, tname);
+                    ++failed_;
+                    ok_ = false;
+                }
+                else
+                {
+                    report(true, tname);
+                    ++succeeded_;
+                }
+            }
+
+            template<class Iterator, class Container>
+            bool assert_contains(Iterator first, Iterator last, const Container& cont)
+            {
+                while (first != last)
+                {
+                    if (cont.find(*first++) == cont.end())
+                        return false;
+                }
+
+                return true;
+            }
+
+            template<class Iterator1, class Iterator2, class Container>
+            bool assert_contains_multi(Iterator1 first1, Iterator1 last1,
+                                       Iterator2 first2, const Container& cont)
+            {
+                while (first1 != last1)
+                {
+                    if (cont.count(*first1++) != *first2++)
+                        return false;
+                }
+
+                return true;
+            }
+    };
 }