我正在尝试实现对等和弦算法。我制作了一个节点数组,每个节点都有一个手指表。我需要能够遍历每个手指表(这是一个哈希表)以找到键值应该去的地方。所以基本上我需要我的fingertable(哈希表)能够被迭代,这样我就可以找到它去哪个节点(它在一个数组中)。我想过将每个手指表(哈希表)放入一个数组列表中,但我无法让它工作。
这可能不是使和弦有效工作的正确方法。因此,如果有更简单的方法来完成这项工作,请告诉我。此外,这不需要是完整的和弦算法(需要添加和删除节点以及所有爵士乐)。只是一个非常基本的和弦版本。
package chord;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Hashtable;
import java.util.Random;
import java.util.Scanner;
public class Chord {
private int userIDSpaceB;
private int userNumberOfNodesN;
private int randomKeyID;
private int nodeStart;
private int[] nodes;
private Random randomKeyInt;
private int idSpace;
public int answer = 0;
/**
* Chord constructor
*
* @param idSpace
* - the space the user wants to use (B). 2^B
* @param numberOfNodes
* - the number of nodes the user wants to have
*/
public Chord(int idSpace, int numberOfNodes) {
this.userIDSpaceB = idSpace;
this.idSpace = idSpace;
this.userNumberOfNodesN = numberOfNodes;
generateNumbers();
}
/**
* Generates random numbers, assigns node list, creates fingers.
*/
public void generateNumbers() {
// Get int 2^B
userIDSpaceB = (int) Math.pow(2, userIDSpaceB);
System.out.println("B (Circular ID Space): " + userIDSpaceB);
System.out.println("Number of Nodes: " + userNumberOfNodesN);
// Create node array and makes sure there is no duplicates
nodes = new int[userNumberOfNodesN];
// This loops through and makes the appropriate amount of numbers to
// choose from
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 1; i < userIDSpaceB; i++) {
list.add(new Integer(i));
}
// This will shuffle the list then nodes will be assigned a number
Collections.shuffle(list);
for (int i = 0; i < nodes.length; i++) {
nodes[i] = list.get(i);
}
// Sorts nodes from least to greatest
Arrays.sort(nodes);
System.out.println("Nodes array: " + Arrays.toString(nodes));
// Get key value
randomKeyInt = new Random();
randomKeyID = randomKeyInt.nextInt(userIDSpaceB + 1) + 1;
System.out.println("Key ID: " + randomKeyID);
nodeStart = nodes[1];
System.out.println("Node Start: " + nodeStart);
// Create successor and predecessor hashtables
Hashtable<Integer, Integer> successor = new Hashtable<Integer, Integer>();
Hashtable<Integer, Integer> predecessor = new Hashtable<Integer, Integer>();
// Set this to 1 because you are trying to get the succesor.
// Onces j exceeds the length of the node array, set it back to zero
// because
// The last element in the node array has the successor of nodes[0]
System.out.println("\nSuccessors of Nodes:");
int j = 1;
for (int i = 0; i < nodes.length; i++) {
if (j > nodes.length - 1) {
j = 0;
}
successor.put(nodes[i], nodes[j]);
System.out.println("N" + nodes[i] + " successor is " + nodes[j] + ".");
j++;
}
// Set m to the last element of nodes array because that is
// nodes[0]'s
// predecessor
// After that first iteration, set m = 0 because that will fill all
// of
// the right predecessors
System.out.println("\nPredeccessors of Nodes:");
int m = nodes.length - 1;
for (int i = 0; i < nodes.length; i++) {
if (m > nodes.length - 1) {
m = 0;
}
predecessor.put(nodes[i], nodes[m]);
System.out.println("N" + nodes[i] + " predecessor is " + nodes[m] + ".");
m++;
}
////////// This is where I would create the arraylist of finger nodes////////////
// Create finger table for each node
for (int i = 0; i < nodes.length; i++) {
System.out.println("\n");
fingerTable(nodes[i]);
}
}
/**
* Creates finger table for a given node
*
* @param node
* - the node that a finger table will be created for
* @return
*/
public Hashtable<Integer, Integer> fingerTable(int node) {
int individualNode = node;
// Create finger table
Hashtable<Integer, Integer> fingerTable = new Hashtable<Integer, Integer>();
// This would create one single finger table
int[] finger = new int[idSpace];
for (int i = 0; i < finger.length; i++) {
int temp = (int) ((int) (individualNode) + Math.pow(2, i));
// If temp is greater than the userIdSpace you have to do
// temp - userIdSpace
// Ex: If finger = 68 but the max space is 64 (2^6) then you have to
// do 68 - 64 = 4 which is the correct finger.
// Then find the closest node to it
if (temp > userIDSpaceB) {
temp = temp - userIDSpaceB;
}
finger[i] = temp;
}
// T is your index keeper for finger array.
int t = 0;
for (int i = 0; t < finger.length;) {
// If finger is greater than last node, then it has to go to the
// first node.
if (finger[t] > nodes[nodes.length - 1]) {
fingerTable.put(finger[t], nodes[0]);
i = 0;
t++;
}
// If the finger array number is greater, then increment i for
// finger array
else if (finger[t] > nodes[i]) {
i++;
}
// If finger node is less than or equal to a the node then assign
// it.
else if (finger[t] <= nodes[i]) {
fingerTable.put(finger[t], nodes[i]);
i = 0;
t++;
}
}
// Prints finger table for each node.
System.out.println("Finger Table for node: N" + individualNode);
for (int i = 0; i < finger.length; i++) {
System.out.println("N" + individualNode + " + " + ((int) Math.pow(2, i)) + " = "
+ (int) ((int) (individualNode) + Math.pow(2, i)) + " Hashed Node = N"
+ fingerTable.get(finger[i]));
}
return fingerTable;
}
/**
* Runs app.
*
* @param args
* - not used
*/
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter a Circular ID Space (5 <= number <= 10)");
int userIDSpace = scan.nextInt();
System.out.println("Enter number of nodes to be in Chord system (5 <= number <= 15)");
int userNumberOfNodes = scan.nextInt();
scan.close();
new Chord(userIDSpace, userNumberOfNodes);
}
}