javaScript数据结构--散列表
散列集合是由一个集合构成，但是插入、移除、或获取元素时，使用的是散列函数
散列表的代码实现
// 散列表
function LinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
this.append = function(element) {
const node = new Node(element);
let current ;
if(head === null) {
head = node;
} else {
current = head;
while(current.next) {
current = current.next;
}
current.next = node;
}
length ++;
}
this.insert = function(position, element) {
if(position >= 0 && position <= length) {
const node = new Node(element);
let current = head,
previous,
index = 0;
if(position === 0) {
head.next = current;
head = node;
} else {
while(index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
}
this.remove = function(element) {
const index = this.indexOf(element);
return this.removeAt(index);
}
this.removeAt = function(position) {
if(position >= 0 && position <= length) {
var current = head,
previous,
index = 0;
if(position === 0) {
head = current.next;
}else {
while(index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
}else {
return null;
}
}
this.isEmpty = function() {
return length === 0
}
this.size = function() {
return length;
}
this.toString = function() {
var current = head,
string = '';
while(current) {
string += String(current.element);
current = current.next;
}
return string;
}
this.indexOf = function(element) {
var current = head,
index = -1;
while(current) {
index++;
if(current.element === element) {
return index;
}
current = current.next;
}
return -1;
}
this.getHead = function() {
return head;
}
}
var l = new LinkedList();
l.append("a");
l.append("b");
l.append("c");
console.log(l.size()); // 3
console.log(l.toString()); // abc
l.insert(1, "d")
console.log(l.size()); // 4
console.log(l.toString()); // adbc
console.log(l.indexOf("e")); // -1
console.log(l.indexOf("b")); // 2
l.removeAt(2);
console.log(l.toString()); // adc
l.remove("a"); // dc
console.log(l.toString());
l.remove("dd");
console.log(l.toString()); // dc
// 有时候， 一些键会有相同的散列值，不同的值在散列表中处于同一个位置，会遇到冲突。
处理冲突方式 分离链接、线性探查
分离链接的代码实现方式：
function HashTable() {
var table = [];
var loseloseHashCode = function(key) {
var hash = 0;
for(var i=0; i<key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37;
}
var ValuePair = function(key, value) {
this.key = key;
this.value = value;
this.toString = function() {
return '[' + this.key + '-' + this.value + ']';
}
}
this.put = function(key, value) {
var position = loseloseHashCode(key);
if(table[position] == undefined) {
table[position] = new LinkedList();
}
table[position].append(new ValuePair(key, value));
}
this.remove = function(key) {
const position = loseloseHashCode(key);
if(table[position] !== undefined) {
const list = table[position];
list.remove(key);
return true;
}
return false;
}
this.get = function(key) {
const position = loseloseHashCode(key);
if(table[position] !== undefined) {
const current = table[position].getHead();
while(current.next) {
if(current.element.key === key) {
return current.element.value;
}
current = current.next;
}
if(current.element.key === key) {
return current.element.value
}
}
return undefined;
}
}
//线性探查
function HashTable() {
var table = [];
var loseloseHashCode = function(key) {
var hash = 0;
for(var i=0; i<key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37;
}
var ValuePair = function(key, value) {
this.key = key;
this.value = value;
this.toString = function() {
return '[' + this.key + '-' + this.value + ']';
}
}
this.put = function(key, value) {
var position = loseloseHashCode(key);
if(table[position] == undefined) {
table[position] = new ValuePair(key, value);
}else {
var index = ++position;
while(table[index != undefined]) {
index ++;
}
table[index] = new ValuePair(key, value);
}
}
this.remove = function(key) {
const position = loseloseHashCode(key);
if(table[position] !== undefined) {
if(table[position].key === key) {
table[position] = undefined;
return true;
}else {
var index = position;
while(table[index] === undefined || table[index].key !== key ) {
index++;
}
if(table[index].key !== key) {
table[position] = undefined;
return true;
}
}
}
return false;
}
this.get = function(key) {
const position = loseloseHashCode(key);
if(table[position] !== undefined) {
if(table[position].key === key) {
return table[position].value;
}else {
var index = ++position;
while(table[index] === undefined || table[index] .key !== key) {
index++;
}
if(table[index].key === key) {
return table[index].value;
}
}
}
return undefined;
}
}
