*TIL 66에서 정리한 자료구조 강의 이어서 정리
데이터를 저장하기 위해 배열이 존재한다
전화번호를 키로 사용한다고 가정했을때,
값은 전화번호와 연관된 사람 key, phone, numbers 등이 있다
전화번호를 키로 쓰기에 너무 길다고 판단할 수 있다
-> 전화번호를 받는 해시함수를 구현
-> 전화번호를 세 숫자로 잘라서 합한다고 가정하고 키 값을 생성한다
생기는 문제점
다른 사람의 번호를 추가 할 때,
두 개의 키가 같은 배열안에 위치한다
-> 충돌이 발생
해시 충돌
서로 다른 값을 가진 키가 일치하는 경우를 말한다
배열에 두 키가 같은 공간에 들어갈 수 없기 때문에 충돌이 발생한다
folding : 긴 숫자를 작은 숫자로 분해한다 -> 작은 숫자들의 합을 사용할 수 있다
숫자가 무작위가 아니기 때문에 배열의 인덱스 또한 무작위로 생성되는 것이 아니다
-> 충돌을 피하고자 함수를 구현할 때 어떻게 분포를 더 펼칠 수 있는지 고려해야 한다
무작위로 숫자를 할당한다면 후에 원래 값을 알 수 없어지기 때문이다
해시에 저장하고 싶은 문자열이 여러 개 있을 때
문자열을 숫자로 바꾸어야 하며 숫자는 정수여야 한다 //배열에 넣기 위함
아스키 코드 : 영어만 표현
유니코드 : 모든 문자를 표현
문자열을 위한 hashCode
문자열 this를 유니코드로 변환 할 때
116 104 105 115 를 모두 더해서 배열에 넣을 키 값인 440이 나오게 된다
이 방식의 경우 hits, tish 또한 값은 키 값이 나오게 된다
-> 문자열을 표현하기 위한 좋은 방법이 아니다
다른 값이 나오게 하기 위해 각 문자의 위치를 사용한다
-> 어떤 상수를 문자의 위치만큼 제곱한 뒤 그 수를 곱한다
문자열 값이 116일때 위치인 g를 곱하여 키 값을 구한다
이러한 방법을 쓰면 this와 tish가 서로 다른 키 값을 갖게 만들 수 있다
문자열을 위한 hashCode 구현
public int hashCode(String s) {
int g = 31;
int hash = 0;
for(int i = 0; i<s.length; i++) {
hash = g * hash + g.charAt(i);
return hash;
}
위 방식의 장점
- 문자들의 순서에 따라 다른 값을 반환하며 해시 충돌을 방지할 수 있는 방식이다
- 비교적 계산 속도가 빠르다
- 긴 문자열의 경우 subString()을 사용하여 줄여서 계산한다
해시의 충돌을 막기 위한 방법
문자열을 배열의 인덱스로 사용하기 위해서는 정수로 변환해야 한다
이때 해시 충돌을 막기 위해서 해시(테이블)의 크기를 최적화 해야 한다
1. 테이블의 크기를 홀수로 정한다
-> % 연산자를 사용했을 때 다양한 결과가 나오게 한다
2. 테이블의 크기를 소수로 정한다
-> 나머지가 다양한 숫자가 나오게 할 수 있다
**hashCode에서 반환되는 정수가 음수일 수도 있다
자바에서는 -10 % 3 의 값으로 -1을 반환한다
-> hashCode에서 반환된 정수를 양수로 바꿔야 한다
hashCode를 양수로 반환하는 법
data의 인덱스 결정
public int hashCode(String s) {
int hashval = data.hashCode(s);
hashval = hashval & 0x7fffffff;
hashval = hashval % tableSize;
}
LoadFactor 메서드
LoadFactor(적재율)는 해시에 데이터가 얼마만큼 있는지 알려준다
적재율 : 항목 수를 자료구조의 크기만큼 나눈값이다
적재율의 크기에 따라 해시 충돌이 일어나지 않도록 해시의 크기를 조절한다.