[자료구조] 해시 (Hash)

_kjwoooo·2023년 8월 22일

hash 해시

개발자 전공지식(CS)

목록 보기

7/8

HashTable(해시테이블)이란?

해시 테이블은 해시 함수를 이용해 Key - Value 로 데이터를 저장하는 자료구조중 하나로 데이터를 빠르게 검색할 수 있는 특징이 있습니다.
우선 해시 테이블을 이해하기전에 Hash, HashFuntion, hashing 등의 개념을 먼저 알 필요가 있습니다.

해시 함수(Hash Funtion)

데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.

아래는 해시 테이블에 사용되는 대표적인 해시 함수들 입니다.

Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다

해싱(Hashing)

매핑 전 원래 데이터 값을 key, 매핑 후 데이터의 값을 해시 값(value)라고 하며, 이러한 매핑하는 과정을 해싱(Hashing) 이라고 합니다.

But 데이터가 많아지면 다른 Key가 같은 해시값으로 인해 충돌이 일어나는 현상이 발생합니다.

* 이러한 충돌이 발생했을 때의 해결법으로 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 등이 있습니다.

* 그럼에도 해시를 사용하는 이유는 적은 자원으로 많은 데이터를 효율적으로 관리가 가능하다는 이유 입니다.

* 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터를(key) 유한한 해시 값으로 매핑시킴.

해시테이블(HashTable) 시간복잡도

평균: O(1) - 각각의 Key값은 해시함수에 의해 고유한 index를 가지므로 데이터에 바로 접근함

최악: O(N) - 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야함

자바에서의 hash

HashMap과 HashTable

HashTable이란 JDK 1.0부터 있던 Java의 API이고, HashMap은 Java 2에서 처음 선보인 Java Collections Framework에 속한 API입니다.
HashTable 또한 Map 인터페이스를 구현하고 있기 때문에 HashMap과 HashTable이 제공하는 기능은 같습니다.

해시맵(HashMap) 사용법

HashMap 선언

import java.util.HashMap;

HashMap<Integer,Integer> map1 = new HashMap<Integer,Integer>();
// Key - Integer / Value - Integer 타입의 Entry를 갖는 HashMap 선언

HashMap<Integer,Integer> map2 = new HashMap<>();
// New에서 타입 파라미터 생략 가능

HashMap<Integer,Integer> map3 = new HashMap<>(10);
// 초기 용량(capacity) 지정

HashMap<String,String> map4 = new HashMap<String,String>();
// Key - String / Value - String 타입의 Entry를 갖는 HashMap 선언

HashMap<String,String> map5 = new HashMap<String,String>(){{
    put("Key1", "Value1");
    put("Key2", "Value2");
}};
// 초기값 지정

HashMap 값 추가

HashMap<Integer,String> aaa = new HashMap<Integer,String>();
// Key - Integer / Value - Integer 타입의 Entry를 갖는 HashMap 선언

//값 추가
aaa.put(1, "One");
aaa.put(2, "Two");
aaa.put(3, "Three");
aaa.put(4, "Four");

System.out.println(aaa);
//출력결과 : {1=One, 2=Two, 3=Three, 4=Four}

HashMap 값 삭제

// HashMap 선언, 초기값 지정
HashMap<Integer,String> aaa = new HashMap<Integer,String>(){{
    put(1, "One");
    put(2, "Two");
    put(3, "Three");
    put(4, "Four");
}};
aaa.remove(1); // key값 1 제거
System.out.println(aaa); // 출력결과 : {2=Two, 3=Three, 4=Four}
aaa.clear(); // 모든 값 제거
System.out.println(aaa); // 출력결과 : {}

HashMap에서 값을 제거하려면 key를 파라미터로 주는 remove(key) 메소드를 사용합니다.모든 값을 제거하려면 clear() 메소드를 사용하면 됩니다.

HashMap 값 출력

// HashMap 선언, 초기값 지정
HashMap<Integer,String> hm = new HashMap<Integer,String>(){{
    put(1, "One");
    put(2, "Two");
    put(3, "Three");
    put(4, "Four");
}};
System.out.println(hm); // 전체 출력 : {2=Two, 3=Three, 4=Four}
System.out.println(hm.get(3)); // Key 값 3의 Value 가져오기 : Three

//entrySet() 활용
for(Map.Entry<Integer,String> entry : hm.entrySet()) {
    System.out.println("Key :" + entry.getKey() + " Value :" + entry.getValue());
}//출력결과
//Key :1 Value :One
//Key :2 Value :Two
//Key :3 Value :Three
//Key :4 Value :Four

//keySet() 활용
for (int i : hm.keySet()) {
    System.out.println("Key :" + i + " Value :" + hm.get(i));
}//출력결과
//Key :1 Value :One
//Key :2 Value :Two
//Key :3 Value :Three
//Key :4 Value :Four

특정 Key의 Value를 가져오고 싶다면 get(key)를 사용하고, 전체를 출력하려면 entrySet() 또는 keySet() 메소드를 활용하여 Map의 객체를 반환받은 후 출력할 수 있습니다.
entrySet()은 Key와 Value로 구성된 Entry의 Set을 받기 때문에 Key와 Value가 모두 필요할 경우 사용합니다.
keySet()은 Key의 Set을 반환받기 때문에 Key 값만 필요할 경우 사용하는데, 위의 코드와 같이 get(key) 메소드를 통해 Value까지 받아올 수도 있습니다.
keySet()을 활용하여 value까지 찾을 경우, key 값을 이용해서 value를 찾는 과정에서 시간이 많이 소모되기 때문에 많은 양의 데이터를 가져와야 한다면 entrySet()이 좋습니다.

참고자료
https://velog.io/@db_jam/Java-%ED%95%B4%EC%8B%9C%EB%A7%B5HashMap-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC
https://choidr.tistory.com/entry/Hash-%EB%9E%80
https://code-lab1.tistory.com/14