Hash란?

---

Hash란 key value쌍으로 이루어진 데이터 구조이다.
Hashing이란 Key가 있는 위치를 산술연산으로 찾아가는 검색 방법을 말한다.
이때 Key값을 원소 위치로 바꿔주는 함수를 Hash Function
Hash Function에 의해 계산된 주소에 저장할 값을 저장한 표를 Hash Table이라고 한다.

import java.util.HashMap;

public class Practice {
    public static void main(String[] args) {
        //hash선언
        HashMap<String, Integer> hash = new HashMap<>();
        /*
        * key : Test
        * value : 1
        * */
        hash.put("Test",1);
        
        int value = hash.get("Test");
        System.out.print(value); //1출력
    }
}

특징

• Key는 절대로 중복되지 않는다.
• List보다 더 빠르게 값을 찾을 수 있다.

---

Hash Collision(해시충돌)

위 특징에서 Key는 절대로 중복되지 않는다고 언급하였다. 그래서 동일한 Key가 들어갈시 이전 value는 사라지고 가장 최근에 저장된 value만 남는다.

import java.util.HashMap;

public class Practice {
    public static void main(String[] args) {
        HashMap<String, Integer> hash = new HashMap<>();
        hash.put("Test",1);
        hash.put("Test",2); //동일한 key로 입력
        int value = hash.get("Test");
        System.out.print(value); //2출력
    }
}

이러한 상황을 Hash Collision(해시충돌)이라고 한다.
구체적으로는 HashMap에 2개 이상의 Key객체가 동일한 최종 Hash값을 생성해서 동일한 버킷 위치 똔믄 배열 인덱스를 가리키는 상황이다.

• 서로 다른 2개의 입력값을 넘겼는데 같은 출력값이 오는 경우를 말한다
• 해시 함수가 무한한 입력값을 받아 유한한 개수의 출력값을 만드는 경우 비둘기집 원리에 의해 해시 충돌은 항상 존재한다
• 해시 함수를 사용한 자료구조, 알고리즘의 효율성을 떨어뜨린다

Hash Collision(해시충돌) 방지법

1. Separate Chaning : Hash값의 버킷이 이미 사용중인 경우 LinkedList를 만들어 순차적으로 저장한다.
   • 장점
     • 삭제에 대한 처리가 linked list를 타고 들어가서 삭제해주면 되기 때문에 Open Addressing보다 간단하다.
2. Open Addressing : 해쉬값의 버킷이 이미 사용중인 경우 비어있는 다른 해시 버킷에 데이터를 삽입하는 방식이다.
   • 장점
     • 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 좋다. 그러므로 데이터가 크기 않을 시 Open Addressing이 효율이 좋다.
   • 단점
     • 데이터가 적으면 효율이 좋지만 많아질시 캐시 적중률이 떨어진다, 그리고 삭제도 어렵다.
     • 중간에 삭제된 데이터가 있으면 검색을 제대로 하지 못하여 Dummy node를 삽입해 두어야 한다는 불편함이 생긴다.