diff --git a/daemon/table/measurements.cpp b/daemon/table/measurements.cpp
index 60e4f8d..c939b72 100644
--- a/daemon/table/measurements.cpp
+++ b/daemon/table/measurements.cpp
@@ -94,7 +94,7 @@
   }
 
   shared_ptr<name_tree::Entry> nteChild = m_nameTree.lookup(child);
-  shared_ptr<name_tree::Entry> nte = nteChild->getParent();
+  name_tree::Entry* nte = nteChild->getParent();
   BOOST_ASSERT(nte != nullptr);
   return &this->get(*nte);
 }
diff --git a/daemon/table/name-tree-entry.cpp b/daemon/table/name-tree-entry.cpp
index c0bc932..77b66ef 100644
--- a/daemon/table/name-tree-entry.cpp
+++ b/daemon/table/name-tree-entry.cpp
@@ -28,36 +28,45 @@
 namespace nfd {
 namespace name_tree {
 
-Node::Node()
-  : m_prev(nullptr)
-  , m_next(nullptr)
+Entry::Entry(const Name& name, Node* node)
+  : m_name(name)
+  , m_node(node)
+  , m_parent(nullptr)
 {
+  BOOST_ASSERT(node != nullptr);
 }
 
-Node::~Node()
+void
+Entry::setParent(Entry& entry)
 {
-  // erase the Name Tree Nodes that were created to
-  // resolve hash collisions
-  // So before erasing a single node, make sure its m_next == nullptr
-  // See eraseEntryIfEmpty in name-tree.cpp
-  if (m_next != nullptr)
-    delete m_next;
+  BOOST_ASSERT(this->getParent() == nullptr);
+  BOOST_ASSERT(!this->getName().empty());
+  BOOST_ASSERT(entry.getName() == this->getName().getPrefix(-1));
+
+  m_parent = &entry;
+
+  m_parent->m_children.push_back(this);
 }
 
-Entry::Entry(const Name& name)
-  : m_hash(0)
-  , m_prefix(name)
+void
+Entry::unsetParent()
 {
+  BOOST_ASSERT(this->getParent() != nullptr);
+
+  auto i = std::find(m_parent->m_children.begin(), m_parent->m_children.end(), this);
+  BOOST_ASSERT(i != m_parent->m_children.end());
+  m_parent->m_children.erase(i);
+
+  m_parent = nullptr;
 }
 
 bool
-Entry::isEmpty() const
+Entry::hasTableEntries() const
 {
-  return m_children.empty() &&
-         m_fibEntry == nullptr &&
-         m_pitEntries.empty() &&
-         m_measurementsEntry == nullptr &&
-         m_strategyChoiceEntry == nullptr;
+  return m_fibEntry != nullptr ||
+         !m_pitEntries.empty() ||
+         m_measurementsEntry != nullptr ||
+         m_strategyChoiceEntry != nullptr;
 }
 
 void
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index b0641d0..9875891 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -26,7 +26,7 @@
 #ifndef NFD_DAEMON_TABLE_NAME_TREE_ENTRY_HPP
 #define NFD_DAEMON_TABLE_NAME_TREE_ENTRY_HPP
 
-#include "core/common.hpp"
+#include "name-tree-hashtable.hpp"
 #include "table/fib-entry.hpp"
 #include "table/pit-entry.hpp"
 #include "table/measurements-entry.hpp"
@@ -35,66 +35,104 @@
 namespace nfd {
 namespace name_tree {
 
-class Node;
-class Entry;
-class NameTree;
-
-/**
- * \brief Name Tree Node Class
- */
-class Node
-{
-public:
-  Node();
-
-  ~Node();
-
-public:
-  // variables are in public as this is just a data structure
-  shared_ptr<Entry> m_entry; // Name Tree Entry (i.e., Name Prefix Entry)
-  Node* m_prev; // Previous Name Tree Node (to resolve hash collision)
-  Node* m_next; // Next Name Tree Node (to resolve hash collision)
-};
-
-/**
- * \brief Name Tree Entry Class
+/** \brief an entry in the name tree
  */
 class Entry : public enable_shared_from_this<Entry>, noncopyable
 {
 public:
-  explicit
-  Entry(const Name& prefix);
+  Entry(const Name& prefix, Node* node);
 
   const Name&
-  getPrefix() const;
+  getName() const
+  {
+    return m_name;
+  }
 
+  /// \deprecated
+  const Name&
+  getPrefix() const
+  {
+    return this->getName();
+  }
+
+  /** \return entry of getName().getPrefix(-1)
+   *  \retval nullptr this entry is the root entry, i.e. getName() == Name()
+   */
+  Entry*
+  getParent() const
+  {
+    return m_parent;
+  }
+
+  /** \brief set parent of this entry
+   *  \param entry entry of getName().getPrefix(-1)
+   *  \pre getParent() == nullptr
+   *  \post getParent() == &entry
+   *  \post entry.getChildren() contains this
+   */
   void
-  setHash(size_t hash);
+  setParent(Entry& entry);
 
-  size_t
-  getHash() const;
-
+  /** \brief unset parent of this entry
+   *  \post getParent() == nullptr
+   *  \post parent.getChildren() does not contain this
+   */
   void
-  setParent(shared_ptr<Entry> parent);
+  unsetParent();
 
-  shared_ptr<Entry>
-  getParent() const;
-
-  std::vector<shared_ptr<Entry>>&
-  getChildren();
-
+  /** \retval true this entry has at least one child
+   *  \retval false this entry has no children
+   */
   bool
-  hasChildren() const;
+  hasChildren() const
+  {
+    return !this->getChildren().empty();
+  }
 
+  /** \return children of this entry
+   */
+  const std::vector<Entry*>&
+  getChildren() const
+  {
+    return m_children;
+  }
+
+  /** \retval true this entry has no children and no table entries
+   *  \retval false this entry has child or attached table entry
+   */
   bool
-  isEmpty() const;
+  isEmpty() const
+  {
+    return !this->hasChildren() && !this->hasTableEntries();
+  }
 
 public: // attached table entries
+  /** \retval true at least one table entries is attached
+   *  \retval false no table entry is attached
+   */
+  bool
+  hasTableEntries() const;
+
+  fib::Entry*
+  getFibEntry() const
+  {
+    return m_fibEntry.get();
+  }
+
   void
   setFibEntry(unique_ptr<fib::Entry> fibEntry);
 
-  fib::Entry*
-  getFibEntry() const;
+  bool
+  hasPitEntries() const
+  {
+    return !this->getPitEntries().empty();
+  }
+
+  const std::vector<shared_ptr<pit::Entry>>&
+  getPitEntries() const
+  {
+    return m_pitEntries;
+  }
 
   void
   insertPitEntry(shared_ptr<pit::Entry> pitEntry);
@@ -102,118 +140,38 @@
   void
   erasePitEntry(shared_ptr<pit::Entry> pitEntry);
 
-  bool
-  hasPitEntries() const;
-
-  const std::vector<shared_ptr<pit::Entry>>&
-  getPitEntries() const;
+  measurements::Entry*
+  getMeasurementsEntry() const
+  {
+    return m_measurementsEntry.get();
+  }
 
   void
   setMeasurementsEntry(unique_ptr<measurements::Entry> measurementsEntry);
 
-  measurements::Entry*
-  getMeasurementsEntry() const;
+  strategy_choice::Entry*
+  getStrategyChoiceEntry() const
+  {
+    return m_strategyChoiceEntry.get();
+  }
 
   void
   setStrategyChoiceEntry(unique_ptr<strategy_choice::Entry> strategyChoiceEntry);
 
-  strategy_choice::Entry*
-  getStrategyChoiceEntry() const;
-
 private:
-  // Benefits of storing m_hash
-  // 1. m_hash is compared before m_prefix is compared
-  // 2. fast hash table resize support
-  size_t m_hash;
-  Name m_prefix;
-  shared_ptr<Entry> m_parent;     // Pointing to the parent entry.
-  std::vector<shared_ptr<Entry>> m_children; // Children pointers.
+  Name m_name;
+  Node* m_node;
+  Entry* m_parent;
+  std::vector<Entry*> m_children;
+
   unique_ptr<fib::Entry> m_fibEntry;
   std::vector<shared_ptr<pit::Entry>> m_pitEntries;
   unique_ptr<measurements::Entry> m_measurementsEntry;
   unique_ptr<strategy_choice::Entry> m_strategyChoiceEntry;
 
-  // get the Name Tree Node that is associated with this Name Tree Entry
-  Node* m_node;
-
-  friend class NameTree;
-  friend class FullEnumerationImpl;
-  friend class PartialEnumerationImpl;
-  friend class PrefixMatchImpl;
+  friend Node* getNode(const Entry& entry);
 };
 
-inline const Name&
-Entry::getPrefix() const
-{
-  return m_prefix;
-}
-
-inline size_t
-Entry::getHash() const
-{
-  return m_hash;
-}
-
-inline void
-Entry::setHash(size_t hash)
-{
-  m_hash = hash;
-}
-
-inline shared_ptr<Entry>
-Entry::getParent() const
-{
-  return m_parent;
-}
-
-inline void
-Entry::setParent(shared_ptr<Entry> parent)
-{
-  m_parent = parent;
-}
-
-inline std::vector<shared_ptr<name_tree::Entry>>&
-Entry::getChildren()
-{
-  return m_children;
-}
-
-inline bool
-Entry::hasChildren() const
-{
-  return !m_children.empty();
-}
-
-inline fib::Entry*
-Entry::getFibEntry() const
-{
-  return m_fibEntry.get();
-}
-
-inline bool
-Entry::hasPitEntries() const
-{
-  return !m_pitEntries.empty();
-}
-
-inline const std::vector<shared_ptr<pit::Entry>>&
-Entry::getPitEntries() const
-{
-  return m_pitEntries;
-}
-
-inline measurements::Entry*
-Entry::getMeasurementsEntry() const
-{
-  return m_measurementsEntry.get();
-}
-
-inline strategy_choice::Entry*
-Entry::getStrategyChoiceEntry() const
-{
-  return m_strategyChoiceEntry.get();
-}
-
 } // namespace name_tree
 } // namespace nfd
 
diff --git a/daemon/table/name-tree-hashtable.cpp b/daemon/table/name-tree-hashtable.cpp
new file mode 100644
index 0000000..1267f99
--- /dev/null
+++ b/daemon/table/name-tree-hashtable.cpp
@@ -0,0 +1,280 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "name-tree-hashtable.hpp"
+#include "name-tree-entry.hpp"
+#include "core/logger.hpp"
+#include "core/city-hash.hpp"
+
+namespace nfd {
+namespace name_tree {
+
+NFD_LOG_INIT("NameTreeHashtable");
+
+class Hash32
+{
+public:
+  static HashValue
+  compute(const void* buffer, size_t length)
+  {
+    return static_cast<HashValue>(CityHash32(reinterpret_cast<const char*>(buffer), length));
+  }
+};
+
+class Hash64
+{
+public:
+  static HashValue
+  compute(const void* buffer, size_t length)
+  {
+    return static_cast<HashValue>(CityHash64(reinterpret_cast<const char*>(buffer), length));
+  }
+};
+
+/** \brief a type with compute static method to compute hash value from a raw buffer
+ */
+typedef std::conditional<(sizeof(HashValue) > 4), Hash64, Hash32>::type HashFunc;
+
+HashValue
+computeHash(const Name& name, ssize_t prefixLen)
+{
+  name.wireEncode(); // ensure wire buffer exists
+
+  HashValue h = 0;
+  for (size_t i = 0, last = prefixLen < 0 ? name.size() : prefixLen; i < last; ++i) {
+    const name::Component& comp = name[i];
+    h ^= HashFunc::compute(comp.wire(), comp.size());
+  }
+  return h;
+}
+
+HashSequence
+computeHashes(const Name& name)
+{
+  name.wireEncode(); // ensure wire buffer exists
+
+  HashSequence seq;
+  seq.reserve(name.size() + 1);
+
+  HashValue h = 0;
+  seq.push_back(h);
+
+  for (const name::Component& comp : name) {
+    h ^= HashFunc::compute(comp.wire(), comp.size());
+    seq.push_back(h);
+  }
+  return seq;
+}
+
+Node::Node(HashValue h, const Name& name)
+  : hash(h)
+  , prev(nullptr)
+  , next(nullptr)
+  , entry(make_shared<Entry>(name, this))
+{
+}
+
+Node::~Node()
+{
+  BOOST_ASSERT(prev == nullptr);
+  BOOST_ASSERT(next == nullptr);
+}
+
+Node*
+getNode(const Entry& entry)
+{
+  return entry.m_node;
+}
+
+HashtableOptions::HashtableOptions(size_t size)
+  : initialSize(size)
+  , minSize(size)
+{
+}
+
+Hashtable::Hashtable(const Options& options)
+  : m_options(options)
+  , m_size(0)
+{
+  BOOST_ASSERT(m_options.minSize > 0);
+  BOOST_ASSERT(m_options.initialSize >= m_options.minSize);
+  BOOST_ASSERT(m_options.expandLoadFactor > 0.0);
+  BOOST_ASSERT(m_options.expandLoadFactor <= 1.0);
+  BOOST_ASSERT(m_options.expandFactor > 1.0);
+  BOOST_ASSERT(m_options.shrinkLoadFactor >= 0.0);
+  BOOST_ASSERT(m_options.shrinkLoadFactor < 1.0);
+  BOOST_ASSERT(m_options.shrinkFactor > 0.0);
+  BOOST_ASSERT(m_options.shrinkFactor < 1.0);
+
+  m_buckets.resize(options.initialSize);
+  this->computeThresholds();
+}
+
+Hashtable::~Hashtable()
+{
+  for (size_t i = 0; i < m_buckets.size(); ++i) {
+    foreachNode(m_buckets[i], [] (Node* node) {
+      node->prev = node->next = nullptr;
+      delete node;
+    });
+  }
+}
+
+void
+Hashtable::attach(size_t bucket, Node* node)
+{
+  node->prev = nullptr;
+  node->next = m_buckets[bucket];
+
+  if (node->next != nullptr) {
+    BOOST_ASSERT(node->next->prev == nullptr);
+    node->next->prev = node;
+  }
+
+  m_buckets[bucket] = node;
+}
+
+void
+Hashtable::detach(size_t bucket, Node* node)
+{
+  if (node->prev != nullptr) {
+    BOOST_ASSERT(node->prev->next == node);
+    node->prev->next = node->next;
+  }
+  else {
+    BOOST_ASSERT(m_buckets[bucket] == node);
+    m_buckets[bucket] = node->next;
+  }
+
+  if (node->next != nullptr) {
+    BOOST_ASSERT(node->next->prev == node);
+    node->next->prev = node->prev;
+  }
+
+  node->prev = node->next = nullptr;
+}
+
+std::pair<const Node*, bool>
+Hashtable::findOrInsert(const Name& name, size_t prefixLen, HashValue h, bool allowInsert)
+{
+  size_t bucket = this->computeBucketIndex(h);
+
+  for (const Node* node = m_buckets[bucket]; node != nullptr; node = node->next) {
+    if (node->hash == h && name.compare(0, prefixLen, node->entry->getName()) == 0) {
+      NFD_LOG_TRACE("found " << name.getPrefix(prefixLen) << " hash=" << h << " bucket=" << bucket);
+      return {node, false};
+    }
+  }
+
+  if (!allowInsert) {
+    NFD_LOG_TRACE("not-found " << name.getPrefix(prefixLen) << " hash=" << h << " bucket=" << bucket);
+    return {nullptr, false};
+  }
+
+  Node* node = new Node(h, name.getPrefix(prefixLen));
+  this->attach(bucket, node);
+  NFD_LOG_TRACE("insert " << node->entry->getName() << " hash=" << h << " bucket=" << bucket);
+  ++m_size;
+
+  if (m_size > m_expandThreshold) {
+    this->resize(static_cast<size_t>(m_options.expandFactor * this->getNBuckets()));
+  }
+
+  return {node, true};
+}
+
+const Node*
+Hashtable::find(const Name& name, size_t prefixLen) const
+{
+  HashValue h = computeHash(name, prefixLen);
+  return const_cast<Hashtable*>(this)->findOrInsert(name, prefixLen, h, false).first;
+}
+
+const Node*
+Hashtable::find(const Name& name, size_t prefixLen, const HashSequence& hashes) const
+{
+  BOOST_ASSERT(hashes.at(prefixLen) == computeHash(name, prefixLen));
+  return const_cast<Hashtable*>(this)->findOrInsert(name, prefixLen, hashes[prefixLen], false).first;
+}
+
+std::pair<const Node*, bool>
+Hashtable::insert(const Name& name, size_t prefixLen, const HashSequence& hashes)
+{
+  BOOST_ASSERT(hashes.at(prefixLen) == computeHash(name, prefixLen));
+  return this->findOrInsert(name, prefixLen, hashes[prefixLen], true);
+}
+
+void
+Hashtable::erase(Node* node)
+{
+  BOOST_ASSERT(node != nullptr);
+  BOOST_ASSERT(node->entry->getParent() == nullptr);
+
+  size_t bucket = this->computeBucketIndex(node->hash);
+  NFD_LOG_TRACE("erase " << node->entry->getName() << " hash=" << node->hash << " bucket=" << bucket);
+
+  this->detach(bucket, node);
+  delete node;
+  --m_size;
+
+  if (m_size < m_shrinkThreshold) {
+    size_t newNBuckets = std::max(m_options.minSize,
+      static_cast<size_t>(m_options.shrinkFactor * this->getNBuckets()));
+    this->resize(newNBuckets);
+  }
+}
+
+void
+Hashtable::computeThresholds()
+{
+  m_expandThreshold = static_cast<size_t>(m_options.expandLoadFactor * this->getNBuckets());
+  m_shrinkThreshold = static_cast<size_t>(m_options.shrinkLoadFactor * this->getNBuckets());
+  NFD_LOG_TRACE("thresholds expand=" << m_expandThreshold << " shrink=" << m_shrinkThreshold);
+}
+
+void
+Hashtable::resize(size_t newNBuckets)
+{
+  if (this->getNBuckets() == newNBuckets) {
+    return;
+  }
+  NFD_LOG_DEBUG("resize from=" << this->getNBuckets() << " to=" << newNBuckets);
+
+  std::vector<Node*> oldBuckets;
+  oldBuckets.swap(m_buckets);
+  m_buckets.resize(newNBuckets);
+
+  for (Node* head : oldBuckets) {
+    foreachNode(head, [this] (Node* node) {
+      size_t bucket = this->computeBucketIndex(node->hash);
+      this->attach(bucket, node);
+    });
+  }
+
+  this->computeThresholds();
+}
+
+} // namespace name_tree
+} // namespace nfd
diff --git a/daemon/table/name-tree-hashtable.hpp b/daemon/table/name-tree-hashtable.hpp
new file mode 100644
index 0000000..a9f0cfa
--- /dev/null
+++ b/daemon/table/name-tree-hashtable.hpp
@@ -0,0 +1,254 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016,  Regents of the University of California,
+ *                           Arizona Board of Regents,
+ *                           Colorado State University,
+ *                           University Pierre & Marie Curie, Sorbonne University,
+ *                           Washington University in St. Louis,
+ *                           Beijing Institute of Technology,
+ *                           The University of Memphis.
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
+#define NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
+
+#include "core/common.hpp"
+
+namespace nfd {
+namespace name_tree {
+
+class Entry;
+
+/** \brief a single hash value
+ */
+typedef size_t HashValue;
+
+/** \brief a sequence of hash values
+ *  \sa computeHashes
+ */
+typedef std::vector<HashValue> HashSequence;
+
+/** \brief computes a single hash value
+ *  \param name base name
+ *  \param prefixLen if non-negative, compute hash value for name.getPrefix(prefixLen);
+ *                   if negative, compute hash value for complete name
+ */
+HashValue
+computeHash(const Name& name, ssize_t prefixLen = -1);
+
+/** \brief computes hash values for each prefix of name
+ *  \return a hash sequence, where the i-th hash value equals computeHash(name, i)
+ */
+HashSequence
+computeHashes(const Name& name);
+
+/** \brief a hashtable node
+ *
+ *  Zero or more nodes can be added to a hashtable bucket. They are organized as
+ *  a doubly linked list through prev and next pointers.
+ */
+class Node
+{
+public:
+  /** \post entry != nullptr && entry->getName() == name
+   */
+  Node(HashValue h, const Name& name);
+
+  /** \pre prev == nullptr
+   *  \pre next == nullptr
+   */
+  ~Node();
+
+public:
+  HashValue hash;
+  Node* prev;
+  Node* next;
+  shared_ptr<Entry> entry; /// \todo #3687 make Node sole owner of Entry
+};
+
+/** \return node associated with entry
+ *  \note This function is for NameTree internal use.
+ */
+Node*
+getNode(const Entry& entry);
+
+/** \brief invoke a function for each node in a doubly linked list
+ *  \tparam N either Node or const Node
+ *  \tparam F a functor with signature void F(N*)
+ *  \note It's safe to delete the node in the function.
+ */
+template<typename N, typename F>
+void
+foreachNode(N* head, const F& func)
+{
+  N* node = head;
+  while (node != nullptr) {
+    N* next = node->next;
+    func(node);
+    node = next;
+  }
+}
+
+/** \brief provides options for Hashtable
+ */
+class HashtableOptions
+{
+public:
+  /** \brief constructor
+   *  \post initialSize == size
+   *  \post minSize == size
+   */
+  explicit
+  HashtableOptions(size_t size = 16);
+
+public:
+  /** \brief initial number of buckets
+   */
+  size_t initialSize;
+
+  /** \brief minimal number of buckets
+   */
+  size_t minSize;
+
+  /** \brief if hashtable has more than nBuckets*expandLoadFactor nodes, it will be expanded
+   */
+  float expandLoadFactor = 0.5;
+
+  /** \brief when hashtable is expanded, its new size is nBuckets*expandFactor
+   */
+  float expandFactor = 2.0;
+
+  /** \brief if hashtable has less than nBuckets*shrinkLoadFactor nodes, it will be shrunk
+   */
+  float shrinkLoadFactor = 0.1;
+
+  /** \brief when hashtable is shrunk, its new size is max(nBuckets*shrinkFactor, minSize)
+   */
+  float shrinkFactor = 0.5;
+};
+
+/** \brief a hashtable for fast exact name lookup
+ *
+ *  The Hashtable contains a number of buckets.
+ *  Each node is placed into a bucket determined by a hash value computed from its name.
+ *  Hash collision is resolved through a doubly linked list in each bucket.
+ *  The number of buckets is adjusted according to how many nodes are stored.
+ */
+class Hashtable
+{
+public:
+  typedef HashtableOptions Options;
+
+  explicit
+  Hashtable(const Options& options);
+
+  /** \brief deallocates all nodes
+   */
+  ~Hashtable();
+
+  /** \return number of nodes
+   */
+  size_t
+  size() const
+  {
+    return m_size;
+  }
+
+  /** \return number of buckets
+   */
+  size_t
+  getNBuckets() const
+  {
+    return m_buckets.size();
+  }
+
+  /** \return bucket index for hash value h
+   */
+  size_t
+  computeBucketIndex(HashValue h) const
+  {
+    return h % this->getNBuckets();
+  }
+
+  /** \return i-th bucket
+   *  \pre bucket < getNBuckets()
+   */
+  const Node*
+  getBucket(size_t bucket) const
+  {
+    BOOST_ASSERT(bucket < this->getNBuckets());
+    return m_buckets[bucket]; // don't use m_bucket.at() for better performance
+  }
+
+  /** \brief find node for name.getPrefix(prefixLen)
+   *  \pre name.size() > prefixLen
+   */
+  const Node*
+  find(const Name& name, size_t prefixLen) const;
+
+  /** \brief find node for name.getPrefix(prefixLen)
+   *  \pre name.size() > prefixLen
+   *  \pre hashes == computeHashes(name)
+   */
+  const Node*
+  find(const Name& name, size_t prefixLen, const HashSequence& hashes) const;
+
+  /** \brief find or insert node for name.getPrefix(prefixLen)
+   *  \pre name.size() > prefixLen
+   *  \pre hashes == computeHashes(name)
+   */
+  std::pair<const Node*, bool>
+  insert(const Name& name, size_t prefixLen, const HashSequence& hashes);
+
+  /** \brief delete node
+   *  \pre node exists in this hashtable
+   */
+  void
+  erase(Node* node);
+
+private:
+  /** \brief attach node to bucket
+   */
+  void
+  attach(size_t bucket, Node* node);
+
+  /** \brief detach node from bucket
+   */
+  void
+  detach(size_t bucket, Node* node);
+
+  std::pair<const Node*, bool>
+  findOrInsert(const Name& name, size_t prefixLen, HashValue h, bool allowInsert);
+
+  void
+  computeThresholds();
+
+  void
+  resize(size_t newNBuckets);
+
+private:
+  std::vector<Node*> m_buckets;
+  Options m_options;
+  size_t m_size;
+  size_t m_expandThreshold;
+  size_t m_shrinkThreshold;
+};
+
+} // namespace name_tree
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_NAME_TREE_HASHTABLE_HPP
diff --git a/daemon/table/name-tree-iterator.cpp b/daemon/table/name-tree-iterator.cpp
index 31077be..9832dcd 100644
--- a/daemon/table/name-tree-iterator.cpp
+++ b/daemon/table/name-tree-iterator.cpp
@@ -41,12 +41,15 @@
               "Iterator must be default-constructible");
 
 Iterator::Iterator()
-  : m_state(0)
+  : m_entry(nullptr)
+  , m_ref(nullptr)
+  , m_state(0)
 {
 }
 
-Iterator::Iterator(shared_ptr<EnumerationImpl> impl, shared_ptr<Entry> ref)
+Iterator::Iterator(shared_ptr<EnumerationImpl> impl, const Entry* ref)
   : m_impl(impl)
+  , m_entry(nullptr)
   , m_ref(ref)
   , m_state(0)
 {
@@ -98,8 +101,9 @@
   return os;
 }
 
-EnumerationImpl::EnumerationImpl(const NameTree& nt1)
-  : nt(nt1)
+EnumerationImpl::EnumerationImpl(const NameTree& nt)
+  : nt(nt)
+  , ht(nt.m_ht)
 {
 }
 
@@ -112,37 +116,38 @@
 void
 FullEnumerationImpl::advance(Iterator& i)
 {
-  // find initial entry
+  // find first entry
   if (i.m_entry == nullptr) {
-    for (size_t bucket = 0; bucket < nt.m_nBuckets; ++bucket) {
-      Node* node = nt.m_buckets[bucket];
+    for (size_t bucket = 0; bucket < ht.getNBuckets(); ++bucket) {
+      const Node* node = ht.getBucket(bucket);
       if (node != nullptr) {
-        i.m_entry = node->m_entry;
+        i.m_entry = node->entry.get();
         break;
       }
     }
-    if (i.m_entry == nullptr) { // empty enumeration
+    if (i.m_entry == nullptr) { // empty enumerable
       i = Iterator();
       return;
     }
-    if (m_pred(*i.m_entry)) { // visit initial entry
+    if (m_pred(*i.m_entry)) { // visit first entry
       return;
     }
   }
 
   // process entries in same bucket
-  for (Node* node = i.m_entry->m_node->m_next; node != nullptr; node = node->m_next) {
-    if (m_pred(*node->m_entry)) {
-      i.m_entry = node->m_entry;
+  for (const Node* node = getNode(*i.m_entry)->next; node != nullptr; node = node->next) {
+    if (m_pred(*node->entry)) {
+      i.m_entry = node->entry.get();
       return;
     }
   }
 
   // process other buckets
-  for (size_t bucket = i.m_entry->m_hash % nt.m_nBuckets + 1; bucket < nt.m_nBuckets; ++bucket) {
-    for (Node* node = nt.m_buckets[bucket]; node != nullptr; node = node->m_next) {
-      if (m_pred(*node->m_entry)) {
-        i.m_entry = node->m_entry;
+  size_t currentBucket = ht.computeBucketIndex(getNode(*i.m_entry)->hash);
+  for (size_t bucket = currentBucket + 1; bucket < ht.getNBuckets(); ++bucket) {
+    for (const Node* node = ht.getBucket(bucket); node != nullptr; node = node->next) {
+      if (m_pred(*node->entry)) {
+        i.m_entry = node->entry.get();
         return;
       }
     }
@@ -166,7 +171,7 @@
 
   // initialize: start from root
   if (i.m_entry == nullptr) {
-    if (i.m_ref == nullptr) { // empty enumeration
+    if (i.m_ref == nullptr) { // root does not exist
       i = Iterator();
       return;
     }
@@ -195,8 +200,8 @@
       // first child rejected, let while loop process other children (siblings of new m_entry)
     }
     else { // process siblings of m_entry
-      shared_ptr<Entry> parent = i.m_entry->getParent();
-      const std::vector<shared_ptr<Entry>>& siblings = parent->getChildren();
+      const Entry* parent = i.m_entry->getParent();
+      const std::vector<Entry*>& siblings = parent->getChildren();
       auto sibling = std::find(siblings.begin(), siblings.end(), i.m_entry);
       BOOST_ASSERT(sibling != siblings.end());
       while (++sibling != siblings.end()) {
@@ -232,7 +237,7 @@
 PrefixMatchImpl::advance(Iterator& i)
 {
   if (i.m_entry == nullptr) {
-    if (i.m_ref == nullptr) { // empty enumeration
+    if (i.m_ref == nullptr) { // empty enumerable
       i = Iterator();
       return;
     }
diff --git a/daemon/table/name-tree-iterator.hpp b/daemon/table/name-tree-iterator.hpp
index a764677..fcc57b1 100644
--- a/daemon/table/name-tree-iterator.hpp
+++ b/daemon/table/name-tree-iterator.hpp
@@ -72,7 +72,7 @@
 public:
   Iterator();
 
-  Iterator(shared_ptr<EnumerationImpl> impl, shared_ptr<Entry> ref);
+  Iterator(shared_ptr<EnumerationImpl> impl, const Entry* ref);
 
   virtual
   ~Iterator() = default;
@@ -84,7 +84,7 @@
     return *m_entry;
   }
 
-  shared_ptr<Entry>
+  const Entry*
   operator->() const
   {
     BOOST_ASSERT(m_impl != nullptr);
@@ -113,11 +113,11 @@
 
   /** \brief current entry; nullptr for uninitialized iterator
    */
-  shared_ptr<Entry> m_entry;
+  const Entry* m_entry;
 
   /** \brief reference entry used by enumeration implementation
    */
-  shared_ptr<Entry> m_ref;
+  const Entry* m_ref;
 
   /** \brief state used by enumeration implementation
    */
@@ -145,6 +145,7 @@
 
 protected:
   const NameTree& nt;
+  const Hashtable& ht;
 };
 
 /** \brief full enumeration implementation
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 09b57f7..bbe5784 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -25,7 +25,6 @@
 
 #include "name-tree.hpp"
 #include "core/logger.hpp"
-#include "core/city-hash.hpp"
 
 #include <boost/concept/assert.hpp>
 #include <boost/concept_check.hpp>
@@ -36,190 +35,30 @@
 
 NFD_LOG_INIT("NameTree");
 
-// http://en.cppreference.com/w/cpp/concept/ForwardIterator
-BOOST_CONCEPT_ASSERT((boost::ForwardIterator<NameTree::const_iterator>));
-// boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
-// which doesn't require DefaultConstructible
-#ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
-static_assert(std::is_default_constructible<NameTree::const_iterator>::value,
-              "NameTree::const_iterator must be default-constructible");
-#else
-BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<NameTree::const_iterator>));
-#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
-
-class Hash32
-{
-public:
-  static size_t
-  compute(const char* buffer, size_t length)
-  {
-    return static_cast<size_t>(CityHash32(buffer, length));
-  }
-};
-
-class Hash64
-{
-public:
-  static size_t
-  compute(const char* buffer, size_t length)
-  {
-    return static_cast<size_t>(CityHash64(buffer, length));
-  }
-};
-
-/// @cond NoDocumentation
-typedef boost::mpl::if_c<sizeof(size_t) >= 8, Hash64, Hash32>::type CityHash;
-/// @endcond
-
-// Interface of different hash functions
-size_t
-computeHash(const Name& prefix)
-{
-  prefix.wireEncode();  // guarantees prefix's wire buffer is not empty
-
-  size_t hashValue = 0;
-  size_t hashUpdate = 0;
-
-  for (Name::const_iterator it = prefix.begin(); it != prefix.end(); ++it) {
-    const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
-    hashUpdate = CityHash::compute(wireFormat, it->size());
-    hashValue ^= hashUpdate;
-  }
-
-  return hashValue;
-}
-
-std::vector<size_t>
-computeHashSet(const Name& prefix)
-{
-  prefix.wireEncode(); // guarantees prefix's wire buffer is not empty
-
-  size_t hashValue = 0;
-  size_t hashUpdate = 0;
-
-  std::vector<size_t> hashValueSet;
-  hashValueSet.push_back(hashValue);
-
-  for (Name::const_iterator it = prefix.begin(); it != prefix.end(); ++it) {
-    const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
-    hashUpdate = CityHash::compute(wireFormat, it->size());
-    hashValue ^= hashUpdate;
-    hashValueSet.push_back(hashValue);
-  }
-
-  return hashValueSet;
-}
-
 NameTree::NameTree(size_t nBuckets)
-  : m_nItems(0)
-  , m_nBuckets(nBuckets)
-  , m_minNBuckets(nBuckets)
-  , m_enlargeLoadFactor(0.5) // more than 50% buckets loaded
-  , m_enlargeFactor(2)       // double the hash table size
-  , m_shrinkLoadFactor(0.1)  // less than 10% buckets loaded
-  , m_shrinkFactor(0.5)      // reduce the number of buckets by half
+  : m_ht(HashtableOptions(nBuckets))
 {
-  m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor * static_cast<double>(m_nBuckets));
-  m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor * static_cast<double>(m_nBuckets));
-
-  // array of node pointers
-  m_buckets = new Node*[m_nBuckets];
-  // Initialize the pointer array
-  for (size_t i = 0; i < m_nBuckets; ++i) {
-    m_buckets[i] = nullptr;
-  }
 }
 
-NameTree::~NameTree()
-{
-  for (size_t i = 0; i < m_nBuckets; ++i) {
-    if (m_buckets[i] != nullptr) {
-      delete m_buckets[i];
-    }
-  }
-
-  delete[] m_buckets;
-}
-
-// insert() is a private function, and called by only lookup()
-std::pair<shared_ptr<Entry>, bool>
-NameTree::insert(const Name& prefix)
-{
-  NFD_LOG_TRACE("insert " << prefix);
-
-  size_t hashValue = computeHash(prefix);
-  size_t loc = hashValue % m_nBuckets;
-
-  NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue << "  location = " << loc);
-
-  // Check if this Name has been stored
-  Node* node = m_buckets[loc];
-  Node* nodePrev = node;
-
-  for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
-    if (node->m_entry != nullptr) {
-      if (prefix == node->m_entry->m_prefix) {
-         return {node->m_entry, false}; // false: old entry
-      }
-    }
-    nodePrev = node;
-  }
-
-  NFD_LOG_TRACE("Did not find " << prefix << ", need to insert it to the table");
-
-  // If no bucket is empty occupied, we need to create a new node, and it is
-  // linked from nodePrev
-  node = new Node();
-  node->m_prev = nodePrev;
-
-  if (nodePrev == nullptr) {
-    m_buckets[loc] = node;
-  }
-  else{
-    nodePrev->m_next = node;
-  }
-
-  // Create a new Entry
-  auto entry = make_shared<Entry>(prefix);
-  entry->setHash(hashValue);
-  node->m_entry = entry; // link the Entry to its Node
-  entry->m_node = node; // link the node to Entry. Used in eraseEntryIfEmpty.
-
-  return {entry, true}; // true: new entry
-}
-
-// Name Prefix Lookup. Create Name Tree Entry if not found
 shared_ptr<Entry>
-NameTree::lookup(const Name& prefix)
+NameTree::lookup(const Name& name)
 {
-  NFD_LOG_TRACE("lookup " << prefix);
+  NFD_LOG_TRACE("lookup " << name);
 
-  shared_ptr<Entry> entry;
-  shared_ptr<Entry> parent;
+  HashSequence hashes = computeHashes(name);
+  const Node* node = nullptr;
+  Entry* parent = nullptr;
 
-  for (size_t i = 0; i <= prefix.size(); ++i) {
-    Name temp = prefix.getPrefix(i);
-
-    // insert() will create the entry if it does not exist.
+  for (size_t prefixLen = 0; prefixLen <= name.size(); ++prefixLen) {
     bool isNew = false;
-    std::tie(entry, isNew) = insert(temp);
+    std::tie(node, isNew) = m_ht.insert(name, prefixLen, hashes);
 
-    if (isNew) {
-      ++m_nItems; // Increase the counter
-      entry->m_parent = parent;
-
-      if (parent != nullptr) {
-        parent->m_children.push_back(entry);
-      }
+    if (isNew && parent != nullptr) {
+      node->entry->setParent(*parent);
     }
-
-    if (m_nItems > m_enlargeThreshold) {
-      resize(m_enlargeFactor * m_nBuckets);
-    }
-
-    parent = entry;
+    parent = node->entry.get();
   }
-  return entry;
+  return node->entry;
 }
 
 shared_ptr<Entry>
@@ -263,132 +102,46 @@
   return nte;
 }
 
-// return {false: this entry is not empty, true: this entry is empty and erased}
-bool
-NameTree::eraseEntryIfEmpty(shared_ptr<Entry> entry)
+size_t
+NameTree::eraseEntryIfEmpty(Entry* entry)
 {
   BOOST_ASSERT(entry != nullptr);
 
-  NFD_LOG_TRACE("eraseEntryIfEmpty " << entry->getPrefix());
-
-  // first check if this Entry can be erased
-  if (entry->isEmpty()) {
-    // update child-related info in the parent
-    shared_ptr<Entry> parent = entry->getParent();
+  size_t nErased = 0;
+  for (Entry* parent = nullptr; entry != nullptr && entry->isEmpty(); entry = parent) {
+    parent = entry->getParent();
 
     if (parent != nullptr) {
-      std::vector<shared_ptr<Entry>>& parentChildrenList = parent->getChildren();
-
-      bool isFound = false;
-      size_t size = parentChildrenList.size();
-      for (size_t i = 0; i < size; ++i) {
-        if (parentChildrenList[i] == entry) {
-          parentChildrenList[i] = parentChildrenList[size - 1];
-          parentChildrenList.pop_back();
-          isFound = true;
-          break;
-        }
-      }
-
-      BOOST_VERIFY(isFound == true);
+      entry->unsetParent();
     }
 
-    // remove this Entry and its Name Tree Node
-    Node* node = entry->m_node;
-    Node* nodePrev = node->m_prev;
-
-    // configure the previous node
-    if (nodePrev != nullptr) {
-      // link the previous node to the next node
-      nodePrev->m_next = node->m_next;
-    }
-    else {
-      m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
-    }
-
-    // link the previous node with the next node (skip the erased one)
-    if (node->m_next != nullptr) {
-      node->m_next->m_prev = nodePrev;
-      node->m_next = 0;
-    }
-
-    BOOST_ASSERT(node->m_next == nullptr);
-
-    --m_nItems;
-    delete node;
-
-    if (parent != nullptr) {
-      eraseEntryIfEmpty(parent);
-    }
-
-    size_t newNBuckets = static_cast<size_t>(m_shrinkFactor * static_cast<double>(m_nBuckets));
-
-    if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold) {
-      resize(newNBuckets);
-    }
-
-    return true;
-
+    m_ht.erase(getNode(*entry));
+    ++nErased;
   }
 
-  return false;
+  if (nErased == 0) {
+    NFD_LOG_TRACE("not-erase " << entry->getName());
+  }
+  return nErased;
 }
 
-// Exact Match
 shared_ptr<Entry>
-NameTree::findExactMatch(const Name& prefix) const
+NameTree::findExactMatch(const Name& name) const
 {
-  NFD_LOG_TRACE("findExactMatch " << prefix);
-
-  size_t hashValue = computeHash(prefix);
-  size_t loc = hashValue % m_nBuckets;
-
-  NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue << "  location = " << loc);
-
-  shared_ptr<Entry> entry;
-  Node* node = nullptr;
-
-  for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
-    entry = node->m_entry;
-    if (entry != nullptr) {
-      if (hashValue == entry->getHash() && prefix == entry->getPrefix()) {
-        return entry;
-      }
-    }
-  }
-
-  // if not found, the default value of entry (null pointer) will be returned
-  entry.reset();
-  return entry;
+  const Node* node = m_ht.find(name, name.size());
+  return node == nullptr ? nullptr : node->entry;
 }
 
 // Longest Prefix Match
 shared_ptr<Entry>
-NameTree::findLongestPrefixMatch(const Name& prefix, const EntrySelector& entrySelector) const
+NameTree::findLongestPrefixMatch(const Name& name, const EntrySelector& entrySelector) const
 {
-  NFD_LOG_TRACE("findLongestPrefixMatch " << prefix);
+  HashSequence hashes = computeHashes(name);
 
-  shared_ptr<Entry> entry;
-  std::vector<size_t> hashValueSet = computeHashSet(prefix);
-
-  size_t hashValue = 0;
-  size_t loc = 0;
-
-  for (int i = static_cast<int>(prefix.size()); i >= 0; --i) {
-    hashValue = hashValueSet[i];
-    loc = hashValue % m_nBuckets;
-
-    Node* node = nullptr;
-    for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
-      entry = node->m_entry;
-      if (entry != nullptr) {
-        // isPrefixOf() is used to avoid making a copy of the name
-        if (hashValue == entry->getHash() &&
-            entry->getPrefix().isPrefixOf(prefix) &&
-            entrySelector(*entry)) {
-          return entry;
-        }
-      }
+  for (ssize_t prefixLen = name.size(); prefixLen >= 0; --prefixLen) {
+    const Node* node = m_ht.find(name, prefixLen, hashes);
+    if (node != nullptr && entrySelector(*node->entry)) {
+      return node->entry;
     }
   }
 
@@ -396,12 +149,13 @@
 }
 
 shared_ptr<Entry>
-NameTree::findLongestPrefixMatch(shared_ptr<Entry> entry,
+NameTree::findLongestPrefixMatch(shared_ptr<Entry> entry1,
                                  const EntrySelector& entrySelector) const
 {
+  Entry* entry = entry1.get();
   while (entry != nullptr) {
     if (entrySelector(*entry)) {
-      return entry;
+      return entry->shared_from_this();
     }
     entry = entry->getParent();
   }
@@ -436,7 +190,7 @@
   // trie from the root node.
 
   shared_ptr<Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
-  return {Iterator(make_shared<PrefixMatchImpl>(*this, entrySelector), entry), end()};
+  return {Iterator(make_shared<PrefixMatchImpl>(*this, entrySelector), entry.get()), end()};
 }
 
 boost::iterator_range<NameTree::const_iterator>
@@ -453,98 +207,7 @@
 {
   // the first step is to process the root node
   shared_ptr<Entry> entry = findExactMatch(prefix);
-  return {Iterator(make_shared<PartialEnumerationImpl>(*this, entrySubTreeSelector), entry), end()};
-}
-
-// Hash Table Resize
-void
-NameTree::resize(size_t newNBuckets)
-{
-  NFD_LOG_TRACE("resize");
-
-  Node** newBuckets = new Node*[newNBuckets];
-  size_t count = 0;
-
-  // referenced ccnx hashtb.c hashtb_rehash()
-  Node** pp = nullptr;
-  Node* p = nullptr;
-  Node* pre = nullptr;
-  Node* q = nullptr; // record p->m_next
-
-  for (size_t i = 0; i < newNBuckets; ++i) {
-    newBuckets[i] = nullptr;
-  }
-
-  for (size_t i = 0; i < m_nBuckets; ++i) {
-    for (p = m_buckets[i]; p != nullptr; p = q) {
-      ++count;
-      q = p->m_next;
-      BOOST_ASSERT(p->m_entry != nullptr);
-      uint32_t h = p->m_entry->m_hash;
-      uint32_t b = h % newNBuckets;
-      pre = nullptr;
-      for (pp = &newBuckets[b]; *pp != nullptr; pp = &((*pp)->m_next)) {
-        pre = *pp;
-      }
-      p->m_prev = pre;
-      p->m_next = *pp; // Actually *pp always == nullptr in this case
-      *pp = p;
-    }
-  }
-
-  BOOST_ASSERT(count == m_nItems);
-
-  Node** oldBuckets = m_buckets;
-  m_buckets = newBuckets;
-  delete[] oldBuckets;
-
-  m_nBuckets = newNBuckets;
-  m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor * static_cast<double>(m_nBuckets));
-  m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor * static_cast<double>(m_nBuckets));
-}
-
-// For debugging
-void
-NameTree::dump(std::ostream& output) const
-{
-  NFD_LOG_TRACE("dump()");
-
-  Node* node = nullptr;
-  shared_ptr<Entry> entry;
-
-  for (size_t i = 0; i < m_nBuckets; ++i) {
-    for (node = m_buckets[i]; node != nullptr; node = node->m_next) {
-      entry = node->m_entry;
-
-      // if the Entry exist, dump its information
-      if (entry != nullptr) {
-        output << "Bucket" << i << '\t' << entry->m_prefix.toUri() << '\n';
-        output << "\t\tHash " << entry->m_hash << '\n';
-
-        if (entry->m_parent != nullptr) {
-          output << "\t\tparent->" << entry->m_parent->m_prefix.toUri();
-        }
-        else {
-          output << "\t\tROOT";
-        }
-        output << '\n';
-
-        if (!entry->m_children.empty()) {
-          output << "\t\tchildren = " << entry->m_children.size() << '\n';
-
-          for (size_t j = 0; j < entry->m_children.size(); ++j) {
-            output << "\t\t\tChild " << j << " " << entry->m_children[j]->getPrefix() << '\n';
-          }
-        }
-
-      }
-
-    }
-  }
-
-  output << "Bucket count = " << m_nBuckets << '\n';
-  output << "Stored item = " << m_nItems << '\n';
-  output << "--------------------------\n";
+  return {Iterator(make_shared<PartialEnumerationImpl>(*this, entrySubTreeSelector), entry.get()), end()};
 }
 
 } // namespace name_tree
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 91ec3fa..ad9f314 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -31,19 +31,6 @@
 namespace nfd {
 namespace name_tree {
 
-/** \brief Compute the hash value of the given name prefix's WIRE FORMAT
- */
-size_t
-computeHash(const Name& prefix);
-
-/** \brief Incrementally compute hash values
- *  \return Return a vector of hash values, starting from the root prefix
- */
-std::vector<size_t>
-computeHashSet(const Name& prefix);
-
-/** \brief shared name-based index for FIB, PIT, Measurements, and StrategyChoice
- */
 class NameTree : noncopyable
 {
 public:
@@ -52,13 +39,14 @@
   explicit
   NameTree(size_t nBuckets = 1024);
 
-  ~NameTree();
-
 public: // information
   /** \brief Get the number of occupied entries in the Name Tree
    */
   size_t
-  size() const;
+  size() const
+  {
+    return m_ht.size();
+  }
 
   /** \brief Get the number of buckets in the Name Tree (NPHT)
    *
@@ -66,18 +54,19 @@
    *  table, i.e., m_nBuckets.
    */
   size_t
-  getNBuckets() const;
+  getNBuckets() const
+  {
+    return m_ht.getNBuckets();
+  }
 
   /** \return Name Tree Entry on which a table entry is attached
    */
   template<typename ENTRY>
   shared_ptr<Entry>
-  getEntry(const ENTRY& tableEntry) const;
-
-  /** \brief Dump all the information stored in the Name Tree for debugging.
-   */
-  void
-  dump(std::ostream& output) const;
+  getEntry(const ENTRY& tableEntry) const
+  {
+    return tableEntry.m_nameTreeEntry.lock();
+  }
 
 public: // mutation
   /** \brief Look for the Name Tree Entry that contains this name prefix.
@@ -86,12 +75,12 @@
    *  number of name components by one each time. All non-existing Name Tree
    *  Entries will be created.
    *
-   *  \param prefix The querying name prefix.
+   *  \param name The querying name prefix.
    *  \return The pointer to the Name Tree Entry that contains this full name prefix.
    *  \note Existing iterators are unaffected.
    */
   shared_ptr<Entry>
-  lookup(const Name& prefix);
+  lookup(const Name& name);
 
   /** \brief get NameTree entry from FIB entry
    *
@@ -128,15 +117,23 @@
    *        it has no children, then repeats the same process on its ancestors.
    *  \note Existing iterators, except those pointing to deleted entries, are unaffected.
    */
+  size_t
+  eraseEntryIfEmpty(Entry* entry);
+
+  /// \deprecated
   bool
-  eraseEntryIfEmpty(shared_ptr<Entry> entry);
+  eraseEntryIfEmpty(shared_ptr<Entry> entry)
+  {
+    BOOST_ASSERT(entry != nullptr);
+    return this->eraseEntryIfEmpty(entry.get()) > 0;
+  }
 
 public: // matching
   /** \brief Exact match lookup for the given name prefix.
    *  \return nullptr if this prefix is not found; otherwise return the Name Tree Entry address
    */
   shared_ptr<Entry>
-  findExactMatch(const Name& prefix) const;
+  findExactMatch(const Name& name) const;
 
   /** \brief Longest prefix matching for the given name
    *
@@ -144,7 +141,7 @@
    *  by one each time, until an Entry is found.
    */
   shared_ptr<Entry>
-  findLongestPrefixMatch(const Name& prefix,
+  findLongestPrefixMatch(const Name& name,
                          const EntrySelector& entrySelector = AnyEntry()) const;
 
   shared_ptr<Entry>
@@ -217,86 +214,27 @@
    *  \note The returned iterator may get invalidated when NameTree is modified
    */
   const_iterator
-  begin() const;
+  begin() const
+  {
+    return fullEnumerate().begin();
+  }
 
   /** \brief Get an iterator referring to the past-the-end FIB entry
    *  \note Iteration order is implementation-specific and is undefined
    *  \note The returned iterator may get invalidated when NameTree is modified
    */
   const_iterator
-  end() const;
+  end() const
+  {
+    return Iterator();
+  }
 
 private:
-  /** \brief Create a Name Tree Entry if it does not exist, or return the existing
-   *         Name Tree Entry address.
-   *
-   *  Called by lookup() only.
-   *
-   *  \return The first item is the Name Tree Entry address, the second item is
-   *          a bool value indicates whether this is an old entry (false) or a new
-   *          entry (true).
-   */
-  std::pair<shared_ptr<Entry>, bool>
-  insert(const Name& prefix);
+  Hashtable m_ht;
 
-  /** \brief Resize the hash table size when its load factor reaches a threshold.
-   *
-   *  As we are currently using a hand-written hash table implementation
-   *  for the Name Tree, the hash table resize() function should be kept in the
-   *  name-tree.hpp file.
-   *  \param newNBuckets The number of buckets for the new hash table.
-   */
-  void
-  resize(size_t newNBuckets);
-
-private:
-  size_t m_nItems;  ///< Number of items being stored
-  size_t m_nBuckets; ///< Number of hash buckets
-  size_t m_minNBuckets; ///< Minimum number of hash buckets
-  double m_enlargeLoadFactor;
-  size_t m_enlargeThreshold;
-  int m_enlargeFactor;
-  double m_shrinkLoadFactor;
-  size_t m_shrinkThreshold;
-  double m_shrinkFactor;
-  Node** m_buckets; ///< Name Tree Buckets in the NPHT
-
-  friend class FullEnumerationImpl;
-  friend class PartialEnumerationImpl;
-  friend class PrefixMatchImpl;
+  friend class EnumerationImpl;
 };
 
-inline size_t
-NameTree::size() const
-{
-  return m_nItems;
-}
-
-inline size_t
-NameTree::getNBuckets() const
-{
-  return m_nBuckets;
-}
-
-template<typename ENTRY>
-inline shared_ptr<Entry>
-NameTree::getEntry(const ENTRY& tableEntry) const
-{
-  return tableEntry.m_nameTreeEntry.lock();
-}
-
-inline NameTree::const_iterator
-NameTree::begin() const
-{
-  return fullEnumerate().begin();
-}
-
-inline NameTree::const_iterator
-NameTree::end() const
-{
-  return Iterator();
-}
-
 } // namespace name_tree
 
 using name_tree::NameTree;
diff --git a/tests/daemon/table/name-tree.t.cpp b/tests/daemon/table/name-tree.t.cpp
index 394f4d1..f87b50f 100644
--- a/tests/daemon/table/name-tree.t.cpp
+++ b/tests/daemon/table/name-tree.t.cpp
@@ -36,36 +36,166 @@
 BOOST_AUTO_TEST_SUITE(Table)
 BOOST_FIXTURE_TEST_SUITE(TestNameTree, BaseFixture)
 
-BOOST_AUTO_TEST_CASE(Hash)
+BOOST_AUTO_TEST_CASE(ComputeHash)
 {
   Name root("/");
   root.wireEncode();
-  size_t hashValue = computeHash(root);
+  HashValue hashValue = computeHash(root);
   BOOST_CHECK_EQUAL(hashValue, 0);
 
   Name prefix("/nohello/world/ndn/research");
   prefix.wireEncode();
-  std::vector<size_t> hashSet = computeHashSet(prefix);
-  BOOST_CHECK_EQUAL(hashSet.size(), prefix.size() + 1);
+  HashSequence hashes = computeHashes(prefix);
+  BOOST_CHECK_EQUAL(hashes.size(), prefix.size() + 1);
 }
 
+BOOST_AUTO_TEST_SUITE(Hashtable)
+using name_tree::Hashtable;
+
+BOOST_AUTO_TEST_CASE(Modifiers)
+{
+  Hashtable ht(HashtableOptions(16));
+
+  Name name("/A/B/C/D");
+  HashSequence hashes = computeHashes(name);
+
+  BOOST_CHECK_EQUAL(ht.size(), 0);
+  BOOST_CHECK(ht.find(name, 2) == nullptr);
+
+  const Node* node = nullptr;
+  bool isNew = false;
+  std::tie(node, isNew) = ht.insert(name, 2, hashes);
+  BOOST_CHECK_EQUAL(isNew, true);
+  BOOST_CHECK(node != nullptr);
+  BOOST_CHECK_EQUAL(ht.size(), 1);
+  BOOST_CHECK_EQUAL(ht.find(name, 2), node);
+  BOOST_CHECK_EQUAL(ht.find(name, 2, hashes), node);
+
+  BOOST_CHECK(ht.find(name, 0) == nullptr);
+  BOOST_CHECK(ht.find(name, 1) == nullptr);
+  BOOST_CHECK(ht.find(name, 3) == nullptr);
+  BOOST_CHECK(ht.find(name, 4) == nullptr);
+
+  const Node* node2 = nullptr;
+  std::tie(node2, isNew) = ht.insert(name, 2, hashes);
+  BOOST_CHECK_EQUAL(isNew, false);
+  BOOST_CHECK_EQUAL(node2, node);
+  BOOST_CHECK_EQUAL(ht.size(), 1);
+
+  std::tie(node2, isNew) = ht.insert(name, 4, hashes);
+  BOOST_CHECK_EQUAL(isNew, true);
+  BOOST_CHECK(node2 != nullptr);
+  BOOST_CHECK_NE(node2, node);
+  BOOST_CHECK_EQUAL(ht.size(), 2);
+
+  ht.erase(const_cast<Node*>(node2));
+  BOOST_CHECK_EQUAL(ht.size(), 1);
+  BOOST_CHECK(ht.find(name, 4) == nullptr);
+  BOOST_CHECK_EQUAL(ht.find(name, 2), node);
+
+  ht.erase(const_cast<Node*>(node));
+  BOOST_CHECK_EQUAL(ht.size(), 0);
+  BOOST_CHECK(ht.find(name, 2) == nullptr);
+  BOOST_CHECK(ht.find(name, 4) == nullptr);
+}
+
+BOOST_AUTO_TEST_CASE(Resize)
+{
+  HashtableOptions options(9);
+  BOOST_CHECK_EQUAL(options.initialSize, 9);
+  BOOST_CHECK_EQUAL(options.minSize, 9);
+  options.minSize = 6;
+  options.expandLoadFactor = 0.80;
+  options.expandFactor = 5.0;
+  options.shrinkLoadFactor = 0.12;
+  options.shrinkFactor = 0.3;
+
+  Hashtable ht(options);
+
+  auto addNodes = [&ht] (int min, int max) {
+    for (int i = min; i <= max; ++i) {
+      Name name;
+      name.appendNumber(i);
+      HashSequence hashes = computeHashes(name);
+      ht.insert(name, name.size(), hashes);
+    }
+  };
+
+  auto removeNodes = [&ht] (int min, int max) {
+    for (int i = min; i <= max; ++i) {
+      Name name;
+      name.appendNumber(i);
+      const Node* node = ht.find(name, name.size());
+      BOOST_REQUIRE(node != nullptr);
+      ht.erase(const_cast<Node*>(node));
+    }
+  };
+
+  BOOST_CHECK_EQUAL(ht.size(), 0);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 9);
+
+  addNodes(1, 1);
+  BOOST_CHECK_EQUAL(ht.size(), 1);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 9);
+
+  removeNodes(1, 1);
+  BOOST_CHECK_EQUAL(ht.size(), 0);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 6);
+
+  addNodes(1, 4);
+  BOOST_CHECK_EQUAL(ht.size(), 4);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 6);
+
+  addNodes(5, 5);
+  BOOST_CHECK_EQUAL(ht.size(), 5);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 30);
+
+  addNodes(6, 23);
+  BOOST_CHECK_EQUAL(ht.size(), 23);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 30);
+
+  addNodes(24, 25);
+  BOOST_CHECK_EQUAL(ht.size(), 25);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 150);
+
+  removeNodes(19, 25);
+  BOOST_CHECK_EQUAL(ht.size(), 18);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 150);
+
+  removeNodes(17, 18);
+  BOOST_CHECK_EQUAL(ht.size(), 16);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 45);
+
+  removeNodes(7, 16);
+  BOOST_CHECK_EQUAL(ht.size(), 6);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 45);
+
+  removeNodes(5, 6);
+  BOOST_CHECK_EQUAL(ht.size(), 4);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 13);
+
+  removeNodes(1, 4);
+  BOOST_CHECK_EQUAL(ht.size(), 0);
+  BOOST_CHECK_EQUAL(ht.getNBuckets(), 6);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // Hashtable
+
 BOOST_AUTO_TEST_CASE(NameTreeEntry)
 {
   Name prefix("ndn:/named-data/research/abc/def/ghi");
 
-  auto npe = make_shared<Entry>(prefix);
+  auto node = make_unique<Node>(0, prefix);
+  shared_ptr<Entry> npe = node->entry;
   BOOST_CHECK_EQUAL(npe->getPrefix(), prefix);
 
   // examine all the get methods
 
-  size_t hash = npe->getHash();
-  BOOST_CHECK_EQUAL(hash, 0);
-
-  shared_ptr<Entry> parent = npe->getParent();
+  Entry* parent = npe->getParent();
   BOOST_CHECK(parent == nullptr);
 
-  std::vector<shared_ptr<Entry>>& childList = npe->getChildren();
-  BOOST_CHECK_EQUAL(childList.size(), 0);
+  const std::vector<Entry*>& children = npe->getChildren();
+  BOOST_CHECK_EQUAL(children.size(), 0);
 
   fib::Entry* fib = npe->getFibEntry();
   BOOST_CHECK(fib == nullptr);
@@ -75,13 +205,10 @@
 
   // examine all the set method
 
-  npe->setHash(12345);
-  BOOST_CHECK_EQUAL(npe->getHash(), 12345);
-
   Name parentName("ndn:/named-data/research/abc/def");
-  parent = make_shared<Entry>(parentName);
-  npe->setParent(parent);
-  BOOST_CHECK_EQUAL(npe->getParent(), parent);
+  auto parentNode = make_unique<Node>(1, parentName);
+  npe->setParent(*parentNode->entry);
+  BOOST_CHECK_EQUAL(npe->getParent(), parentNode->entry.get());
 
   // Insert FIB
 
@@ -137,14 +264,14 @@
   // validate lookup() and findExactMatch()
 
   Name nameAB ("/a/b");
-  BOOST_CHECK_EQUAL(npeABC->getParent(), nt.findExactMatch(nameAB));
-  BOOST_CHECK_EQUAL(npeABD->getParent(), nt.findExactMatch(nameAB));
+  BOOST_CHECK_EQUAL(npeABC->getParent(), nt.findExactMatch(nameAB).get());
+  BOOST_CHECK_EQUAL(npeABD->getParent(), nt.findExactMatch(nameAB).get());
 
   Name nameA ("/a");
-  BOOST_CHECK_EQUAL(npeAE->getParent(), nt.findExactMatch(nameA));
+  BOOST_CHECK_EQUAL(npeAE->getParent(), nt.findExactMatch(nameA).get());
 
   Name nameRoot ("/");
-  BOOST_CHECK_EQUAL(npeF->getParent(), nt.findExactMatch(nameRoot));
+  BOOST_CHECK_EQUAL(npeF->getParent(), nt.findExactMatch(nameRoot).get());
   BOOST_CHECK_EQUAL(nt.size(), 7);
 
   Name name0("/does/not/exist");