해시 테이블 (Hash table)

 

 

Hash Function

해시 함수는 어떠한 문자열을 고정된 길이의 암호화된 문자열로 바꿉니다.

암호화되어 출력된 문자열은 원래 문자열로 되돌아 갈 수 없습니다.

밑에 있는 두개의 코드처럼 해시함수를 간단히 구현할 수 있습니다.

function hashFunction (key) {
  return key % 3;
}

console.log(hashFunction(128745)); // 0

String.prototype.hashCode = function() {
    var hash = 0;
    if (this.length == 0) {
        return hash;
    }
    for (var i = 0; i < this.length; i++) {
        var char = this.charCodeAt(i);
        hash = ((hash<<5)-hash)+char;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
}

console.log('안녕하세요'.hashCode()); // 803356551

 

Hash Table

직접 주소 테이블 + 해시 함수

 

해시 테이블은 직접 주소 테이블에 해시 함수가 더해져 빠르고 공간 효율성까지 좋은 자료구조입니다.

저장하려는 데이터가 해시 함수를 거쳐서 나오게된 값이 배열의 인덱스가 되어서 데이터가 저장됩니다. 

찾으려는 데이터를 해싱하여 인덱스을 얻고, 바로 조회하면 되므로 시간 복잡도가 O(1)가 되는 자료구조입니다.

 

 

직접 주소 테이블 (Direct Address Table)

 

해시 테이블 (Direct Address Table)

 

 

충돌 (Hash Collision)

해시 함수를 통해서 공간의 효율성을 얻었지만 같은 값이 해싱되어 나오는 경우가 생깁니다.

해싱되어 나온 인덱스 값에 이미 데이터가 있는 경우를 다루는 여러방법이 있습니다.

 

 

 분리 연결법 (Separate Chaining) 

이미 데이터가 들어간 인덱스에 또 다른 데이터를 연결 리스트(Linked List) 또는 트리 (Tree) 형태로 더하는 방법입니다.

 

 테이블 크기 재할당 (Resizing) 

테이블에 공간이 없어서 더이상 저장을 하지 못하는 상황이 발생하기에 저장공간을 늘리거나 줄이는 방법입니다.

기본적으로 저장공간을 두배로 늘리거나 절반으로 줄여서 저장공간을 최대한 효율적으로 사용합니다.