해시(Hash)
해시는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 의미한다.
이러한 해시는 해시 함수에 의해서 얻게 된다.
데이터의 key 값이 해시 함수를 통해 변환된 간단한 정수이고, 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용된다.
해시 함수(Hash Function)
해시 함수는 입력받은 데이터를 해시 값으로 출력시키는 알고리즘을 의미한다.
이렇게 출력된 해시 값은 알고리즘에 따라 다양한 결과를 보여주기 때문에 함수는 목적에 맞게 다양하게 설계됩니다.
해시 테이블(Hash Table)
해시 테이블은 키와 값을 함께 저장해 둔 데이터 구조이다.
데이터가 행과 열로 구성된 표에 저장되는 것과 유사하며 데이터를 저장할 때 위치는 무작위로 지정되어 작성되므로 중간에 여유공간이 발생할 수 있다.
해싱(Hashing)
해싱은 해시 함수에서 해시를 출력하고, 해시 ㅔㅌ이블에 저장하는 과정까지의 행위를 의미한다.
충돌(Collision)
해시 충돌은 2가지 경우에 해당된다.
1. 서로 다른 키가 같은 해시 코드를 반환한다.
2. 키와 해시 코드가 서로 다르지만 같은 인덱스를 환산한다.
해결 방법으로는 2가지 방법이 존재한다.
1. 분리 연결법(Separate Chaining)
배열에 LinkedList를 사용하여 동일한 인덱스를 반환하는 경우 List에 추가하는 방식을 사용하여 해시 충돌을 해결할 수 있다.
단, 동일한 인덱스에 너무 많은 데이터가 저장된다면 List를 탐색해야 하기 때문에 성능이 저하될 수 있다.
2. 개방 주소법(Open Addressing)
선형 조사법(Linear Probing)
해시 충돌이 발생한 배열 방에 다음 비어있는 배열방으로 데이터를 저장하는 방식이다.
배열의 경계를 넘어갈 경우 맨 앞으로 넘어가게 된다.
만약 비어있는 배열방이 없는 경우 빈 배열방을 탐색하는 시간이 늘어나게 된다.
이차원 조사법(Qyadratuc Probing)
선형 조사법의 단점을 보완한 방식으로 선형 조사법에서는 하나씩 배열방을 탐색했다면 이차원 조사법은 제곱으로 빈 배열방을 탐색한다.
특정 영역에 데이터가 몰려도 그 영역을 빠르게 벗어날 수 있는 장점이 있으나 동일한 인덱스를 환산할 경우 탐색해왔던 경로를 그대로 탐색하여 빈 배열방을 찾게되는 단점이 있다.
더블 해싱(Double Hashing)
두 개의 해시 함수를 사용하는 방식이다.
인덱스를 반환하여 해시 충돌이 발생하면 다른 해시 함수를 통해 이동할 폭을 얻는다.
해시 함수를 두 번 사용하다보니 이동 폭이 같을 확률이 매우 적어 서로 다른 보폭으로 빈 배열 방을 탐색하게 된다.
HashMap
자바에서 해시 알고리즘을 바탕으로 만들어진 수많은 도구 중 하나
Key와 Value 쌍으로 저장할 수 있다.
자바에서 해시 개념을 써서 문제를 풀어야 겠다는 생각이 들 때, 가장 먼저 사용하는 도구
선언 방법
import java.util.HashMap;
HashMap<String, Integer> map = new HashMap<>();
데이터 추가, 수정, 삭제, 조회(기본 CRUD)
//추가 put(key, value)
map.put("사과", 1000);
//수정 : 같은 key로 다시 put하면 값이 덮어씌워짐
map.put("사과", 1500);
//조회 get(key) => 그 키에 해당하는 value값을 반환
int applePrice = map.get("사과");
//삭제: remove(key) -> 해당 쌍을 지우고, 지운 value를 반환
map.remove("사과");
getOrDefault()
값이 없으면 에러 대신 기본값을 설정하여 카운팅할 때 편리
//fruit이 map에 있으면 그 값을, 없으면 0을 가져오고 +1을 해서 저장
//map : hashmap
map.put(fruit, map.getOrDefault(fruit,0)+1);