해시
해시의 개념
- 해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조
- 해시는 키와 데이터를 일대일 대응하여 저장하므로 키를 통해 데이터에 바로 접근할 수 있다.배열로 구현한 연락처
- 특정 데이터의 위치를 판단할 수 있는 정보가 없으므로, 선형탐색 해야 함
- 선형탐색: 배열의 처음부터 끝까지 차례대로 원하는 값을 찾는 방법해시를 적용한 연락처
- 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키-값을 저장해서 빠른 데이터 탐색 제공
- 해시테이블
- 이름 키에 해시함수를 적용하면 인덱스를 얻는다
- 몇번을 해봐도 이름의 해시함수 적용값은 인덱스가 된다.
- 이름을 가지고 바로 연락처 위치를 알 수 있다.
- 이름 자체로 인덱스를 구할 수 있다.
해시함수(정의)
- 임의의 키를 해시테이블의 인덱스로 변경해주는 함수
- 해시 테이블의 크기가 N이라면 해시함수는 0 ~ (N-1)사이 값을 내야 함
- 충돌을 최소화 할수록 좋은 해시함수
- 예)
- 이름1과 이름2는 다른 키임
- 서로 다른 키에 대해 해시 함수가 동일한 인덱스를 반환할 경우 충돌이 발생해시함수(나눗셈 법)
- h(x) = x mod k (x는 키, k는 소수)
- k로 나눈 나머지는 0 ~ k-1 이므로 해시 테이블의 크기는 k
- k가 소수인 이유는 충돌을 줄이기 위함(소수가 아니면 k주기로 해시값 반복 됨)
- 7 % 2, 짝수는 무조건 0, 홀수는 무조건 1
- k로 나눈 나머지 값을 인덱스로 사용
- 단점
- k는 소수가 있어야 나눗셈 법이 가능, 해시테이블의 크기가 커지면 더 큰 소수가 필요함
- 해시테이블의 크기가 k이면, 0 ~ k-1까지 나오는 소수가 있어야 함.
해시함수(곳셈법, 정의)
- 곱셈법은 소수를 활용하지 않고 황금비를 곱하는 방식
- a/b = a/(a+b) = 황금비, 황금비는 대략 1.6180339887...
- h(x) = (((x * A) mod 1) * m) x는 키, A는 황금 비, m은 최대 버킷의 갯수
해시함수(문자열 해싱, 해시함수 설명)
- hash(s) = (s[0] + s[1]_p1 + s[2]_p2 + ... + s[n-1]*pn-1) mod m
해시 충돌
- 서로 다른키에 대해 해시 함수 결괏값이 같은 경우 '충돌'이 발생
- 체이닝, 개방 주소법이 충돌을 처리하는 대표적인 방법해시충돌처리(체이닝)
- 충돌 발생 시, 해당 버킷에 링크드리스트로 데이터를 연결 함.
- 특정 버킷에 데이터가 N개인 경우, 원하는 값을 찾는데 O(N)이 걸릴 수 있음
해시충돌처리(개방 주소법 - 선형 탐사)
- 충돌 발생 시, 다른 빈 버킷을 찾아 충돌값을 삽입
- 최대한 기존 테이블을 사용하자는 방식 (메모리 절약)
- h(k,i) = (h(k)+i) mod m
- K는 키, I는 충돌시 이동할 버킷 수, m은 버킷 사이즈
해시충돌처리(개방 주소법 - 이중해싱)
- 용어 그대로 해시 함수를 2개 사용(경우에 따라 N개까지 확장)
해시 활용하여 문제 해결
- 키-값 쌍으로 연관된 데이터가 존재하며, 해당 값에 대한 접근이 빈번한 경우
- 중복되지 않는 키를 사용하는 경우
문제
문제 21: 오픈 채팅방
public static void main(String[] args) {
String[] record = {"Enter uid1234 Muzi", "Enter uid4567 Prodo", "Leave uid1234", "Enter uid1234 Prodo", "Change uid4567 Ryan"};
HashMap<String, String> hashMap = new HashMap<>();
for (int i = 0; i < record.length; i++) {
String[] s = record[i].split(" ");
if (!s[0].equals("Leave")) {
hashMap.put(s[1], s[2]);
}
}
ArrayList<String> answer = new ArrayList<>();
for (int i = 0; i < record.length; i++) {
String[] s = record[i].split(" ");
if (s[0].equals("Enter")) {
answer.add(hashMap.get(s[1]) + "님이 들어왔습니다.");
} else if (s[0].equals("Leave")) {
answer.add(hashMap.get(s[1]) + "님이 나갔습니다.");
}
}
String[] strings = answer.toArray(new String[0]);
for (String string : strings) {
System.out.println("string = " + string);
}
}
[출처] 코딩테스트 합격자 되기 - C++
