散列表碰撞处理、开链法、HashTable散列

散列表碰撞处理、开链法、HashTable散列

解决了散列函数的碰撞处理问题 .table = Array(137.betterHash = betterHash;函数 .showDistro = showDistro;显示散列表里的数据 .buildChains = buildChains;生成二维数组 .put = put; .get = get; // put for separate chaining
function put(key,data) {
var pos = this.betterHash(key);
var index = 0;
if (this.table[pos][index] == undefined) {
this.table[pos][index] = data;
}else {
while (this.table[pos][index] != undefined) {
++index;
}
this.table[pos][index] = data;
}
}

/散列函数/
function betterHash(string) {
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {
total += this.table.length-1;
}
return parseInt(total);
}

function showDistro() {
var n = 0;
for (var i = 0; i < this.table.length; ++i) {
if (this.table[i][n] != undefined) {
console.log(i + ": " + this.table[i]);
}
}
}

function buildChains() {
for (var i = 0; i < this.table.length; ++i) {
this.table[i] = new Array();
}
}

// get for separate chaining
function get(key) {
var index = 0;
var pos = this.betterHash(key);

</span><span style="color: #0000ff;"&gt;while</span> ((<span style="color: #0000ff;"&gt;this</span>.table[pos][index] != undefined)&amp;&amp;(<span style="color: #0000ff;"&gt;this</span>.table[pos][index] !=<span style="color: #000000;"&gt; key)) {
    index </span>+= 1<span style="color: #000000;"&gt;;
}

</span><span style="color: #0000ff;"&gt;if</span>(<span style="color: #0000ff;"&gt;this</span>.table[pos][index] ==<span style="color: #000000;"&gt; key) {
    console.log(key</span>+" 的键值为： "+<span style="color: #0000ff;"&gt;this</span><span style="color: #000000;"&gt;.table[pos][index]);
    </span><span style="color: #0000ff;"&gt;return</span> <span style="color: #0000ff;"&gt;this</span><span style="color: #000000;"&gt;.table[pos][index];
}</span><span style="color: #0000ff;"&gt;else</span><span style="color: #000000;"&gt;{
    console.log(</span>"无该键值"<span style="color: #000000;"&gt;);
    </span><span style="color: #0000ff;"&gt;return</span><span style="color: #000000;"&gt; undefined;
}

}

/测试开链法/
var someNames = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];
var hTable = new HashTable();
hTable.buildChains();
for (var i = 0; i < someNames.length; ++i) {
hTable.put(someNames[i],someNames[i]);
}
hTable.showDistro();
hTable.betterHash("Jennifer");
hTable.get("Jennidfer");
hTable.get("Jennifer");

原文链接：https://www.f2er.com/js/403376.html

散列表碰撞处理、开链法、HashTable散列

猜你在找的JavaScript相关文章