<p>Your question in the first sentence is a bit vague and open-ended. I'm guessing you want to know about routing and mutual node knowledge in the context of lookup.</p>

<p>Each node shouldn't have to know about every other node. Assuming a hash ring topology, the simplest approach is to have each node know about its two neighbors on the ring. This defines a circular linked list. Unfortunately, as with all linked lists, it only supports slow linear search. It's also very sensitive to node removal: if any two nodes go offline, it breaks the connectivity of the ring.</p>

<p>If you try to repair this idea by having nodes maintain knowledge of their longer-range relatives then you eventually wind up with the idea of a skip graph, a generalization of skip lists that can handle node disappearance robustly. Unlike skip lists they are not explicitly stratified, which is important due to the non-hierarchical peer-to-peer nature of the problem.</p>

CC BY-SA 2.5
2010-10-05T03:04:50.373Z
2010-10-05T03:15:32.433Z
2010-10-05T03:15:32.433Z
Per Vognsen
<p>How is DHT different than regular hash tables in context to data/node lookup?</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.2405&amp;rep=rep1&amp;type=pdf" rel="nofollow">This</a> (introduction, 3rd paragraph) paper says:</p>

<blockquote>
  <p>First, in addition to the insertion
  and deletion of items, DHTs must support the insertion and deletion of
  buckets: as machines join and leave
  the network, items must be migrated to
  other machines and the hash function
  revised to reflect their new location.</p>
</blockquote>

<p>This problem is also in Hashtables (for example, if you implement a hashtable in C using LinkedList and Array, then if the size of the array increased (new node added) then the data needs to be redistributed to achieve good load factor)</p>

<blockquote>
  <p>Second, some kind of routing protocol
  is usually necessary: since it is not
  feasible in a P2P system for every
  node to maintain up-to-date knowledge
  of all other nodes in the system, an
  item is looked up (or inserted) by
  following a sequence of routing hops
  through the peer-to-peer network.</p>
</blockquote>

<p>Is this point talking about routing mechanism, if yes, then is this done is normal hashtable?</p>

<hash-function><dc.distributed-comp>
How is DHT different than regular hash tables in context to data/node lookup?
zengr
# How is DHT different than regular hash tables in context to data/node lookup?

(Asked by: username_0 on 2010-10-05)

How is DHT different than regular hash tables in context to data/node lookup?

[This](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.2405&rep=rep1&type=pdf) (introduction, 3rd paragraph) paper says:

> First, in addition to the insertion
> and deletion of items, DHTs must support the insertion and deletion of
> buckets: as machines join and leave
> the network, items must be migrated to
> other machines and the hash function
> revised to reflect their new location.

This problem is also in Hashtables (for example, if you implement a hashtable in C using LinkedList and Array, then if the size of the array increased (new node added) then the data needs to be redistributed to achieve good load factor)

> Second, some kind of routing protocol
> is usually necessary: since it is not
> feasible in a P2P system for every
> node to maintain up-to-date knowledge
> of all other nodes in the system, an
> item is looked up (or inserted) by
> following a sequence of routing hops
> through the peer-to-peer network.

Is this point talking about routing mechanism, if yes, then is this done is normal hashtable?

**Tags:** hash-function, dc.distributed-comp

---

## 1 answers

### Answer by username_1 on 2010-10-05. Score: 4 | Accepted answer

Your question in the first sentence is a bit vague and open-ended. I'm guessing you want to know about routing and mutual node knowledge in the context of lookup.

Each node shouldn't have to know about every other node. Assuming a hash ring topology, the simplest approach is to have each node know about its two neighbors on the ring. This defines a circular linked list. Unfortunately, as with all linked lists, it only supports slow linear search. It's also very sensitive to node removal: if any two nodes go offline, it breaks the connectivity of the ring.

If you try to repair this idea by having nodes maintain knowledge of their longer-range relatives then you eventually wind up with the idea of a skip graph, a generalization of skip lists that can handle node disappearance robustly. Unlike skip lists they are not explicitly stratified, which is important due to the non-hierarchical peer-to-peer nature of the problem.


---

