调用哈希表的Javascript实现中的链接列表中的方法

Question

我正在使用Javascript创建哈希表以更好地理解数据结构。我在每个表格位置使用链接列表来实现它来处理冲突。

问题是我不能在this.storage [index]上调用.add，因为它是未定义的。当我登录this.storage [index]我看到我的头节点在我的链表和我需要的方法。所以我不确定问题是什么。

var Node = function(key, value) { 
 
    this.key = key; 
 
    this.value = value; 
 
    this.next = null; 
 
}; 
 

 
var LinkedList = function() { 
 
    this.head = new Node('head'); 
 
    this.add = function(key, value) { 
 
    var node = new Node(key, value); 
 
    var curNode = this.head; 
 
    while (curNode.next !== null) { 
 
     curNode = curNode.next; 
 
    } 
 
    curNode.next = node; 
 
    }; 
 
    this.find = function(key) { 
 
    var curNode = this.head; 
 
    while (curNode.key !== key && curNode.next !== null) { 
 
     curNode = curNode.next; 
 
    } 
 
    return curNode.value; 
 
    }; 
 
}; 
 

 
var HashTable = function(max) { 
 
    this.max = max; 
 
    this.storage = []; 
 
    for (var i = 0; i < max; ++i) { 
 
    this.storage[i] = new LinkedList(); 
 
    } 
 
    this.hash = function(key) { 
 
    var sum = 0; 
 
    for (var i = 0; i < key.length; ++i) { 
 
     sum += key[i].charCodeAt() - 97; 
 
    } 
 
    return sum % this.max; 
 
    }; 
 
    this.addValue = function(key, value) { 
 
    var index = this.hash(key); 
 
    this.storage[index].add(key, value); 
 
    }; 
 
    this.getValue = function(key) { 
 
    var index = this.hash(key); 
 
    return this.storage[index].find(key); 
 
    }; 
 
}; 
 

 
var hash = new HashTable(5); 
 
hash.addValue("I"); 
 
hash.addValue("would"); 
 
hash.addValue("like"); 
 
hash.addValue("coffee"); 
 
hash.getValue('I');

Answer 1

JavaScript的模运算不工作，你可能会想到为负数。如果sum是-4，sum % max不是max - 4，则它是-4。然后你尝试添加到this.storage[-4]，这是未定义的。您需要检查并调整。

var Node = function(key, value) { 
 
    this.key = key; 
 
    this.value = value; 
 
    this.next = null; 
 
}; 
 

 
var LinkedList = function() { 
 
    this.head = new Node('head'); 
 
    this.add = function(key, value) { 
 
    var node = new Node(key, value); 
 
    var curNode = this.head; 
 
    while (curNode.next !== null) { 
 
     curNode = curNode.next; 
 
    } 
 
    curNode.next = node; 
 
    }; 
 
    this.find = function(key) { 
 
    var curNode = this.head; 
 
    while (curNode.key !== key && curNode.next !== null) { 
 
     curNode = curNode.next; 
 
    } 
 
    return curNode.value; 
 
    }; 
 
}; 
 

 
var HashTable = function(max) { 
 
    this.max = max; 
 
    this.storage = []; 
 
    for (var i = 0; i < max; ++i) { 
 
    this.storage[i] = new LinkedList(); 
 
    } 
 
    this.hash = function(key) { 
 
    var sum = 0; 
 
    for (var i = 0; i < key.length; ++i) { 
 
     sum += key[i].charCodeAt() - 97; 
 
    } 
 
    sum = sum % this.max; 
 
    if (sum < 0) { 
 
     sum = this.max + sum; 
 
    } 
 
    return sum; 
 
    }; 
 
    this.addValue = function(key, value) { 
 
    var index = this.hash(key); 
 
    this.storage[index].add(key, value); 
 
    }; 
 
    this.getValue = function(key) { 
 
    var index = this.hash(key); 
 
    return this.storage[index].find(key); 
 
    }; 
 
}; 
 

 
var hash = new HashTable(5); 
 
hash.addValue("I"); 
 
hash.addValue("would"); 
 
hash.addValue("like"); 
 
hash.addValue("coffee"); 
 
hash.getValue('I'); 
 
console.log(hash);