논문 링크

https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf

2012년 발행

0. TITLE

ImageNet Classification with Deep Convolutional Neural Networks

: CNN을 이용해서 ImageNet 데이터에 classification task를 수행한다.

1. Abstract

ImageNet LSVRC-2010 contest에 나왔던 1.2 백만개의 데이터를 1000개의 클래스로 분류하는 작업이다.

top-1과 top-5 error rate가 각각 37.5%, 17%로 이전 SOTA 모델보다 개선된 수치를 달성하였다.

[ 구조 ]

6천만개의 파라미터와 65만개의 뉴런을 가진 뉴럴 네트워크가

5개의 convolution layers로 이루어져 있다.

이 중 일부는 max-pooling layer와 3개의 fully connected layer로 이어진다.

마지막은 1000개로 softmax.

[ 성능 향상을 위해 ]

fully connected layer의 overfitting을 줄이기 위해

"dropout"이라는 정규화 기법 사용

2. Results & discussion (data 훑기)

1) ILSVRC2010 test set 에 대한 error rates 비교

2) ILSVRC-2012 validation과 test sets에 대한 error rates 비교

(asterisk*가 붙은 것은 ImageNet 2011 Fall release 데이터로 “pre-trained”한 것)

3) Discussion

한 개라도 convolution layer가 사라진다면, 성능이 크게 저하된다. 

top-1  performance에서도 중간에 한 layer를 삭제했더니 2%의 성능 감소가 있었다.

따라서, depth는 결과에 있어 아주 중요한 요소이다.

학습에 있어서 unsupervised pre-training을 사용하지 않았다.

궁극적으로는 video sequences에 크고 깊은 convolution nets를 사용하여 

도움이 되는 정보를 제공하는 것이 목표이다.

3. Introduction

간단한 recognition task는 작은 데이터셋으로도 풀 수 있었지만,

실제 물체는 상당한 다양성을 가지고 있기 때문에 더 큰 training set를 사용해야만 한다.

수만은 물체들을 인식하기 위해서는 더 큰 용량을 가진 모델이 필요해졌다.

게다가 주어지지 않은 이미지들에 대한 고려도 해야한다.

이러이러한 문제점이 있지만,

다행히도 현재의 강력한 GPU와 오버피팅없이 train할 수 있을만큼 많은 레이블된 데이터가 있어

문제를 해결할 수 있다.

우리의 모델은 가장 큰 CNN 모델 중의 하나를 학습시켰고,

ILSVRC-2010 and ILSVRC-2012에서 가장 높은 결과를 얻을 수 있었다.

두 개의 GTX 580 3GB GPU로 5-6일간 학습시켰다.

우리의 실험은 더 빠른 GPU와 더 큰 데이터셋이 있다면 결과가 더 개선될 수 있음을 제안하였다.

4. Architecture

5개의 convolution layer + 3개의 fully-connected layer

1) ReLU의 Non-linearity

기존의 sigmoid나 tanh는 ReLU보다 훨씬 느리다. 즉, ReLU가 훨씬 빠르다.

ReLU는 기존의 activation 함수들보다 경사 하강 알고리즘에 유리하며, overfitting 감소하는 장점이 있다.

ReLU(solid), tanh(dashed) 비교 그래프

f(x) = |tanh| 함수로도 시도가 있었지만, 여기서는 overfitting을 막는 데에 초점이 맞춰져 있었기 때문에

우리가 발표한 ReLU를 사용할 때 발생되는 accelerated ability와는 다르다 

2) 2개의 GPU 사용

1.2백만개의 training 데이터를 사용하기에 1개의 GPU로는 충분치 않아서

두 개의 GPU 사용하였다. 

parallelization 기법 사용하였다.

kernel을 반으로 나눠 각각의 GPU에 넣고, 특정 layer에서 communication 하는 방식

3) Local Response Normalization 국지 정규화

정규화가 일반화에 영향을 준다는 것을 알아냈다.

k = 2, n = 5, α = 10−4, β = 0.75 는 여러 연구를 통해 알아낸 최적의 수치이며 

이는 하이퍼 파라미터이다. 아래의 식에 적용하여 정규화(normalization) 수행

* 해당 Normalization 방식을 ReLU 뒤에 수행하였다. 성능향상에 효과적이었다.

4) Overlapping pooling

pooling layer에서 s(stride) < z(filter size) 하게 만들어서

overlap 하게 만들었다. 성능향상에 효과적이었다.

5) 전체 구조

[ 모델 구조 ]

두 번째, 네 번째, 다섯 번째 convolution layer는 동일한 GPU에 있었던 이전 layer와만 연결되어 있다.

세 번째 Layer은 두 번째 layer의 모든 kernel map과 연결되어 있다.

fully-connect layer들은 모든 이전의 kernel map과 연결되어 있다.

첫번째, 두번째 convolution layer에서 LRN을 사용하였다.

max-pooling은 LRN 뒤에랑 다섯번째 convolution layer에서 사용하였다.

ReLU non-linearity는 모든 convolution layer와 fully-connected layer에서 사용되었다.

[ 필터 크기 ]

첫번째 convolution layer의 필터는 224x224x3 input images + 96개의 11x11x3 kernel + 4 pixel의 stride

두번째 convolution layer의 필터는 첫번째 layer의 output size(LRN과 max-pooling 적용된) + 256 kernels of size 5 × 5 × 48 The third, fourth, and fifth convolutional layers are connected to one another without any intervening pooling or normalization layers.

The third convolutional layer has 384 kernels of size 3 × 3 × 256 connected to the (normalized, pooled) outputs of the second convolutional layer.

The fourth convolutional layer has 384 kernels of size 3 × 3 × 192 , and

the fifth convolutional layer has 256 kernels of size 3 × 3 × 192. The fully-connected layers have 4096 neurons each.

5. Overfitting을 줄이기 위해

1) Data Augmentation

label-preservatin transformations를 사용하여 데이터셋을 인위적으로 늘리는 방식 사용하였다.

data augmentation은 CPU에서 실행하였으므로 computationally free하다.

- The first form of data augmentation

generating image translations & horizontal reflections

(random 224 × 224 patches)

-> softmax

- The second form of data augmentation

altering the intensities of the RGB channels in training images

Specifically, PCA on the set of RGB pixel values

add multiples of the found principal components with magnitudes proportional to the corresponding eigenvalues times a random variable drawn from a Gaussian with mean zero and standard deviation 0.1.

2) Dropout

여러 다른 모델들의 예측 결과를 합치는 것도 error 줄이는 데에 매우 효과적이다.

하지만, 굉장히 큰 neural network에 쓰기에는 너무 비싸다.

대신에 dropout을 사용하면 매우 효과적이다. (setting to zero the output of each hidden neuron with probability 0.5)

뉴런들끼리의 영향력을 줄여준다.

마지막에 0.5를 곱해준다.

우리는 dropout을 첫 두개의 fully-connected layer에 적용하였다.

6. Details of learning

stochastic gradient descent를 사용하였다.

batch size 128

momentum 0.9

weight decay 0.0005(중요함) -> 정규화 뿐만 아니라 training error를 줄여줬음

모든 layer에 동일한 Learning Rate 적용하였음 -> lr = 0.01

epoch = 90

https://www.acmicpc.net/problem/18870

import java.util.*;
import java.util.Map.Entry;

public class CoordinateCompression_18870_me {

    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        Integer N = sc.nextInt();
        Integer [] arr = new Integer[N];
        Map<Integer, Integer> orderedMap = new HashMap<>();


        for (int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }

        Integer [] sortedArr = arr.clone();
        Arrays.sort(sortedArr);


        Integer cnt = 0;
        for(int num : sortedArr){
            if (!orderedMap.containsKey(num)){
                orderedMap.put(num, cnt++);
            }
        };


        StringBuilder sb = new StringBuilder();    
        // 하나씩 출력하다가 StringBuiler 객체에 넣어서 한번에 출력하니까 성공뜸
        for(int num : arr){
            sb.append(orderedMap.get(num)).append(' ');
        }

        System.out.println(sb.toString());

    }
}

https://www.acmicpc.net/problem/14889

package com.company;
import java.util.Scanner;

public class StartAndLink_14889_me {


    static int min_diff = Integer.MAX_VALUE;;
    static int N;
    static boolean[] ans;
    static int[][] arr;


    public static void main(String [] args){

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N][N];
        ans = new boolean[N];

        for (int i=0; i<N; i++){
            for (int j=0; j<N; j++){
                arr[i][j] = sc.nextInt();
            }
        }

        startLink(0, 0);

        System.out.print(min_diff);
    }

    static void startLink(int idx, int count){

        if(count == N/2){
            int start_sum = 0;
            int link_sum = 0;
            for (int j=0; j<N-1; j++){
                for (int k=j+1; k<N; k++){
                    if (ans[j] == true && ans[k] == true){
                        start_sum += arr[j][k];
                        start_sum += arr[k][j];

                    } else if (ans[j] == false && ans[k] == false){
                        link_sum += arr[j][k];
                        link_sum += arr[k][j];

                    }
                }
            }

            int min_tmp = Math.abs(start_sum - link_sum);
            if(min_tmp == 0){
                System.out.print(0);
                System.exit(0);
            }

            min_diff = Math.min(min_tmp, min_diff);
            return;
        }

        for(int i = idx; i < N; i++) {  // 이 부분 때문에 계속 시간초과 났었음
            if(!ans[i]) {
                ans[i] = true; 
                startLink(i + 1, count + 1);   // 이 부분 때문에 계속 시간초과 났었음
                ans[i] = false;    
            }
        }
    }
}

백트래킹이란 무엇인가?

다시금 정의를 써보면 백트래킹은 구하고자 하는 해를 튜플로 나타내고 튜플에 기준 함수(한정 함수)를 적용했을 때의 결과가 최대치, 최소치 혹은 일정 조건을 만족하게끔 만들어주는 퇴각 검색 기법으로 정의된다.

백트래킹의 목표

상태 공간 트리를 DFS로 탐색하여 해결 상태에 도달하는데 있어 불필요한 탐색을 하지 않는 것을 목표로 한다.

Sum of Subset 문제에서 나올 수 있는 조합의 모든 경우의 수를 전체 탐색을 통해 확인한다면 집합

에 대해 |S| = n 일 때, 2^n 의 경우의 수를 탐색해야 한다. 즉, 시간 복잡도가 Ω(2^n)  이 되어 매우 비효율적인 탐색이 된다.

백트래킹 과정

백트래킹은 상태 공간 트리를 탐색하는 것을 전제로 한다.

(x[1], x[2], ..., x[k]) : 1~k번째 단계에서 선택된 노드들을 순서대로 튜플로 표현한다.

T(x[1], ... x[k-1]) : (x[1], ..., x[k])의 튜플의 경로가 상태 공간 트리에 속하도록 하는 모든 x[k]의 집합이다. 즉, (x[1], ..., x[k-1]) 의 경로에서 x[k-1]의 자식 노드들을 x[k]라고 한다.

이 문제에서 예시를 드는 Sum of Subset 문제는 n=4,  S={5, 9, 11, 20},  m=25  라 가정한다.

1. 문제 상황을 상태 공간 트리로 표현한다.

Sum of Subset의 경우 아래 그림과 같이 집합의 각 원소의 선택 여부로 상태 공간 트리를 표현할 수 있다.

이때 명시적 제약조건은 다음과 같다.

명시적 제약 조건 : 트리의 각 노드는 0 또는 1의 값을 가진다. 이때 i번째 높이의 노드는 i번째 원소의 선택 여부를 나타내며 0은 선택하지 않음, 1은 선택함을 나타낸다.

[그림1]

2. 루트 부터 DFS를 하여 불필요한 탐색을 하지 않고 한정 함수를 만족하는 (x[1], x[2], ..., x[n])를 찾는 것을 목표로 한다.

아래 [그림 2]는 Sum of Subset 문제에서 DFS 후 정답 25가 만들어지는 부분집합 {5. 25}를 찾아낸 상황이다.

[그림  2]

3. 각 노드 s 에 도착할 때마다 루트에서 s까지의 경로 예를 들어 k번째 선택에선 (x[1], x[2], ..., x[k])의 튜플이 한정함수를 만족하는지 판단한다.

한정 함수는 암시적 제약 조건의 참/거짓 여부를 판별하는 함수이다.

Sum of Subset의 경우 집합의 원소의 개수가 n이고 원하는 부분집합의 합이 m일 때 암시적 제약 조건은 다음과 같다.

암시적 제약 조건 : w[i]를 집합에서 i번째 원소라고 가정하면 한정함수

을 만족하면 참을 반환한다.

4-1. (x[1], x[2], ..., x[k])의 튜플이 한정 함수를 만족한다면 x[k] 노드를 live node이자 e-node로 변경한다.

4-2. 한정함수를 만족하지 않는 다면 T(x[1], ... x[k])의 노드들을 더이상 확장하지 않으며 dead node로 만든다.

5. k < n 일때 x[k]의 자식 노드들인 x[k+1] 들 즉, T(x[1], ... x[k])을 탐색한다.

6. 모든 자식 노드를 탐색했다면 현재 노드를 dead node로 변경한다.

7. 진행 도중 한정함수를 만족하는 (x[1], x[2], ..., x[n])에 도달하면 정답을 출력한다.

8. 정답이 도출되었거나 모든 노드가 dead 노드가 되었다면 탐색을 종료한다. 이때 정답이 여러개 인 경우에 모든 정답을 찾고 싶다면 모든 노드가 dead 노드가 될때까지 탐색해야 한다.

백준 문제 적용

https://www.acmicpc.net/problem/2580

package com.company;

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Ans {

    static ArrayList<int[]> empty_spots = new ArrayList<>();
    static int[][] matrix = new int[9][9];

    public static void main(String [] args){
        BufferedWriter buf = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);

        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++) {
                matrix[i][j] = sc.nextInt();
                if (matrix[i][j] == 0) {
                    empty_spots.add(new int[]{i, j});
                }
            }
        }

        sudoku(0);

        EDA();
    }

    static boolean sudoku(int count){
        if(count == empty_spots.size()){
            return true;
        } else {
            int [] position = empty_spots.get(count);
            int n = position[0];
            int m = position[1];
            for(int i=1; i<10; i++){
                if(isPromising(matrix, n, m, i)){
                    matrix[n][m] = i;
                    if(sudoku(count+1)) return true; // 끝에 도달했으면 return true
                    else matrix[n][m] = 0;   // 백트래킹
                }
            }
        }

        return false;  // 중요
    }

    static boolean isPromising(int[][] matrix, int n, int m, int num){
        int len = matrix.length;
        int n_block = (n / 3) * 3;
        int m_block = (m / 3) * 3;

        for(int i=0; i<len; i++){
            if(matrix[n][i] == num) return false;
            if(matrix[i][m] == num) return false;
        }

        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                if(matrix[n_block + i][m_block + j] == num) return false;
            }
        }

        return true;
    }

    public static void EDA(){
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                System.out.print(matrix[i][j]);
                System.out.print(' ');
            }
            System.out.println();
        }
    }
}

출처: https://it00.tistory.com/26 [IT]

https://dev-note-97.tistory.com/59

1-2. onCreate() 는 무엇일까?

onCreate를 이해하려면 안드로이드의 생명주기를 알아야 하는데요, 유니티와 같은 엔진을 사용해 본 경험이 있다면 좀 더 익숙할 수도 있습니다. 액티비티가 앱에서 처음으로 생성될 때 딱 한번 실행되는데요, 즉 액티비티가 생성되었다는 것을 알려주는 것과 같다고 볼 수 있습니다. 보통 이 onCreate에서 초기화 등을 하게 되는데 xml 파일과 연결하는 것도 여기서 하게 됩니다. setContentView가 바로 그 역할을 하는 것입니다. saveInstanceState는 앱이 불가피하게 종료되었을 경우 상태를 복구하기 위해 사용되는 것인데, 지금 당장 필요한 것은 아니므로 넘어가겠습니다. 안드로이드의 생명주기에 대한 내용은 아래에서 확인할 수 있습니다.

참고 : https://www.youtube.com/watch?v=49N59HnCAxQ


안드로이드의 액티비티 생명주기에 대해 간단하게 정리해보겠다.


먼저 파란배경의 launched는 아이콘을 눌러 액티비티가 나오게되는 시점이다.


OnCreate()는 생성자랑 비슷하다고 생각하면된다. 처음에 액티비티가 생성되었을 때 나온다.


OnStart()는 말그대로 액티비티가 시작되기 직전이라 생각하면된다. OnCreate()와 OnResume() 사이의 순서에 있다.


OnResume()은 OnStart와 비슷한데 이제 액티비티가 뜨고 동작하기 완전 직전에 실행 된다. OnStart보다 액티비티가 실행되기 더 직전에 가깝다.
(onPause에서 sharedpreferences에 임시저장된 데이터를 불러오는데 주로 사용된다.)


OnCreate=>OnStart=>OnResume은 액티비티가 실행되기 전에 차례대로 실행되는 순서라고 생각하면 이해하기가 쉬웠다.


OnPause()부터는 액티비티가 실행상태인 이후의 생명주기들인데 화면이 가려지기 직전에  onPause()가 호출된다. 그리고 만약 해당 앱을 종료하거나 현재 액티비티(화면)이 다른 화면에 의해 완전히 가려져 안보이게되어 백그라운드에 있는 상태 등은 onStop()이나 onDestory()까지 차례로 호출된다. 좀더 자세히 말하면 다음과 같다.


즉,
1. 현재화면 액티비티가 아직 완전히 가려지지않으면 onPause(),
2. 다른 액티비티가 위로 올라오면서 현재화면이 다가려지면(완전히 뒤로 들어가서 원래 액티비티가 백background에 있는 경우) onPause()->onStop() ==>다시 복구되면 onRestart()->onStart()
3. 아예 종료되거나 뒤로가기등으로 없어지면 onPause()->onStop->onDestory()
이런식으로 진행되는 거라고 보면 될 거 같다.


추가적으로 onPause()는 데이터를 저장하는데 주로 사용된다.
예를들어 게임을 하고있다가 중간에 전화가오거나 멈춰진 경우 전화가 끝나고 게임을 시작하면 게임이 원래 하던곳부터 계속 진행될수 있어야 할 것이다.
그런 경우 onPause()에서 현재의 데이터들을 sharedpreferences를 사용하여 저장해놓고 다시 앱을 진행했을때 복원 할 수 있게 onResume()에서 저장한 데이터들을 복원해 진행시킬 수 있다.


+) 추가적으로 데이터를 저장하는데 onSaveInstanceState() , onRestoreInstanceState()를 사용하는 방법도 있는데 화면전환할때 데이터 유지에도 유용하다.
자세한건 다음 사이트를 참고바란다.
https://developer.android.com/training/basics/activity-lifecycle/recreating.html?hl=ko&refresh=1




OnStop은 우리가 쓰던 액티비티가 완전히 이제 뒤로가서 안보일 때 호출되는 메소드이다. 그런데 OnStop인 상태일때 앱을 다시 킬수도 있는데 그런 경우 OnRestart()를 거쳐 onStart 생명주기로 다시 넘어간다. 참고로 onStop은 아직 액티비티가 소멸된 상태는 아니다.


추가로 하나 예를 더 들면 액티비티를 사용중에 홈버튼을 눌렀을 경우 onPasue와 OnStop이 순서대로 호출될 것이다. 그리고 다시 앱이 종료되지 않았으므로 앱을 다시 키면 원래 액티비티가 뜰건데 이때 onRestart와 onStart 가 호출된다.
그리고 만약 뒤로가기로 앱을 끄면 OnPasue->OnStop->OnDestory 순서로 호출될거고 다시 종료된 앱을 키면 OnCreate() 부터 호출된다.


OnDestory는 액티비티를 더이상 쓰지 않을 경우 액티비티를 종료했을 때 호출된다. 이 이후에 액티비티를 다시실행시키면 onCreate() 부터 진행될 것이다.


즉 OnPause=>OnStop=>OnDestory 도 위에서 말한거와 마찬가지로 액티비티가 실행되고 이후의 생명주기 순서라고 보면된다. 다만 어느정도 액티비티가 가려지느냐 없어지느냐로 판단하면 쉽게 이해 할 수 있을거 같다.


이 생명주기 그림은 중요하므로 꼭 외우고 이해하도록 해야한다.




-------------------------------------------------






밑 사진과 같은 자세하고 더 정확한 설명은 다음 사이트를 참고바란다.
출처 : https://developer.android.com/guide/components/activities?hl=ko

# 출처

https://youngest-programming.tistory.com/29

https://keykat7.blogspot.com/2021/03/android-activity.html

Hashing / HashTable

key 값을 조작해서, 배열의 인덱스와 매핑한다면, key에 해당하는 value 값을 배열의 인덱스에 접근하는 것처럼, O(1)의 비용으로 가져올 수 있을 것이다.

예를들어, 과일 과게에서 과일의 바코드 Id와 과일 명을 담는 테이블을 만든다고 치자. 

102 -> apple

543 -> banana

87426 -> orange

9 -> grape 

왼쪽이 id, 오른쪽이 상품명이라고 하면, 과일 과게 주인은 다음과 같은 표를 만들 수 있다.

만약 가게 주인이 id에 해당하는 과일 이름을 알고 싶다면, id를 순차적으로 하나씩 확인하고, 해당 id의 과일 이름을 가져와야 하는 것이다. 

혹은 이런 표를 만들면 어떨까. 

id의 끝자리를 인덱스로 해서 아래처럼 표를 그리면 가게 주인은 더이상 표를 쭉 탐색하지 않아도, 규칙에 따라 끝자리에 해당하는 인덱스 칸만 탐색하는 것으로 과일의 이름을 알 수 있는 것이다.

index = key % 10

fruit_name = table[index]

이렇게 key와 인덱스를 매핑하는 방법을 해싱이라고 한다.

Collision

위의 예시를 이어서, 이번에는 가게에 id가 4529인 멜론이 들어왔다고 가정해보자.

표의 인덱스 9는 이미 포도가 들어가있어, 가게 주인의 꼼수에 문제가 생겼다.

이렇게 동일한 입력 값이 같은 key 값을 가져 저장하지 못하는 상황을 충돌이라고 한다.

이 충돌을 해결하기 위한 방법으로 크게 Separate Chaining 방식과, Open Addressing 방식이 있다.

Separate Chaining 

충돌 시 해시 테이블 인덱스에 연결 리스트를 이용해서 여러 값을 연결한 형태로 저장한다.

상대적으로 적은 메모리를 사용하나, 해시 함수가 고른 분포를 만들지 못하면 성능에 치명적이다.

이를 테면, 모든 과일의 hash 값이 한 인덱스에 몰려 모든 value가 연결된다면, value를 찾아내는데는 연결 리스트를 모두 탐색해야하므로 최악의 경우 O(n)의 성능을 갖을 수 있다.

Open addressing

충돌 시, 연결이 아닌 비어있는 인덱스를 찾아 데이터를 저장하는 방식이다.

비어있는 인덱스 중 데이터가 저장될 공간을 찾는 규칙은 다음 세가지 방식으로 할 수 있다.

Linear Probing

선형 탐색에서 n=1, 즉 충돌 시 다음 비어있는 공간에 데이터를 넣는 방식으로 위 예시 충돌 상황을 처리해보자.

왼쪽이 데이터 추가 전, 오른쪽이 추가 후

위 그림에서 왼쪽은 원본 예시 상황이고, 여기에 4529 / 13 / 59를 추가하면 오른쪽 그림처럼 데이터가 저장된다.

4529는 인덱스 9에서 충돌이 일어나 다음 비어있는 칸, index 0에 저장되고, 13 역시 543의 바로 다음 칸 index 4, 59는 index 9, index 0 모두 값이 존재하므로 그 다음 칸인 index 1 에 저장된 것이다.

선형 탐색에서의 Search

선형 탐색에서의 탐색은 원래 해시 값에 해당하는 인덱스를 탐색하고, key가 일치하지 않으면 규칙에 맞춰 다음 칸, 또 다음 칸을 순서대로 탐색하는 것이다.

만약 탐색하는 칸이 비어있다면, 해당 key는 아직 저장이 안된 것을 알 수 있다.

이를 수도 코드로 나타내면 다음과 같다.

while(Node != null){  // 탐색 노드가 비어있다면 searchKey가 아직 저장이 안된 것임

  if(Node.key == searchKey) return Node.value;  
  
  Node = Node.next;   // 규칙에 맞는 다음 노드
}

key : 59의 value를 탐색하는 과정

선형 탐색의 단점이 여기에 있다.

1. Primary clustering

비어있지 않은 슬롯이 연속하게 되면 탐색에도 오래걸릴 뿐 아니라, 규칙에 따라 다음 빈 곳을 찾는 추가에도 많은 시간이 걸린다.

또 한번 군집이 시작되면 점점 더 커진다.

2. 삭제 처리

선형 탐색은 데이터 추가 시 규칙에 따라 슬롯을 탐색하고, 처음 만나는 빈 슬롯에 데이터를 저장한다. 그렇기 때문에 탐색 시에도 비어있는 슬롯을 만나면 데이터가 저장되지 않았다고 생각하고 탐색을 종료한다.

그런데 만약 중간 데이터가 삭제된 상황이라면 어떻게 할 것인가.

선형 탐색으로 해시 테이블을 만든다면 이를 해결하기 위해 삭제된 노드에 Dummy node를 포함시켜 탐색 시 다음 index를 연결하는 역할을 하도록한다.

이 Dummy node도 너무 많아질 경우 쓸데없는 탐색 시간과 공간이 낭비되므로, hash를 리빌딩하여 Dummy node를 삭제하는 과정이 필요하다.

자바에서의 Hash

자바8의 HashMap은 충돌을 어떤 방식으로 처리할까. 

1. Seperate Chaining 

자바7까지 HashMap에 Separate Chaining을 사용한 것은 같지만, 자바8부터는 버킷 당 8개 이상의 데이터가 쌓이면 링크드 리스트에서 트리로 변경한다. (이때 트리 탐색 대소 판단 기준은 해시 함수 값이다.)

그리고 데이터가 삭제되어 6개에 이르면 트리에서 다시 링크드 리스트로 변경한다.

이는 노드가 많을 경우 탐색 성능을 위해서는 트리가 우수하지만, 노드가 적을 경우에 트리는 리스트보다 메모리 사용량이 많고, 탐색 성능에서도 크게 차이가 없기 때문이다.

또, 리스트->트리, 트리->리스트를 8/6으로 차이를 둔 것은 만약 차이가 1이라면 한 쌍이 추가, 삭제가 반복될 경우 자료 구조를 매번 변경해야하는 오버헤드를 낳을 수 있어 2개의 차이를 뒀다고 한다.

2. 해시 버킷 동적 확장

해시 버킷의 개수가 적으면 메모리를 아낄 수 있고, 버킷이 많으면 해시 충돌을 줄여 성능을 높일 수 있을 것이다.

자바의 HashMap에서는 데이터의 개수가 일정 개수 이상이 되면 버킷의 개수를 2배로 늘려 성능 손실 문제를 해결한다고 한다.

이때 어느정도 예측 가능한 상황의 경우 버킷의 최초 개수와 임계점을 직접 지정할 수 있다. (디폴트는 16개, 75%이다)

최초 버킷의 수는 말그대로 최초 Entry 개수를 말하고, 임계점(load Factor)는 현재 Entry 개수의 몇 배수가 되면 버킷 확장을 실행할까를 결정한다.

예를 들어, 버킷이 100개이고, load factor가 0.87이면, 데이터의 개수가 87개 이상일 때, 버킷의 개수를 200으로 확장하는 것이다.

구현

자바로 간단하게 Seperate Chaining을 구현해봤다.

class HashTable {

    class Node {
        String key;
        String value;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    private LinkedList<Node>[] table;

    public HashTable(int size) {
        table = new LinkedList[size];
    }

    Long getHashCode(String key) {
        Long hashCode = 0L;

        for (char c : key.toCharArray()) { hashCode += (long) c; }

        return hashCode;
    }

    public int getIndex(Long hashCode) {
        return (int) (hashCode % table.length);
    }

    Node searchNode(int index, String key) {
        LinkedList<Node> indexedList = table[index];

        for (Node n : indexedList) {
            if (n.key == key) { return n; }
        }

        return null;
    }

    public void put(String key, String value) {
        Long hashCode = getHashCode(key);
        int index = getIndex(hashCode);

        if (table[index] == null) {
            table[index] = new LinkedList<Node>();
            table[index].add(new Node(key, value));
        }
        else {
            Node searched = searchNode(index, key);

            if (searched != null) { searched.value = value; }
            else { table[index].add(new Node(key, value)); }
        }
    }

    public String get(String key) {
        Long hashCode = getHashCode(key);
        int index = getIndex(hashCode);

        Node searched = searchNode(index, key);

        if (searched == null) { return ""; }
        else { return searched.value; }
    }
}