Index: uspace/lib/cpp/include/internal/hash_table.hpp
===================================================================
--- uspace/lib/cpp/include/internal/hash_table.hpp	(revision 871cfe0c7e94a7815c417644fe624acdcaa7f418)
+++ uspace/lib/cpp/include/internal/hash_table.hpp	(revision e9027b52de96107ea3a3d00ebc72c00b44124ad9)
@@ -121,4 +121,38 @@
             );
         }
+
+        template<class Table, class Key>
+        static typename Table::size_type erase(Table& table, const Key& key)
+        {
+            auto idx = table.get_bucket_idx_(key);
+            auto head = table.table_[idx].head;
+            auto current = head;
+
+            do
+            {
+                if (table.key_eq_(key, table.key_extractor_(current->value)))
+                {
+                    --table.size_;
+
+                    if (current == head)
+                    {
+                        if (current->next != head)
+                            table.table_[idx].head = current->next;
+                        else
+                            table.table_[idx].head = nullptr;
+                    }
+
+                    current->unlink();
+                    delete current;
+
+                    return 1;
+                }
+                else
+                    current = current->next;
+            }
+            while (current != head);
+
+            return 0;
+        }
     };
 
@@ -154,4 +188,10 @@
             //       link (if key is already in it, place the new copy
             //       next to it, otherwise just return head)
+        }
+
+        template<class Table, class Key>
+        static typename Table::size_type erase(Table& table, const Key& key)
+        {
+            // TODO: erase all items with given key
         }
     };
@@ -169,7 +209,7 @@
             using iterator_category = forward_iterator_tag;
 
-            hash_table_const_iterator(hash_table_bucket<value_type, size_type>* table = nullptr,
+            hash_table_const_iterator(const hash_table_bucket<value_type, size_type>* table = nullptr,
                                       size_type idx = size_type{}, size_type max_idx = size_type{},
-                                      list_node<value_type>* current = nullptr)
+                                      const list_node<value_type>* current = nullptr)
                 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}
             { /* DUMMY BODY */ }
@@ -239,17 +279,22 @@
             list_node<value_type>* node()
             {
+                return const_cast<list_node<value_type>*>(current_);
+            }
+
+            const list_node<value_type>* node() const
+            {
                 return current_;
             }
 
-            const list_node<value_type>* node() const
-            {
-                return current_;
+            size_type idx() const
+            {
+                return idx_;
             }
 
         private:
-            hash_table_bucket<value_type, size_type>* table_;
+            const hash_table_bucket<value_type, size_type>* table_;
             size_type idx_;
             size_type max_idx_;
-            list_node<value_type>* current_;
+            const list_node<value_type>* current_;
     };
 
@@ -358,4 +403,9 @@
             }
 
+            size_type idx() const
+            {
+                return idx_;
+            }
+
             template<class ConstRef, class ConstPtr>
             operator hash_table_const_iterator<
@@ -363,5 +413,5 @@
             >() const
             {
-                return hash_table_const_iterator{
+                return hash_table_const_iterator<value_type, ConstRef, ConstPtr, size_type>{
                     table_, idx_, max_idx_, current_
                 };
@@ -401,6 +451,6 @@
 
             // TODO: requirement for forward iterator is default constructibility, fix others!
-            hash_table_const_local_iterator(list_node<value_type>* head = nullptr,
-                                            list_node<value_type>* current = nullptr)
+            hash_table_const_local_iterator(const list_node<value_type>* head = nullptr,
+                                            const list_node<value_type>* current = nullptr)
                 : head_{head}, current_{current}
             { /* DUMMY BODY */ }
@@ -438,17 +488,18 @@
             }
 
+
             list_node<value_type>* node()
             {
+                return const_cast<list_node<value_type>*>(current_);
+            }
+
+            const list_node<value_type>* node() const
+            {
                 return current_;
             }
 
-            const list_node<value_type>* node() const
-            {
-                return current_;
-            }
-
         private:
-            list_node<value_type>* head_;
-            list_node<value_type>* current_;
+            const list_node<value_type>* head_;
+            const list_node<value_type>* current_;
     };
 
@@ -530,5 +581,7 @@
             >() const
             {
-                return hash_table_const_local_iterator{head_, current_};
+                return hash_table_const_local_iterator<
+                    value_type, ConstRef, ConstPtr
+                >{head_, current_};
             }
 
@@ -659,4 +712,5 @@
 
                 ++size_;
+                // TODO: if we go over max load factor, rehash
             }
 
@@ -673,14 +727,36 @@
 
                 ++size_;
+                // TODO: if we go over max load factor, rehash
             }
 
             size_type erase(const key_type& key)
             {
-                // TODO: implement
+                return Policy::erase(*this, key);
             }
 
             iterator erase(const_iterator it)
             {
-                // TODO: implement
+                auto node = it.node();
+                auto idx = it.idx();
+
+                /**
+                 * Note: This way we will continue on the next bucket
+                 *       if this is the last element in its bucket.
+                 */
+                iterator res{table_, idx, size_, node};
+                ++res;
+
+                if (table_[idx].head == node)
+                {
+                    if (node->next != node)
+                        table_[idx].head = node->next;
+                    else
+                        table_[idx].head = nullptr;
+                }
+
+                node->unlink();
+                delete node;
+
+                return res;
             }