[Non-Linear] Hash Table

1. 해시테이블이란?

   1) 효율적인 탐색을 위한 자료구조로서 키-값으로 저장을 한다. 

   2) 키를 해싱하여 해시테이블의 인덱스를 구한 후에 저장을 함.

     ※ 해시테이블은 개발자의 기본이라고 불리울 만큼 중요하며, 자유자재로 다룰 줄 알아야 한다.

   3) 핵심은 해시함수를 거친 후 해시테이블에 저장되는 방식이다.

2. 충돌시 회피방법 3가지.

   1) Chaining  : 저장을 Linked List 방식으로 저장하는 방법이다.

chaining방식

   2) Linear probing :  비어있는 인덱스에 저장하는 방식이며, if 5번 인덱스랑 겹치는데 6번 인덱스가 비어있으면 6번

                             인덱스에 저장, 6번도 이미 차있으면 7번에 저장하는 방식.

Linear Probing 방식

   3) Table resize : 테이블을 기존의 2배로 늘리고 조정하는 방식.

 

1. 간단한 해시테이블.

//put(key, value)
//remove(key)
//get(key)

function HashTable(){
  var table = [];
  
 this.put = function(key, value){
   var position = generateHashCode(key);
   console.log(position + '-'+key);
   table[position] = value;
 }  
  
 this.get = function(key){
   return table[generateHashCode(key)];
 } 
 
 this.remove = function(key){
   table[generateHashCode(key)] = undefined;
 }  
  
 this.print = function(){
   for(var i=0; i<table.length; i++){
     if(table[i] !== undefined){
       console.log(i+": "+table[i]);
     }
   }
 } 
}

//해시 생성기.
var generateHashCode = function(key){
  var hash = 0;
  for(var i = 0; i<key.length; i++){
    hash +=key.charCodeAt(i);  //UTF-16 코드를 10진수로 표현한 수. 
  }  
  return hash % 37;  //임의숫자
}

var hash = new HashTable();
hash.put('Gandalf','gandalf@email.com');
hash.put('John','johnsnow@email.com');
hash.put('Tyrion','tyrion@email.com');
hash.put('Aaron','aaron@email.com');
hash.put('Jonathan','jonathan@email.com');
hash.put('Jamie','jamie@email.com');
hash.put('Sue','sue@email.com');
hash.print();

2. chaining 포함한 해시테이블

  1) Linked List로 저장하기 때문에 Linked List 메서드를 만들어야 한다.

//put, get, remove 변경

function HashTable(){
  var table = [];
  
 this.put = function(key, value){
   var position = generateHashCode(key);
   if(table[position] === undefined){ //chaining으로 추가.
     table[position] = new LinkedList();
   }
   table[position].append(new ValuePair(key,value));
 }  
  
 this.get = function(key){
   var position = generateHashCode(key);
   if(table[position] !== undefined){
     //링크드리스트 키 값 찾기
     var current = table[position].getHead();
   
     while(current.next){
       if(current.item.key === key){
         return current.item.value;
       }
       current = current.next;
     }  
     //처음 or 마지막 요소 탐색
     if(current.item.key === key){
       return current.item.value;
     }
   }
     return undefined;   
 } 
 
 this.remove = function(key){
   var position = generateHashCode(key);
   
   if(table[position] !== undefined){
     var current = table[position].getHead();
     while(current.next){
       if(current.item.key === key){
         table[position].remove(current.item);
         if(table[position].isEmpty()){
           table[position] = undefined;
         }
         return true;
       }
       current = current.next;
     }
     if(current.item.key === key){
       table[position].remove(current.item);
       if(table[position].isEmpty()){
         table[position] = undefined;
       }
       return true;
     }
   }
   return false;
 }  
  
 this.print = function(){
   for(var i=0; i<table.length; i++){
     if(table[i] !== undefined){
       console.log(i+": "+table[i]);
     }
   }
 } 
}

//해시 생성기.
var generateHashCode = function(key){
  var hash = 0;
  for(var i = 0; i<key.length; i++){
    hash +=key.charCodeAt(i);  //UTF-16 코드를 10진수로 표현한 수. 
  }  
  return hash % 37;  //임의숫자
}

//chaining으로 추가
var ValuePair = function(key,value){
  this.key = key;
  this.value = value;
  this.toString = function(){
    return '['+this.key+' - ' + this.value +']';
  }  
}


var hash = new HashTable();
hash.put('Gandalf','gandalf@email.com');
hash.put('John','johnsnow@email.com');
hash.put('Tyrion','tyrion@email.com');
hash.put('Aaron','aaron@email.com');
hash.put('Jonathan','jonathan@email.com');
hash.put('Jamie','jamie@email.com');
hash.put('Sue','sue@email.com');
hash.print();

3.Linear Probing

  1) 해시테이블 차있으면 비어있는 index 찾아서 저장.

function HashTable(){
  var table = [];
  
 this.put = function(key, value){
   var position = generateHashCode(key);
   if(table[position] === undefined){ //chaining으로 추가.
     table[position] = new LinkedList();
   }else{ //Linear Probing 방식으로 인한 변경.
     var index = ++position;
     while(table[index] != undefined){
       index++;
     }
     table[index] = new ValuePair(key,value);
   }  
 }  
  
 this.get = function(key){
   var position = generateHashCode(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;   
 } 
 
 this.remove = function(key){
   var position = generateHashCode(key);
   if(table[position] !== undefined){    
     if(table[position].key === key){
       return table[index] = undefined;
     }else{
       var index = ++position;
       while(table[index] === undefined || table[index].key !== key){
         index++;
       }
       if(table[index].key === key){
         return table[index] = undefined;
       }
     }
   }
     return undefined;   
 }  
  
 this.print = function(){
   for(var i=0; i<table.length; i++){
     if(table[i] !== undefined){
       console.log(i+": "+table[i]);
     }
   }
 } 
}

//해시 생성기.
var generateHashCode = function(key){
  var hash = 0;
  for(var i = 0; i<key.length; i++){
    hash +=key.charCodeAt(i);  //UTF-16 코드를 10진수로 표현한 수. 
  }  
  return hash % 37;  //임의숫자
}

//chaining
var ValuePair = function(key,value){
  this.key = key;
  this.value = value;
  this.toString = function(){
    return '['+this.key+' - ' + this.value +']';
  }  
}


var hash = new HashTable();
hash.put('Gandalf','gandalf@email.com');
hash.put('John','johnsnow@email.com');
hash.put('Tyrion','tyrion@email.com');
hash.put('Aaron','aaron@email.com');
hash.put('Jonathan','jonathan@email.com');
hash.put('Jamie','jamie@email.com');
hash.put('Sue','sue@email.com');
hash.print();

4. resize

var resizeHashCode = function(key){
  var hash = 5831; //해시 변수를 소수로 시작함. 대부분 5381로 함.
  for(var i = 0; i<key.length; i++){
    hash = hash*33 + key.charCodeAt(i);  //해시값에 33(마법의 숫자라고 함..;;;) 곱한 후 문자의 아스키값과 합한다.
  }  
  return hash % 1013;  //임의숫자
}

 위의 설명에 대해서 5831이나 33인 내용은 

https://stackoverflow.com/questions/10696223/reason-for-5381-number-in-djb-hash-function 여기서 참고할 수 있다.