HashTableSeparateChaining

分離鏈結

by Chris_Walter

JavaScript

class Node{
  constructor(element){
	  this.element = element;
		this.next = null;
	}
}

class LinkedList{
  constructor(){
	  this.length = 0;
	  this.head = null;
	}
	getHead(){
	  return this.head;
	}
	append(element){
	  let node = new Node(element);
	  if(this.head === null){
		  this.head = node;
		} else{
		  let current = this.head;
			while(current.next !== null){
			  current = current.next;
			}
			current.next = node;
		}
		this.length++;
	}
	size(){
	  return this.length;
	}
	isEmpty(){
	  return this.size() === 0;
	}
	removeAt(position){
	  if(position > -1 && position < this.size()){
		  let current = this.head;
			if(position === 0){
			  this.head = current.next;
			} else{
			  let index = 0
				let previous;
				while(position !== index){
				  index++;
					previous = current;
					current = current.next;
				}
				previous.next = current.next;
			}
			this.length --;
			return current.element;
		} else{
		  return undefined;
		}
	}
	indexOf(element){
	  let index = 0;
		let current = this.head;
		while(current !== null){
		  if(element === current.element){
			  return index;
			}
			index++;
			current = current.next;
		}
		return -1;
	}
	remove(element){
	  let index = this.indexOf(element);
		return this.removeAt(index);
	}
}

class ValuePair{
  constructor(key,value){
	  this.key = key;
		this.value = value;
	}
}

class HashTableSeparateChaining{
  constructor(){
	  this.table = [];
	}
	hash(key){
	  let sum = 0;
		for(let i=0; i<key.length; i++){
		  sum+= key.charCodeAt(i);
		}
		return sum % 37;
	}
	put(key,value){
	  let position = this.hash(key);
		if(this.table[position] == undefined){
		  this.table[position] = new LinkedList();
		}
		this.table[position].append(new ValuePair(key,value));
	}
	get(key){
	  let position = this.hash(key);
		if(this.table[position] !== undefined){
		  let current = this.table[position].getHead();
			while(current.next !== null){
			  if(current.element.key === key){
				  return...