調用哈希表的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);