带注释_合工大数据结构课设Chord网络的模拟（90分）

有些代码来自GitHub，词典文件为盗版，仅用于学习，禁止传播

Chord网络模拟(90分)

(1)问题描述

Chord很经典P2P结构化网络，可在Chord上分布式P2P文件共享等应用。Chord网络的基本结构如图6-59所示，是一种基于分布式散列表的逻辑网络。

分布式散列表（DHT）它实际上是一个由大量结点分布式共同维护的巨大散列表。散列表分为不连续块，每个结点分配给自己的散列块（散列值范围），并成为散列块的经理，负责存储散列结果中的信息。DHT散列函数通常是加密散列函数(如MD5，SHA-通过这些函数，一个对象的名称(如节点)ID或其IP地址)或关键字(如文件名)被映射为128或160个散列，如SHA-1（“202.38.64.1”）=24b92cb1d2b81a47472a93d06af3d85a42e463ea。一个采用DHT在系统中，所有计算结点和数据对象都被映射到一个空间中。一个采用DHT在系统中，所有计算结点和数据对象都被映射到一个空间中。图6-59中Chord结构，每个计算节点根据其IP它可以计算出来ID，如图中的N14。

每个文件可以根据其关键字计算每个信息ID，就是图中的K，如图中的K=hash（key）=54，这些K被放在Chord环中机器节点ID大于K且最近的K节点，如图所示K=54的信息放在ID=56的节点N56上，将K=30和K=24的信息放在ID=32的节点N32上。

Chord结构主要支持以下操作：①Insert（key,V），即将关键词key存储在节点中的相应信息VID大于K=hash（key）而且在离K最近的节点上，这样ID可用Successor（K）表示，其中Successor（K）是最接近K的节点，从K开始顺时针。②Lookup（K），根据K查询相应的V，主要表现为基础Chord中间节点的连接(上图中的节点间连接)路由到存储K的节点，即节点ID=Successor（K）K对应的节点可以在节点上找到V。③Update（K,new_V）：根据K更新相应的V。④Join（NID）：添加新节点，NID它是节点的标志，如节点IP地址，在Chord添加节点需要建立相应的连接和移动信息数据，如上图所示N26，则需要将K=24移动到节点。⑤Leave():节点主动离开Chord，在Chord需要修改相应的连接，并移动一些信息数据，如上图所示N14，则需要将K=10移动到节点N21。

Chord如果每个节点只维护后继节点，结构的一个非常重要的特点是ID、IP地址和其他信息，查询信息通过后续节点指针在环上传输，直到查询信息中包含的K落在节点ID以及它的后继节点ID之间，这询速度太慢O（N），N如图6-60所示，网络中的节点数（a）所示。因此在基本Chord上面介绍了一些可以加快查询的东西finger表，finger如图6-60所示（b）表示，节点为ID的finger所有的都存放在表中（ID 2i）modN?IDi从1开始，逐个增加1ID=Successor（ID 2i）每个i对应的节点finger表中的1项。有了finger表后，可以加速查询过程，对于路由中的任何一个节点ID，节点选择的路由下跳是finger表中满足（ID 2i）modN小于等于K且最接近K的i对应表项，可以从此表项中找到查询的下一个跳跃，如图6-60所示（c）所示。

仔细分析可以发现引入finger表后，查询K的路由跳数为O（logN），相比O（N）有很大的进步。

(2)课程设计目的

建立对Chord对结构的理解可以通过数据结构知识来完成Chord模拟结构。

(3)基本要求

①设计和实现数据结构知识Chord网络结构。

②实现Chord结构上的Insert、Lookup、Update、Leave、Join五个操作。

③构建一个Chord如果可以定义单机模拟应用程序，数据信息可以自己定义key英语单词一个接一个，相应的数据用英语解释。

④每个操作的结果都特别是模拟Lookup路由过程和模拟过程应可视化，即节点连接、路由跳跃过程、鼓励使用VC实现。

⑤实验结果分析验证验证finger表后，查询K的路由跳数为O（logN）理论结果。

(4)实现提示

可以查阅P2P中关于Chord现有的散列函数可以直接用于数据，如SHA-使用散列函数的源代码可直接下载。

代码：

头文件：

Chord.h

#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <vector>

using namespace std;

class Node;

class FingerTable {
public:
	vector<Node*> fingerTable;
	Node* local_node;
	int nodeId;

	FingerTable(int id, Node* node) {
		this->nodeId = id;
		this->local_node = node;
	}

	~FingerTable() {
		this->nodeId = -99;
		this->fingerTable.clear();
	}

	void printFingerTable();
};

class Node {

public:
	uint64_t id;
	Node* predecessor;
	std::map<int, int> local_keys;
	FingerTable *fingertable;

	Node(int id) {
		this->id = (int) id;
		this->predecessor = NULL;
		this->fingertable = new FingerTable(this->id, this);
	}

	~Node() {
		this->id = INT64_MIN;
		(this->local_keys).clear();
	}

	// Move keys (if any) to the newly added node
	void moveKeys(Node* succ, int new_node_id) {
		map<int, int> m;
		map<int, int>::iterator iter;

		for (map<int, int>::iterator iter = succ->local_keys.begin();
				iter != succ->local_keys.end(); iter++) {
			if (iter->first <= new_node_id
					&& iter->first > succ->predecessor->id) {
				insert_key_local(iter->first, iter->second);
			} else {
				m.insert(pair<int, int>(iter->first, iter->second));
			}
		}

		succ->local_keys.clear();
		succ->local_keys = m;
	}

	// Node join operation
	void Join(Node* node) {
		if (node == NULL) {  // First node to join
			for (int i = 0; i < 8; i++) {
				fingertable->fingerTable.push_back(this);
			}
			predecessor = this;
		} else {
			for (int i = 0; i < 8; i++) {
				fingertable->fingerTable.push_back(this);
			}

			// Find successor to attach to
			Node* succ = node->find_successor(id);

			// Update node's successor to point to the successor
			fingertable->fingerTable[0] = succ;

			// Update predecessor's successor to self
			succ->predecessor->fingertable->fingerTable[0] = this;

			// Update predecessor to successor's old predecessor
			predecessor = succ->predecessor;

			// move keys on the successor before changing predecessor
			moveKeys(succ, id);

			// Update successor's predecssor to self
			succ->predecessor = this;

			// update finger table
			// fingerTable[0] is always the successor
			createFingerTable();
		}
	}

	// creates the finger table
	void createFingerTable() {
		for (int i = 1; i < fingertable->fingerTable.size(); i++) {
			Node* ptr = this;
			int flag = 0;

			for (int j = 0; j < pow(2, i); j++) {
				ptr = ptr->fingertable->fingerTable[0];

				if (ptr == this) {
					flag = 1;
					break;
				}
			}

			if (flag == 0) {
				fingertable->fingerTable[i] = ptr;
			}
		}
	}

	// stabilize the finger tables
	void stabilize() {
		for (int i = 1; i < fingertable->fingerTable.size(); i++) {
			fingertable->fingerTable[i]->createFingerTable();
		}
	}

	// Find Successor
	Node* find_successor(int id) {
		if (this->id == id) {
			return this;
		}
		else if (this->id > id) {
			return this;
		}
		else if(this->id < id && this->fingertable->fingerTable[0]->id <= this->id) {
			return this->fingertable->fingerTable[0];
		}
		else {
			return fingertable->fingerTable[0]->find_successor(id);
		}
	}

	// Search a key value pair
	string LookUp(int key) {
		int node_id = 0;
		string ret_val;

		cout << "\n Searching Key " << key << " on node " << id << endl;
		node_id = local_key_lookup(key);
		if (node_id >= 0) {
			ret_val = " Found value - " + to_string(node_id) + " on Node - "
					+ to_string(id) + "\n";
		} else {
			for (int i = 0; i < fingertable->fingerTable.size(); i++) {
				node_id = fingertable->fingerTable[i]->local_key_lookup(key);
				if (node_id >= 0) {
					ret_val =  " Found value - " + to_string(node_id) + " on Node - "
							+ to_string(fingertable->fingerTable[i]->id) + "\n";
					break;
				}
				else {
					cout << "Found None" << endl;
				}
			}
		}

		return ret_val;
	}

	// Insert key
	void Insert(int key, int value) {
		if (key < 0) {
			cerr << "\n *** Error Key is less than 0 *** \n";
			return;
		}

		Node* succ = this->fingertable->fingerTable[0];

		if (succ->id <= id && id <= key) {
			succ->insert_key_local(key, value);
		}
		else if (predecessor->id > id && key > predecessor->id) {
			insert_key_local(key, value);
		}
		else {
			while (succ->id < key) {
				succ = succ->fingertable->fingerTable[0];
			}
			succ->insert_key_local(key, value);
		}
	}

	// Insert a key on this node
	void insert_key_local(int key, int value) {
		if (!key) {
			cout << "No key provided to insert_key!" << endl;
		}

		local_keys.insert(pair<int, int>(key, value));
	}

	// Search a key locally
	int local_key_lookup(int key) {
		cout << " Node " << this->id << " searched" << endl;
		int node = -1;

		for (int i = 0; i < local_keys.size(); i++) {
			if (local_keys.find(key)->first == key) {
				node =  local_keys.find(key)->second;
			}
		}

		return node;
	}

	// Leave the chord ring and automatically move the info on it
	void Leave() {
		Node* succ = this->fingertable->fingerTable[0];
		Node* pred = this->predecessor;
		
		// Connect the predecessor's successor to this's successor
		pred->fingertable->fingerTable[0] = succ;
		// Connect the successor's predecessor to this's predecessor
		succ->predecessor = pred;
		// Rest of the nodes recreating the Finger Table
		succ->createFingerTable();
		pred->createFingerTable();

		// // Insert the value to the rest nodes
		for (map<int, int>::iterator iter = this->local_keys.begin(); iter != this->local_keys.end(); iter++) {
			succ->Insert(iter->first, iter->second);
		}

	}
};

// Print Finger Table
void FingerTable::printFingerTable() {
	cout << "\n**** Node ID : " << this->nodeId << " ****";
	cout << "\nFingerTable\n";

	for (int i = 0; i < fingerTable.size(); i++) {
		if (i == 0 || (nodeId != fingerTable[i]->fingertable->nodeId)) {
			cout << i + 1 << " : " << fingerTable[i]->fingertable->nodeId
					<< "\n";
		}
	}

	cout << "\nKeys : ";
	for (map<int, int>::iterator iter = local_node->local_keys.begin();
			iter != local_node->local_keys.end(); iter++) {
		cout << iter->second << "  ";
	}

	cout << "\n**********************\n";
}

Chord_sha1.h

#include <bits/stdc++.h>
using namespace std;

class Node;

//Fingertable
//Fingertable表的[0]位永远为该结点后继
class FingerTable {
public:
	vector<Node*> fingerTable;//fingertable
	Node* local_node;//当前结点
	string nodeId;//当前结点的id

	FingerTable(string id, Node* node) {
		this->nodeId = id;
		this->local_node = node;
	}

	~FingerTable() {
		this->nodeId = "NULL";
		this->fingerTable.clear();
	}

	//打印当前结点的fingertable以及key值
	void printFingerTable();

	//打印当前结点的fingertable
	void printFingerTableWithoutKey();
};

//Node
class Node {

public:
	string id;//此节点的id
	Node* predecessor;//此节点的前驱
	std::map<string, string> local_keys;//此节点存储的所有key值
	FingerTable *fingertable;//此节点的fingertable（注意同样是个类）

	Node(string id) {
		this->id = id;
		this->predecessor = NULL;
		this->fingertable = new FingerTable(this->id, this);
	}

	~Node() {
		this->id = "NULL";
		(this->local_keys).clear();
	}

	//加入node
	void Join(Node* node) {
		if (node == NULL) {  //第一个node
			for (int i = 0; i < 8; i++) {
				fingertable->fingerTable.push_back(this);
			}
			predecessor = this;
		} else {
			for (int i = 0; i < 8; i++) {
				fingertable->fingerTable.push_back(this);
			}

			//找到后继，即插入位置
			Node* succ = node->find_successor(id);

			//调整位置关系
			fingertable->fingerTable[0] = succ;
			succ->predecessor->fingertable->fingerTable[0] = this;
			predecessor = succ->predecessor;

			//调整key
			moveKeys(succ, id);

			//更新后继的前驱为此节点
			succ->predecessor = this;

			//更新fingertable
			createFingerTable();
		}
	}

	//更新fingertable
	void stabilize() {
		for (int i = 1; i < fingertable->fingerTable.size(); i++) {
			fingertable->fingerTable[i]->createFingerTable();
		}
	}

	//寻找
	string LookUp(string key) {
		string value = "NULL";//存储寻找到的值
		string ret_val;//返回值

		cout << "Searching Key " << key << " on node " << id << endl;
		value = local_key_lookup(key);//当前节点搜寻
		if (value != "NULL") {
			ret_val = "Found value: " + value + " on Node: " + id + "\n";
		}
		//若未找到
		else {
			Node *t = this;
			bool b = false;
			//外层i循环作用为规定最大循环次数防止出现找不到的情况
			for (int i = 0; i < 100; i++) {
				b = false;
				int j;
				//j循环作用为在当前结点的fingertable中寻找目标id
				for(j = 0; j < t->fingertable->fingerTable.size(); j++) {
					//当前结点的fingertable中某节点的id大于了寻找的id
					if(t->fingertable->fingerTable[j]->id >= key) {
						//若找到的是后继，则寻找id在当前结点的前面，所以更新结点为其前驱
						if(j == 0) {
							t = t->predecessor;
						}
						//若id不在当前结点前，即找到了,更新当前结点为fingertable中寻找到的结点的前一位
						else {
							t = t->fingertable->fingerTable[j - 1];
							b = true;//标记找到
							break;
						}
					}

					//防止数组越界
					//写的什么shi
					if(j < 8) {
						//fingertable中当前结点已找完（fingertable未满情况）
						if(t->fingertable->fingerTable[j]->id == t->fingertable->fingerTable[j + 1]->id) {
							break;
						}
					}
				}

				//若在当前结点的fingertable中未找到，则当前结点变为fingertable中的最后一个
				if(!b) {
					t = t->fingertable->fingerTable[j - 2];
				}

				// t->fingertable->printFingerTableWithoutKey();
				
				//不论是否找到，都在当前结点中搜寻
				value = t->fingertable->fingerTable[0]->local_key_lookup(key);
				
				//若找到
				if (value != "NULL") {
					ret_val =  "Found value: " + value + " on Node: " + t->fingertable->fingerTable[0]->id + "\n";
					break;
				}
				//若为找到
				else {
					cout << "Found None" << endl;
					// t = t->fingertable->fingerTable[0];

					//如果未找到且当前节点后继大于key，即后继再也没有此值了
					if(t->fingertable->fingerTable[0]->id > key) {
						ret_val =  "Can't Find\n";
						break;
					}
				}

			}
		}

		return ret_val;
	}

	//插入值
	void Insert(string key, string value) {
		//首先找到后继结点，用于判断以下的不同插入情况
		Node* succ = this->fingertable->fingerTable[0];

		//若插入结点（后继结点）小于当前结点且当前结点小于key，即当前结点在环的最后一位且key大于当前结点
		if (succ->id <= id && id <= key) {
			//则插入到环的第一位
			succ->insert_key_local(key, value);
		}
		//若当前结点的前驱大于当前结点且key大于前驱，即当前结点在环的第一位且key大于前驱
		else if (predecessor->id > id && key > predecessor->id) {
			//则插入到当前结点
			insert_key_local(key, value);
		}


//		上面两个好像一样，但是我不想删了因为程序已经能跑了
//		我也忘了为什么要这样写，可能删了会有bug
//		反正我是写unity c#的，c++我也学不透，说实话这个实验的代码挺烂
//		实验验收这块代码略过就行
//		有人cv的话记得在实验前把这块删一下，顺便点个赞和收藏（づ￣3￣）づ  ～～～❤
//
//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//                            _ooOoo_
//                           o8888888o
//                           88" . "88
//                           (| -_- |)
//                           O\  =  /O
//                        ____/`---'\____
//                      .'  \\|     |//  `.
//                     /  \\|||  :  |||//  \
//                    /  _||||| -:- |||||-  \
//                    |   | \\\  -  /// |   |
//                    | \_|  ''\---/''  |   |
//                    \  .-\__  `-`  ___/-. /
//                  ___`. .'  /--.--\  `. . __
//               ."" '<  `.___\_<|>_/___.'  >'"".
//              | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//              \  \ `-.   \_ __\ /__ _/   .-` /  /
//         ======`-.____`-.___\_____/___.-`____.-'======
//                        
//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

		//不在环的边界情况下时
		else {
			//若后继结点小于key时，应继续寻找
			while (succ->id < key) {
				//后继结点向后移动
				succ = succ->fingertable->fingerTable[0];
			}
			//最后找到则插入
			succ->insert_key_local(key, value);
		}
	}

	//退出结点
	void Leave(string id) {
		find_successor(id)->_Leave();//寻找目标结点并退出
		stabilize();//退出后自动更新结点的fingertable
	}

private: 

	//移动Keys到新加入的node上
	void moveKeys(Node* succ, string new_node_id) {
		map<string, string> m;
		map<string, string>::iterator iter;

		for (map<string, string>::iterator iter = succ->local_keys.begin(); iter != succ->local_keys.end(); iter++) {
			if (iter->first <= new_node_id && iter->first > succ->predecessor->id) {
				insert_key_local(iter->first, iter->second);
			} else {
				m.insert(pair<string, string>(iter->first, iter->second));
			}
		}

		succ->local_keys.clear();
		succ->local_keys = m;
	}

	//创建fingertable
	void createFingerTable() {
		for (int i = 1; i < fingertable->fingerTable.size(); i++) {
			Node* ptr = this;
			int flag = 0;

			for (int j = 0; j < pow(2, i); j++) {
				ptr = ptr->fingertable->fingerTable[0];

				if (ptr == this) {
					flag = 1;
					break;
				}
			}

			if (flag == 0) {
				fingertable->fingerTable[i] = ptr;
			}
		}
	}

	//寻找某id的后继结点
	Node* find_successor(string id) {
		if (this->id == id) {
			return this;
		}
		else if (this->id > id) {
			return this;
		}
		else if(this->id < id && this->fingertable->fingerTable[0]->id <= this->id) {
			return this->fingertable->fingerTable[0];
		}
		else {
			return fingertable->fingerTable[0]->find_successor(id);
		}
	}

	//在当前结点中插入值
	void insert_key_local(string key, string value) {

		if (key == "NULL") {
			cout << "No key provided to insert_key!" << endl;
		}

		local_keys.insert(pair<string, string>(key, value));
	}

	//在当前结点的key中搜寻目标key
	string local_key_lookup(string key) {
		cout << "Node " << this->id << " searched" << endl;
		string value = "NULL";

		for (int i = 0; i < local_keys.size(); i++) {
			if(local_keys.find(key)->first == key) {
				value = local_keys.find(key)->second;
			}
		}

		return value;
	}

	//结点退出代码（内部的）
	void _Leave() {
		//先保存删除结点的前驱后继
		Node* succ = this->fingertable->fingerTable[0];
		Node* pred = this->predecessor;
		
		//连接前驱和后继
		pred->fingertable->fingerTable[0] = succ;
		succ->predecessor = pred;
		//前驱和后继这两个结点重新建立fingertable
		succ->createFingerTable();
		pred->createFingerTable();

		//将删除结点上的key和value插入到别的结点上
		for (map<string, string>::iterator iter = this->local_keys.begin(); iter != this->local_keys.end(); iter++) {
			succ->Insert(iter->first, iter->second);
		}
	
	}
};

//打印当前结点的fingertable以及key值
void FingerTable::printFingerTable() {
	cout << "**** Node ID : " << this->nodeId << " ****" << endl;
	cout << "FingerTable" << endl;

	for (int i = 0; i < fingerTable.size(); i++) {
		if (i == 0 || (nodeId != fingerTable[i]->fingertable->nodeId)) {
			cout << i + 1 << " : " << fingerTable[i]->fingertable->nodeId << endl;
		}
	}
	cout << "Keys: " << endl;
	for (map<string, string>::iterator iter = local_node->local_keys.begin(); iter != local_node->local_keys.end(); iter++) {
		cout << iter->first << endl;
	}

	cout << "**********************" << endl;
}

//打印当前结点的fingertable
void FingerTable::printFingerTableWithoutKey() {
	cout << "**** Node ID : " << this->nodeId << " ****" << endl;
	cout << "FingerTable" << endl;

	for (int i = 0; i < fingerTable.size(); i++) {
		if (i == 0 || (nodeId != fingerTable[i]->fingertable->nodeId)) {
			cout << i + 1 << " : " << fingerTable[i]->fingertable->nodeId << endl;
		}
	}

	cout << "**********************" << endl;
}

sha1.hpp

/*
    sha1.hpp - source code of

    ============
    SHA-1 in C++
    ============

    100% Public Domain.

    Original C Code
        -- Steve Reid <steve@edmweb.com>
    Small changes to fit into bglibs
        -- Bruce Guenter <bruce@untroubled.org>
    Translation to simpler C++ Code
        -- Volker Diels-Grabsch <v@njh.eu>
    Safety fixes
        -- Eugene Hopkinson <slowriot at voxelstorm dot com>
    Header-only library
        -- Zlatko Michailov <zlatko@michailov.org>
*/

#ifndef SHA1_HPP
#define SHA1_HPP


#include <cstdint>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>


class SHA1
{
public:
    SHA1();
    void update(const std::string &s);
    void update(std::istream &is);
    std::string final();
    static std::string from_file(const std::string &filename);

private:
    uint32_t digest[5];
    std::string buffer;
    uint64_t transforms;
};


static const size_t BLOCK_INTS = 16;  /* number of 32bit integers per SHA1 block */
static const size_t BLOCK_BYTES = BLOCK_INTS * 4;


inline static void reset(uint32_t digest[], std::string &buffer, uint64_t &transforms)
{
    /* SHA1 initialization constants */
    digest[0] = 0x67452301;
    digest[1] = 0xefcdab89;
    digest[2] = 0x98badcfe;
    digest[3] = 0x10325476;
    digest[4] = 0xc3d2e1f0;

    /* Reset counters */
    buffer = "";
    transforms = 0;
}


inline static uint32_t rol(const uint32_t value, const size_t bits)
{
    return (value << bits) | (value >> (32 - bits));
}


inline static uint32_t blk(const uint32_t block[BLOCK_INTS], const size_t i)
{
    return rol(block[(i+13)&15] ^ block[(i+8)&15] ^ block[(i+2)&15] ^ block[i], 1);
}


/*
 * (R0+R1), R2, R3, R4 are the different operations used in SHA1
 */

inline static void R0(const uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
    z += ((w&(x^y))^y) + block[i] + 0x5a827999 + rol(v, 5);
    w = rol(w, 30);
}


inline static void R1(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
    block[i] = blk(block, i);
    z += ((w&(x^y))^y) + block[i] + 0x5a827999 + rol(v, 5);
    w = rol(w, 30);
}


inline static void R2(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
    block[i] = blk(block, i);
    z += (w^x^y) + block[i] + 0x6ed9eba1 + rol(v, 5);
    w = rol(w, 30);
}


inline static void R3(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
    block[i] = blk(block, i);
    z += (((w|x)&y)|(w&x)) + block[i] + 0x8f1bbcdc + rol(v, 5);
    w = rol(w, 30);
}


inline static void R4(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
    block[i] = blk(block, i);
    z += (w^x^y) + block[i] + 0xca62c1d6 + rol(v, 5);
    w = rol(w, 30);
}


/*
 * Hash a single 512-bit block. This is the core of the algorithm.
 */

inline static void transform(uint32_t digest[], uint32_t block[BLOCK_INTS], uint64_t &transforms)
{
    /* Copy digest[] to working vars */
    uint32_t a = digest[0];
    uint32_t b = digest[1];
    uint32_t c = digest[2];
    uint32_t d = digest[3];
    uint32_t e = digest[4];

    /* 4 rounds of 20 operations each. Loop unrolled. */
    R0(block, a, b, c, d, e,  0);
    R0(block, e, a, b, c, d,  1);
    R0(block, d, e, a, b, c,  2);
    R0(block, c, d, e, a, b,  3);
    R0(block, b, c, d, e, a,  4);
    R0(block, a, b, c, d, e,  5);
    R0(block, e, a, b, c, d,  6);
    R0(block, d, e, a, b, c,  7);
    R0(block, c, d, e, a, b,  8);
    R0(block, b, c, d, e, a,  9);
    R0(block, a, b, c, d, e, 10);
    R0(block, e, a, b, c, d, 11);
    R0(block, d, e, a, b, c, 12);
    R0(block, c, d, e, a, b, 13);
    R0(block, b, c, d, e, a, 14);
    R0(block, a, b, c, d, e, 15);
    R1(block, e, a, b, c, d,  0);
    R1(block, d, e, a, b, c,  1);
    R1(block, c, d, e, a, b,  2);
    R1(block, b, c, d, e, a,  3);
    R2(block, a, b, c, d, e,  4);
    R2(block, e, a, b, c, d,  5);
    R2(block, d, e, a, b, c,  6);
    R2(block, c, d, e, a, b,  7);
    R2(block, b, c, d, e, a,  8);
    R2(block, a, b, c, d, e,  9);
    R2(block, e, a, b, c, d, 10);
    R2(block, d, e, a, b, c, 11);
    R2(block, c, d, e, a, b, 12);
    R2(block, b, c, d, e, a, 13);
    R2(block, a, b, c, d, e, 14);
    R2(block, e, a, b, c, d, 15);
    R2(block, d, e, a, b, c,  0);
    R2(block, c, d, e, a, b,  1);
    R2(block, b, c, d, e, a,  2);
    R2(block, a, b, c, d, e,  3);
    R2(block, e, a, b, c, d,  4);
    R2(block, d, e, a, b, c,  5);
    R2(block, c, d, e, a, b,  6);
    R2(block, b, c, d, e, a,  7);
    R3(block, a, b, c, d, e,  8);
    R3(block, e, a, b, c, d,  9);
    R3(block, d, e, a, b, c, 10);
    R3(block, c, d, e, a, b, 11);
    R3(block, b, c, d, e, a, 12);
    R3(block, a, b, c, d, e, 13);
    R3(block, e, a, b, c, d, 14);
    R3(block, d, e, a, b, c, 15);
    R3(block, c, d, e, a, b,  0);
    R3(block, b, c, d, e, a,  1);
    R3(block, a, b, c, d, e,  2);
    R3(block, e, a, b, c, d,  3);
    R3(block, d, e, a, b, c,  4);
    R3(block, c, d, e, a, b,  5);
    R3(block, b, c, d, e, a,  6);
    R3(block, a, b, c, d, e,  7);
    R3(block, e, a, b, c, d,  8);
    R3(block, d, e, a, b, c,  9);
    R3(block, c, d, e, a, b, 10);
    R3(block, b, c, d, e, a, 11);
    R4(block, a, b, c, d, e, 12);
    R4(block, e, a, b, c, d, 13);
    R4(block, d, e, a, b, c, 14);
    R4(block, c, d, e, a, b, 15);
    R4(block, b, c, d, e, a,  0);
    R4(block, a, b, c, d, e,  1);
    R4(block, e, a, b, c, d,  2);
    R4(block, d, e, a, b, c,  3);
    R4(block, c, d, e, a, b,  4);
    R4(block, b, c, d, e, a,  5);
    R4(block, a, b, c, d, e,  6);
    R4(block, e, a, b, c, d,  7);
    R4(block, d, e, a, b, c,  8);
    R4(block, c, d, e, a, b,  9);
    R4(block, b, c, d, e, a, 10);
    R4(block, a, b, c, d, e, 11);
    R4(block, e, a, b, c, d, 12);
    R4(block, d, e, a, b, c, 13);
    R4(block, c, d, e, a, b, 14);
    R4(block, b, c, d, e, a, 15);

    /* Add the working vars back into digest[] */
    digest[0] += a;
    digest[1] += b;
    digest[2] += c;
    digest[3] += d;
    digest[4] += e;

    /* Count the number of transformations */
    transforms++;
}


inline static void buffer_to_block(const std::string &buffer, uint32_t block[BLOCK_INTS])
{
    /* Convert the std::string (byte buffer) to a uint32_t array (MSB) */
    for (size_t i = 0; i < BLOCK_INTS; i++)
    {
        block[i] = (buffer[4*i+3] & 0xff)
                   | (buffer[4*i+2] & 0xff)<<8
                   | (buffer[4*i+1] & 0xff)<<16
                   | (buffer[4*i+0] & 0xff)<<24;
    }
}


inline SHA1::SHA1()
{
    reset(digest, buffer, transforms);
}


inline void SHA1::update(const std::string &s)
{
    std::istringstream is(s);
    update(is);
}


inline void SHA1::update(std::istream &is)
{
    while (true)
    {
        char sbuf[BLOCK_BYTES];
        is.read(sbuf, BLOCK_BYTES - buffer.size());
        buffer.append(sbuf, (std::size_t)is.gcount());
        if (buffer.size() != BLOCK_BYTES)
        {
            return;
        }
        uint32_t block[BLOCK_INTS];
        buffer_to_block(buffer, block);
        transform(digest, block, transforms);
        buffer.clear();
    }
}


/*
 * Add padding and return the message digest.
 */

inline std::string SHA1::final()
{
    /* Total number of hashed bits */
    uint64_t total_bits = (transforms*BLOCK_BYTES + buffer.size()) * 8;

    /* Padding */
    buffer += (char)0x80;
    size_t orig_size = buffer.size();
    while (buffer.size() < BLOCK_BYTES)
    {
        buffer += (char)0x00;
    }

    uint32_t block[BLOCK_INTS];
    buffer_to_block(buffer, block);

    if (orig_size > BLOCK_BYTES - 8)
    {
        transform(digest, block, transforms);
        for (size_t i = 0; i < BLOCK_INTS - 2; i++)
        {
            block[i] = 0;
        }
    }

    /* Append total_bits, split this uint64_t into two uint32_t */
    block[BLOCK_INTS - 1] = (uint32_t)total_bits;
    block[BLOCK_INTS - 2] = (uint32_t)(total_bits >> 32);
    transform(digest, block, transforms);

    /* Hex std::string */
    std::ostringstream result;
    for (size_t i = 0; i < sizeof(digest) / sizeof(digest[0]); i++)
    {
        result << std::hex << std::setfill('0') << std::setw(8);
        result << digest[i];
    }

    /* Reset for next run */
    reset(digest, buffer, transforms);

    return result.str();
}


inline std::string SHA1::from_file(const std::string &filename)
{
    std::ifstream stream(filename.c_str(), std::ios::binary);
    SHA1 checksum;
    checksum.update(stream);
    return checksum.final();
}


#endif /* SHA1_HPP */

dic.h

#include "Chord_sha1.h"
#include "sha1.hpp"
using namespace std;

static int MaxNum = 100;

// 使用字符分割
void Stringsplit(const string& str, const char split, vector<string>& res)
{
    // int i = 0;

	if (str == ""){
        return;
    }
    
	//在字符串末尾也加入分隔符，方便截取最后一段
	string strs = str + split;
	size_t pos = strs.find(split);
 
	// 若找不到内容则字符串搜索函数返回 npos
	while (pos != strs.npos)
	{
		string temp = strs.substr(0, pos);
		res.push_back(temp);
		//去掉已分割的字符串,在剩下的字符串中进行分割
		strs = strs.substr(pos + 1, strs.size());
		pos = strs.find(split);
	}
}

int Charge(Node *n0) {
    SHA1 sha1;
    
    ifstream srcFile("dic.txt", ios::in); //以文本模式打开dic.txt备读
    if (!srcFile) { //打开失败
        cout << "文件读取失败" << endl;
        return -1;
    }
    cout << "文件打开成功" << endl;
    
    int n;
    for(n = 1; n < MaxNum; n++) {
        sha1.update(to_string(n));
        Node *node = new Node(sha1.final());
        node->Join(n0);
    }
    Node *t = n0;
    int i = 0;
    for(i = 0; i < MaxNum; i++) {
        t->stabilize();
        t = t->fingertable->fingerTable[0];
    }
    cout << "结点加入成功" << endl;

    //存储
    string s1;
    vector<string> s2;
    while(getline(srcFile, s1, '\n')) {
        Stringsplit(s1, ' ', s2);
        sha1.update(s2[0]);
        string s = sha1.final();
        n0->Insert(s, s2[2]);
        // cout << s2[0] << endl;
        s2.clear();
    }

    return 0;
}

CPP文件：

展示用：Chord.cpp

#include "Chord_sha1.h"
#include "sha1.hpp"

int StopFun() {
    int i;
    while(1) {
        std::cout << "是否要退出？（1.退出/0.返回）" << std::endl;
        std::cin >> i;
        if(i == 1) {
            return 1;
        }
        else if(i == 0) {
            return 0;
        }
        else {
            std::cout << "输入错误！" << std::endl;
        }
    }
}

int main() {
    int index;
    int TotalNum = 1;
    bool tag = true;
    SHA1 sha1;
    // n0 join
	Node* n0 = new Node("0");	
	n0->Join(NULL);
	cout << "N0(0)结点初始化完成" << endl;
    while(tag) {
        system("CLS");
        cout << "********************************" << endl;
        cout << "*       1.插入Insert           *" << endl;
        cout << "*       2.查询Lookup           *" << endl;
        cout << "*       3.加入新结点Join       *" << endl;
        cout << "*       4.退出结点Leave        *" << endl;
        cout << "*       5.更新结点Update       *" << endl;
        cout << "*       6.打印结点信息         *" << endl;
        cout << "*      -1.退出                 *" << endl;
        cout << "********************************" << endl;
        cout << "请输入序号：" << endl;
        cin >> index;
        switch (index)
        {
        case 1:
            system("CLS");
            {
                cout << "输入插入数据的key：" << endl;
                string key;
                cin >> key;
                sha1.update(key);
                cout << "输入插入数据的信息：" << endl;
                string value;
                cin >> value;
                n0->Insert(sha1.final(), value);
                cout << "信息已插入" << endl;
            }
            system("pause");
            break;
        case 2:
            system("CLS");
            {
                cout << "输入查询数据的key：" << endl;
                string key;
                cin >> key;
                sha1.update(key);
                string s = sha1.final();
                cout << "对应Sha-1散列值为：" << s << endl;
                cout << n0->LookUp(s) << endl;
            }
            system("pause");
            break;
        case 3:
            system("CLS");
            {
                cout << "输入加入结点序号：" << endl;
                int n;
                cin >> n;
                sha1.update(to_string(n));
                string s = sha1.final();
                Node *node = new Node(s);
                node->Join(n0);
                // node->fingertable->printFingerTable();
                // node->stabilize();
                // node->fingertable->printFingerTable();
                cout << "新结点已加入" << endl;
                cout << "对应Sha-1散列值为：" << s << endl;
                TotalNum++;
            }
            system("pause");
            break;
        case 4:
            system("CLS");
            {
                cout << "输入退出结点序号：" << endl;
                int n;
                cin >> n;
                sha1.update(to_string(n));
                string s = sha1.final();
                n0->Leave(s);
                cout << "结点已退出" << endl;
                TotalNum--;
            }
            system("pause");
            break;
        case 5:
            system("CLS");
            {
                Node *t = n0;
                int i = 0;
                for(i = 0; i < TotalNum; i++) {
                    t->stabilize();
                    t = t->fingertable->fingerTable[0];
                }
            }
            system("pause");
            break;
        case 6:
            system("CLS");
            {
                Node *t = n0;
                int i = 0;
                for(i = 0; i < TotalNum; i++) {
                    t->fingertable->printFingerTable();
                    t = t->fingertable->fingerTable[0];
                }
            }
            system("pause");
            break;
        case -1:
            system("CLS");
            {
                int x = StopFun();
                if(x == 1) {
                    tag = false;
                    break;
                }
                else {
                    break;                
                }
            }
        default:
            cout << "请选择正确序号！" << endl;
            system("pause");
            break;
        }
    }
	system("pause");

	return 0;
}

英文词典：Dictionary.cpp

#include <bits/stdc++.h>
#include "dic.h"
using namespace std;

int StopFun() {
    int i;
    while(1) {
        std::cout << "是否要退出？（1.退出/0.返回）" << std::endl;
        std::cin >> i;
        if(i == 1) {
            return 1;
        }
        else if(i == 0) {
            return 0;
        }
        else {
            std::cout << "输入错误！" << std::endl;
        }
    }
}

int main() {
    int TotalNum = 100;
    int index;
    bool tag = true;
    SHA1 sha1;

    // n0 join
	Node* n0 = new Node("0");	
	n0->Join(NULL);
	cout << "N0(0)结点初始化完成" << endl;
    
    int n = Charge(n0);
    if(n == -1) {
        return 0;
    }
    system("pause");

    while(tag) {
        system("CLS");
        cout << "*************************" << endl;
        cout << "*       1.搜索          *" << endl;
        cout << "*       2.打印结点      *" << endl;
        cout << "*      -1.退出          *" << endl;
        cout << "**************************" << endl;
        cout << "请输入序号：" << endl;
        cin >> index;
        switch (index)
        {
        case 1:
            system("CLS");
            {
                string s;
                cout << "输入查询的单词：" << endl;
                cin >> s;
                sha1.update(s);
                cout << n0->LookUp(sha1.final()) << endl;
            }
            system("pause");
            break;
        case 2:
            system("CLS");
            {
                Node *t = n0;
                int i = 0;
                for(i = 0; i < TotalNum; i++) {
                    cout << i + 1 << endl;
                    t->fingertable->printFingerTableWithoutKey();
                    t = t->fingertable->fingerTable[0];
                }
            }
            system("pause");
            break;
        case -1:
            system("CLS");
            {
                int x = StopFun();
                if(x == 1) {
                    tag = false;
                    break;
                }
                else {
                    break;                
                }
            }   
        default:
            cout << "请选择正确序号！" << endl;
            system("pause");
            break;
        }
    }


    return 0;
}

词典文件：

链接：/s/12UapWwi2-jVDneO6HSrAtg  提取码：hell

可能仍有BUG

未实现VC可视化与验证实验结果