TIL 2022-01-20 HashTable, 정렬 구현하기

 

Hash Table

HashTable는 Key,Value의 자료구조로 key값에 해시함수를 적용해 고유의 index를 생성하고, 이 인덱스 값을 통해 저장하고 검색함. 실제 저장되는 곳을 버킷, 슬롯이라고 한다.

 

Hash function은 key를 고정된 값의 hash로 변경하는 함수를 의미함.

 

key값에서 데이터를 찾을때 O(1)의 시간복잡도를 가진다.

순서가 있거나 관계가 있는 배열에는 어울리지 않고, 미리 저장공간을 할당해야한다는 불편함이 있음.

 

중요한 것은

1. 어떤 해시 함수를 적용할 것인가

2. 해시 충돌이 일어났을떄 어떻게 해결할 것인가인데 하나씩 보자

 

1. 어떤 해시 함수를 적용할 것인가

• division method
  • 가장 기본적인 해시 함수이다. 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 변환한다. 간단하면서도 빠른 연산이 가능한 것이 장점이다.
  • 해시의 중복을 방지하기 위해 테이블의 크기 m은 소수로 지정해서 사용하는것이 좋다. 하지만 남는 공간이 발생해 메모리상으로 비효율적이다.
• multiplication method
  • 숫자 키 k, A는 0<A<1 사이의 실수 일때 `h(k) = (kAmod1)*m 으로 계산한다.
  • 2진수 연산에 최적화된 컴퓨터구조를 고려한 해시함수이다.
• univeral hasing
  • 여러개의 해시함수를 만들고, 이 해사함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법.
  • 서로 다른 해시함수가 서로 다른 해시값을 만들어내기 때문에 같은 공간에 매핑할 확률을 줄이는 것이 목적

 

• Digit Folding
  
  • 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.

 

해시 충돌

해시 충돌은 다른 key가 동일한 hash로 변환되어 key-value가 1대1 매칭이 안되는 문제를 의미한다.

 

Chaining

체이닝은 충돌이 일어나면 값들을 연결리스트로 묶는 방법이다.

장점: 별도의 공간을 만들어낼 필요가 없다

단점: 동일 해쉬에 충돌이 여러번 일어나여 연결리스트가 길어지면 검색 효율이 낮아짐

충돌이 일어난 경우 Chaining에 연결된 연결리스트까지 검색해야하므로 시간복잡도가 O(n)이 됨

 

Open Addressing

충돌이 일어나면 비어있는 해쉬에 데이터를 저장하는 방법이다.

비어있는 Hash를 찾는 방법이 여러가지 있다.

 

 

• Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
• Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
• Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

 

 

장점: 1:1 관계를 유지하여 Chaining같이 검색 효율이 낮아지는 일이 없음

Open Addressing에서 데이터 삭제하면 삭제된 공간은 dummy space로 활용되는데 따라서 Hash Table을 재정리해줘야한다.(왜?)

 

 

 

function selectionSort(arr:number[]){
    for(let i = 0 ; i<arr.length-1; i++){
        let min = i;
        for(let j = i ; j < arr.length; j++){
            if(arr[min]>arr[j]){
                min = j;
            }
        }
        let temp = arr[i];
        arr[i] = arr[min];
        arr[min] =temp;
    }
    return arr;
}
function bubbleSort(arr:number[]){
    for(let i = arr.length-1 ; i >= 0; i--){
        for(let j = 0 ; j < i; j++){
            if(arr[j]>arr[j+1]){
                let temp  =arr[j];
                arr[j] = arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    return arr;
}
function insertionSort(arr:number[]){
    for(let i = 1 ; i < arr.length; i++){
        let key  = arr[i];
        let j = i-1;
        while(j>=0 && arr[j]>key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1]= key;
    }
    return arr;
}

function quickSort(arr:number[], left=0, right=arr.length-1){
    if(left>=right){
        return;
    }

    const mid = Math.floor((left+right)/2);
    const pivot = arr[mid];
    const paritition = divide(arr,left,right,pivot);

    quickSort(arr,left,paritition-1);
    quickSort(arr,paritition,right);
    function divide(arr:number[],left:number,right:number,pivot:number){
        while(left<=right){
            while(arr[left]<pivot){
                left++;
            }
            while(arr[right]>pivot){
                right--;
            }
            if(left<=right){
                let temp = arr[left];
                arr[left]= arr[right];
                arr[right] =temp;
                left++;
                right--;
            }
        }
        return left;
    }
    return arr;
}

function mergeSort(arr:number[]):number[]{
    if(arr.length<2){
        return arr;
    }
    const mid = Math.floor(arr.length/2);
    const left = arr.slice(0,mid);
    const right = arr.slice(mid);
    return merge(mergeSort(left),mergeSort(right));

    function merge(left:number[],right:number[]){
        const resultArr:number[] = [];

        while(left.length&&right.length){
            if(left[0]<right[0]){
                resultArr.push(left.shift() as number);
            }else{
                resultArr.push(right.shift() as number);
            }
        }
        while(left.length){
            resultArr.push(left.shift() as number);
        }
        while(right.length){
            resultArr.push(right.shift() as number);
        }
        return resultArr;
    }
}

function heapSort(arr:number[]){
    let arrLen = arr.length;

    for(let i =Math.floor(arr.length/2-1) ; i >=0; i--){
        heapify(arr, arrLen, i);
    }
    for(let i= arr.length-1; i>=0; i--){
        swap(arr, 0,i);
        heapify(arr,i,0);
    }
    return arr;
    function swap(arr:number[],i:number,j:number){
        const c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }

    function heapify(arr:number[], n:number, i:number){
        let left = i*2+1;
        let right = i*2+2;
        let max = i;
        if(left<n && arr[left]>arr[i]){
            max = left;
        }
        if(right<n && arr[right]>arr[i]){
            max = right;
        }
        if(max!=i){
            swap(arr, i,max);
            heapify(arr,n, max);
        }
    }


}

구현하기 쉬운건 시간 복잡도가 O(N^2)이라니 열심히 살라는 신의 뜻일까

 

 

 

 

 

 

 

 

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

해싱, 해시함수, 해시테이블 · ratsgo's blog

 

 

 

https://mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?

 

https://go-coding.tistory.com/30

[자료구조] Hash의 개념 및 설명