문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42576

1. 문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

2. 분석

1. 참가 선수 명단을 배열로 저장
2. 완주한 선수 명단 배열로 저장(참가 선수 명단보다 1적게 설정)
3. 참가자 중에는 동명이인이 있다
4. 완주하지 못한 인원을 반환해준다

3. 설계

Hash를 통해 데이터 저장

Hash : 임의의 크기를 가진 데이터를 고정된 크기의 데이터로 변화시켜 저장하는것이다.

• 이처럼 Hash에 저장할 때는 정해진 크기 안에서 인덱스가 생성이 되고 key값이 들어오면 hash function에서 식을 사용하여 고유한 숫자를 만들어 내는데 이것이 index 번호이다. 그 후 맵핑을하여 바구니에 저장이 된다.

  Hash 식 구조
  Bucket은 8개가 있다고 가정할때 Hash function은 학과의 알파벳들을 숫자로 변환하여 합한 술르 8로 나눈 나머지를 반환한다.
  
  이 때 hash function이 8로 나눈 나머지를 반환하는 이유는 bucket이 8개이므로 숫자를 0~7 내로 압축하기 위해서이다.
  
  hash function을 h(key)라 하면, h("Music") = (13+21+19+9+3) mod 8 = 1 이고, h("History") = (8+9+19+20+15+18+25) mod 8 = 2 이다.
  이와 같이 모든 데이터를 hash function을 통해 bucket을 결정하여 삽입하면 아래와 같이 된다.
  

Hash Table : Hash함수를 이용해 array에 접근하는 자료구조로 값을 넣을때도 hash(key)를 쓰고 값을 뺄 때도 hash(key)를 쓴다. 그래서 접근 속도가 O(1)이 나와서 빠른 자료구조 이다.

4. CODE

Hash 방식

public class HashFunction {
    public int hash(String key) {
        int asciiSum = 0;
        for(int i=0; i<key.length(); i++) {
            asciiSum += key.charAt(i);
        }
        return asciiSum % 90;
    }

    public static void main(String[] args) {
        HashFunction hf = new HashFunction();
        hf.hash("yeong");
    }
}

• return ascii % size;를 한 이유는 지정된 크기의 배열에 값을 저장하고 size로 정한 배열의 어딘가로 가도록 하기 위함이다(즉, hash가 정한 식에 따라 index 값을 받기 위해)
• size는 Hash 충돌이 나지 않으면서도 메모리를 너무 많이 쓰지 않는 임의의 크기로 설정한다.
  사이즈가 너무 크면 메모리를 많이 사용하고 너무 작으면 중복 값이 발생해 충돌이 난다.

Hash 실습

public class HashTableSolution {
    private int size = 10000;
    private int[] table = new int[size];

    public HashTableSolution() {
    }

    public HashTableSolution(int size) {
        this.size = size;
        this.table = new int[size];
    }

    public int hash(String key) {
        int asciiSum = 0;
        for (int i = 0; i < key.length(); i++) {
            asciiSum += key.charAt(i);
        }
        return asciiSum % size;
    }

    public void insert(String key, Integer value) {
        int hashCode = hash(key);
        this.table[hashCode] = value;
        System.out.println(key + " " + hashCode + "방에 저장이 완료되었습니다.");
    }

    public int search(String key) {
        return this.table[hash(key)];
    }

    public static void main(String[] args) {
        String[] names = new String[]{"aaa","bbb","ccc"};

        HashTableSolution ht = new HashTableSolution(200);
        for (int i = 0; i < names.length; i++) {
            ht.insert(names[i] , ht.hash(names[i]));
        }
        System.out.println(ht.search("aaa"));
        System.out.println(ht.search("ccc"));
    }
}

5. 해시충돌

해시의 고유식을 통해 임의의 값을 지정하여 그곳에 데이터를 저장하는 방식을 하게되면 많은 데이터를 처리할때 값이 중복되어 같은 자리에 2개 이상의 데이터가 입력되는 경우가 발생한다.
따라서, 이를 방지하기 위한 방법을 제시한다.

(1) 리스트를 사용하여 같은 자리에 2개 이상에 데이터를 받는다.

1. 저장할 때 Key도 같이 저장한다.
2. List에 n개를 저장한다.
3. 찾을때 해당 칸에서 전체 스캔을 해서 key가 같으면 return

1개 입력시 {test:1} 표현법

		148
		[{test:1}]

2개 입력시 {test2:2} 표현법

		148
		[{test:1}]
		[{test2:2}]

CODE

// 해시 충돌 했을경우 해결법
public class HashSolution {

    // 멤버변수
    private int size;
    private List<Node>[] table;     // 2차원 배열 리스트
    // ex) 2차원 배열 리스트에 Node형식으로 저장함
    //       1           2          3
    //   ["aa",1]    ["aaa",2]
    //   ["bb",2]
    
    // 내부 클래스 선언
    class Node {        // Node DTO [(String)key,(Integer)value] 형식
        private String key;
        private Integer value;

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

        public String getKey() {
            return key;
        }

        public Integer getValue() {
            return value;
        }
    }


    // 디폴트 생성자
    public HashSolution() {     // 생성자
        this.size = 10000;
        this.table = new ArrayList[size];
    }
    
    // 생성자 오버로딩
    public HashSolution(int size) {     // 생성자
        this.size = size;
        this.table = new ArrayList[size];   // 2차원 배열 사이즈 선언
    }

    public int hash(String str) {       // hash를 통해 임의의 숫자 구함
        int ascii = 0;
        for (int i = 0; i < str.length(); i++) {
            ascii += str.charAt(i);
        }
        return ascii % size; // 1000개   0~999까지의 값 출력
    }

    public Integer get(String key) {        // 해시 값 찾기
        List<Node> nodes = this.table[hash(key)];   // 2차원 배열 리스트중 hash(key)에 해당하는 배열 가져옴
        // ex) 2차원 배열 리스트의 해당 값을 가져옴 만약 1번일때
        //       1           2          3
        //   ["aa",1]    ["aaa",2]
        //   ["bb",2]
        
        // nodes => ["aa",1],["bb',2] 가져옴
        for (Node node : nodes) {       // 2번 반복
            if (key.equals(node.getKey())) {    // 입력한 키와 찾아온 키를 비교함
        // ex) 입력된 키가 "bb"일때
        // 1번째 순서일때는 못찾고 2번째 순서일떄 찾는것으로
        // 2번째 node = {"bb",2}  , node.getkey() = "bb"
        // bb.equals(bb) true
                return node.value;      // 2번쨰 노드의 객체의 값인 2를 가져옴
            }
        }

        return null;
    }

    public void insert(String key, Integer value) {
        int hashCode = hash(key);       // 입력한 문자를 가지고 해시를 통해 임의의 key값 출력
        if (this.table[hashCode] == null) {     // 만약 2차원 배열 리스트에 없는 값이라면
            this.table[hashCode] = new ArrayList<>();   // 2차원 배열 리스트 생성
        }
        this.table[hashCode].add(new Node(key,value));  // 해당 해쉬 자리에 key,value 객체 저장
    }

    public static void main(String[] args) {
        String[] names = new String[]{"DongyeonKang",
                "SubinKang", "KwanwunKo", "HyunseokKo", "KyoungdukKoo", "YeonjiGu", "SoyeonKown", "OhsukKwon", "GunwooKim", "KiheonKim", "NayeongKim", "DohyeonKim", "MinkyoungKim", "MinjiKim", "SanghoKim", "SolbaeKim", "YejinKim", "EungjunKim", "JaegeunKim", "JeonghyeonKim", "JunhoKim", "JisuKim", "kimjinah", "HaneulKim", "HeejungKim", "KimoonPark", "EunbinPark", "JeongHoonPark", "JeminPark", "TaegeunPark", "JiwonBae", "SeunggeunBaek", "JihwanByeon", "HeungseopByeon", "JeongHeeSeo", "TaegeonSeo", "SeeYunSeok", "SuyeonSeong", "SeyoelSon", "MinjiSong", "JinwooSong", "hyunboSim", "SominAhn", "JiyoungAhn", "ChangbumAn", "SoonminEom",
                "HyeongsangOh", "SuinWoo", "JuwanWoo", "InkyuYoon", "GahyunLee", "DaonLee", "DohyunLee", "SanghunLee", "SujinLee", "AjinLee", "YeonJae", "HyeonjuLee", "HakjunYim", "SeoyunJang", "SeohyeonJang", "JinseonJang", "SujinJeon", "SeunghwanJeon", "DaehwanJung", "JaeHyunJeung", "HeejunJeong", "GukhyeonCho", "MunjuJo", "YejiJo", "ChanminJu", "MinjunChoi", "SujeongChoi", "SeunghoChoi", "AyeongChoi", "GeonjooHan", "JinhyuckHeo", "MinwooHwang", "SieunHwang",
                "JunhaHwang"};


        HashSolution hashSolution = new HashSolution(200);
        hashSolution.insert("Yoonseo", 1);
        hashSolution.insert("Seoyoon", 2);

        int result = hashSolution.get("Yoonseo");
        if (result == 1) {
            System.out.println("테스트 성공");
        } else {
            System.out.printf("테스트 실패 value:%d", result);
        }

        result = hashSolution.get("Seoyoon");
        if (result == 2) {
            System.out.println("테스트 성공");
        } else {
            System.out.printf("테스트 실패 value:%d", result);
        }
    }
}

※ 참고자료
https://ejyoo.tistory.com/72
https://ju-hy.tistory.com/107