HashTable Data Structure

About HashTable

• 데이터를 단시간에 삽입하거나 저장된 데이터를 가져올 때 주로 사용하는 기법이다.
• Hash Table 이라는 자료 구조를 이용한다.
• 최대값이나 최소값 같은 전체를 탐색하는 방식에 조회에는 효율이 떨어진다.
• 해시함수를 통해 생성된 벨류값 이 같을때 이를 collision (충돌) 이라 한다.

• Collision 핸들링 기법

  • open-addressing (개방주소 = 선형조사)
  • separate chaining (분리된 체인)

  해싱 알고리즘의 핵심은 해싱을 생성하는 해시 생성 함수에 담겨져 있다. 해시생성 함수는 문자열을 입력받아 charCodeAt() 을 통해 넘어온 문자열을 ASCII 값으로 전환하고 여기에 상수값 37을 곱하여 누적합을 구한뒤 문자열 길이로 나머지를 구한다. 책에선 호너의 메서드라는 해싱 생성 알고리즘을 소개 하고 있다.

function betterHash(string) {
    const H = 37;
    let total = 0;

    for (let i = 0; i < string.length; i += 1) {
        total += H * total + string.charCodeAt(i);
    }
    total % string.length;
    return parseInt(total);
}

해시값은 데이터를 저장하는 장소인 해시 테이블에서 키값 으로 사용 된다. 해시 테이블의 특징은 키값만 주어지면 저장되어 있는 데이터를 검색하는데 걸리는 시간이 언제나 짧은 상수 값에 불과하다는점이다. 즉 테이블에 저장되어 있는 데이터의 양이 늘어나도 검색에 걸리는 시간은(거의) 변하지 않는다. 그렇기때문에 다른 알고리즘에 비해서 속도가 빠른 장점이 있지만 해시 테이블의 크기만큼 메모리 용량을 차지한다는 공간적 단점이 있다. (공간을 취하고 속도를 얻는다.)

ADT(Abstract Data Type) Structure

Method Name	contents
put (key, value)	키, 값 입력
get (key)	value 값을 출력
remove (key)	값 삭제
createHashCode(key)	해시값 생성

ADT 를 구현한 HashTable 은 다음과 같다.

class HashTable {
    constructor() {
        this.table = [];
    }

    put(key, value) {
        this.table[this.createHashCode(key)] = value;
    }

    get(key) {
        return this.table[this.createHashCode(key)];
    }

    remove(key) {
        this.table[this.createHashCode(key)] =undefined;
        //delete this.table[this.createHashCode(key)]; //다른방법
    }

    createHashCode(key) {
        let hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 37 //reference 호너의 메서드 알고리즘
    }
}

createHashCode 를 함수화 시켜서 Toyirn 과 Anaor 를 넣고 함수를 실행해보면 Hash 값이 동일한 16을 반환하는것을 알수 있다. 이것이 collision 현상이며 앞서 소개한대로 이를 핸들링하는 대표적인 2개의 방식을 소개한다. 분리된 체인은 2차원 배열, 선형 조사는 2개의 배열을 사용해 구현하는것이 핵심이다.

separate chaining(분리된 체인)

해시된 키를 저장할 배열을 만든 다음 해시 테이블의 각 배열 요소에 빈 배열을 할당하는 방법으로 분리된 체인 구현이 가능하다. 보편적으론 링크드 리스트를 사용한다.

[hashValue][key,value,key,value,key,value...]

put 과 get 을 분리된 체인 방식으로 수정하면 다음과 같다.

put(key, value) {
    var position = this.createHashCode(key);
    var index = 0;
        if (this.table[position][index] == undefined) {
            this.table[position][index] = key;
            this.table[position][index + 1] = value;
        } else {
            while (this.table[position][index] != undefined) {
                ++index;
            }
            this.table[position][index] = key;
            this.table[position][index + 1] = value;
        }
    }

    get(key) {
        var position = this.createHashCode(key);
        var index = 0;
        if (this.table[position][index] == key) {
            return this.table[position][index + 1]
        } else {
            while(this.table[position][index] != key) {
                index +=2;
            }
            if (this.table[position][index] == key) {
               return this.table[position][index + 1]
            } else {
                return undefined
            }
        }
    }

Linear probing (선형조사)

특정버켓에서 충돌이 발생하면 해시테이블에서 비어있는 버켓을 찾는 방법이다. 만약 table[i] 에서 충돌이 발생했다면 table[i+1] 비어있는지 살펴보고 table[i+...]이런식으로 빈공간을 찾아간다. 한번 충돌이 시작되면 그위치에 항목들이 집중 되는 현상을 군집화 현상 이라고 한다. key 테이블과 value 테이블을 이용하여 충돌을 방지하는 기법이다.

[keyValue : key] [keyValue : value]

/*valueTable 이라는 배열을 생성자에 추가해놓은 상태 this.valueTable = []; */
put(key ,value) {
    var position = this.createHashCode(key);

    if (this.table[position] == undefined) {
        this.table[position] = key;
        this.valueTable[position] = value;
    } else {

        if (this.table[position] == key) {
            this.valueTable[position] = value;
        } else {
            while (this.table[position] != undefined) {
                position++;
            }

            this.table[position] = key;
            this.tableValue[position] = value;
        }

    }
}

get(key) {
    var position = this.createHashCode(key);

    if (this.table[position] == key) {
        return this.tableValue[position]
    } 

}

다음 포스팅으로 이어 가겠습니다.