HashTable vs DHT
Hash table & DHT
先附上定义：In computer science, a hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person’s name), find the corresponding value (e.g. that person’s telephone number).
从上述定义来看，hash表完成的主要功能是查找。
举例说明：
假设某人爱好音乐，有N张CD。为了管理这些CD。此人设计了一个软件。该软件用HT实现查找，存储形式为数组array[N]。此人输入“SHE”，想得到的是和SHE相关的专辑放在什么位置，比如“第三层抽屉第一个CD包”
这里，关键字key是“SHE”，和关键字相关的value是“第三层抽屉第一个CD包”
假设使用的hash函数为Fhash。
（1）Fhash(SHE)=1011 ；hash函数将key变换成一个值，通常是一个数字串
（2）1011对应的数组位置为array[10]，；确定了数字串的存储位置，完成了地址的定位。
（3）程序将array[10]中的结果返回。查找结束。
在DHT里面，某个nodeQ(0010)节点（上面的应用程序）查找“SHE”，和SHE相关的专辑放在什么位置（哪个机器上nodeP(?)）？也就是查询返回的value应该是“nodeX有SHE”
假设nodeQ的路由表只有以下3项。
nodeF1 <-> (0011)
nodeF2 <-> (0111)
nodeF3 <-> (1010)
nodeF3的路由表由以下两项
nodeF4 <-> (1011)
nodeF5 <-> (1100)
nodeF4上面存的信息是“node1（192.168.10.1）和node2（192.168.44.8）存有SHE”
注意。NodeF4并不等价于node1或者node2。它可能是其中某一个节点，也可能不是。
（1）Fhash(SHE)=1011 ；hash函数将key变换成一个值，通常是一个数字串
（2）nodeQ并不知道1011对应哪个节点。它按照距离最近的原则，将查询分组requestSHE（1011）发送给nodeF3
（3）nodeF3收到requestSHE（1011）后，查找自己的路由表，发现nodeF4的ID为1011，将查询分组转发给nodeF4
（4）nodeF4收到requestSHE（1011）后，查找自己的缓冲区（或者硬盘…），将“node1（192.168.10.1）和node2（192.168.44.8）存有SHE”作为reply发送给nodeQ。
（5）nodeQ收到reply，得到想要查找的信息，查找完成。
对比两个查找过程。
HT: Fhash(SHE)->1011 ->a[10] ->“第三层抽屉第一个CD包”
DHT:Fhash(SHE)->1011->nodeF3 ->nodeF4 ->“node1（192.168.10.1）和node2（192.168.44.8）”
从上面的过程可以看到，Hash或者DHT提供的接口都是输入一个关键字，给出关键字对应的value，这个Value就是存储在DHT中的HT或者DHT用户（这个用户可能只是一个应用程序）所关心的信息。
那么，为什么节点nodeQ没有ID（1011）对应的节点IP地址呢？
从查找效率上来说，如果nodeQ具有所有在线的节点的IP地址和节点ID的映射，每次查找都只需要一步就能完成。不需要其他节点转发查询消息。效率最高。但是，这在动态变化的DHT中是不可能做到的。因为存储那么多节点ID和IP的映射需要存储开销，更重要的是，要维护路由表的正确性，需要大量的通信开销。这是任何节点和链路都无法承受的。所以，每个节点都只能维护一部分路由表。至于节点选择维护多大一部分（how much），选择维护哪一部分（which），不同的DHT协议有不同的见解，基本上是在DHT网络的通信开销和查询效率上折中。
那么，回到上次讨论的问题，路由表是不是hash表的一部分呢？
我自己的见解是，这个问题本身是不合适的。如果狭义的将hash表理解为就是静态的数组array[N]的地址，以及array[N]中所存的内容。那么路由表显然不是hash表。HT中Array[x]的地址是节点对应的ID，或者说，是Fhash(nodeX)所得到的值。array[x]中的下标x，对应的是节点的IP地址。而array[x]中保存的内容，是nodeX中保存的内容（或者是一部分内容）。
但是，我所理解的HT，是一种完整的算法，包括查询在内。而DHT，则是这种算法的分布式实现。
所以，路由表是完成DHT查找功能的重要的一部分。是hash算法的分布式实现的重要的一部分。