3주차. 해시
3-4. 해시 함수에서의 문자열
=>Hash에 문자열을 넣는 경우, 출력이 어떻게 되는가?
-
해시가 정수를 출력하는 이유는 index로 받기 때문에!
-
문자열 출력
String s = "My name is Rob";
char c = s.charAt(6);(1)
int i = s.charAt(6);(2)
// result
System.out.println(c);// m
System.out.println(i);// 109 => m을 유니코드(+ASCII)값으로 변환하여 숫자형태로 출력 -모든 문자(ASCII의 경우,영어에서 사용하는 문자 한정)는 숫자로 표현 가능하다(by ASCII,유니코드)
- 참조 - ASCII,유니코드
https://m.blog.naver.com/ycpiglet/222146759413
- 문자열을 해시로 표현
-유니코드로 변환하여 나온 숫자들을 합한 뒤 문자열을 숫자로 표현(숫자(합)는 Key가 되어 문자열을 배열에 넣는다)
하지만 이러면 this뿐만 아니라 hits, tish 등 다른 문자열도 유니코드 값들의 합이 같아지는 경우가 발생한다!(즉, 해시 충돌 발생!)
===>SO, 문자열 내 숫자를 처리할 때 서로 다른 값이 나오도록 하는 방법을 찾아야 한다
ex) 문자의 위치만큼 제곱하여 합을 구한다
public int hashCode(String s) {
int g=31;
int hash=0;
// 문자열을 숫자로 나타내기
// 상수 g를 문자의 위치만큼 제곱한 뒤 곱합니다.
for (int i=0; i<s.length; i++)
hash = g*hash + s.charAt(i);
return hash;
}생각해보기)-문자열을 해시에 저장할 때, 해시 충돌을 방지하는 다른 방법에는 어떤 것이 있을까요?
3-5. 해시 크기 최적화(Compressing HashCode)
-목적: 해시 충돌 방지
-
HashCode함수
-객체 한 개를 받고 정수를 반환
-정수는 나중에 배열의 인덱스(key)로 사용
=> 여기서 정수는 크기가 설정되어 있지 않아 문제(ex 해시충돌, 음수 발생)가 발생하지 않도록 최적화가 필요 -
방법1 - 해시의 크기를 홀수로 설정
===> '%'라는 연산자를 사용하여 결과가 다양해짐 -
방법2 - 해시의 크기를 소수로 설정
===> 나머자가 다양해짐
cf)
-'해시 == 테이블'
-되도록 반환값인 정수는 양수로 설정하는 편이 좋다!
그 외에도 방법은 존재
생각해보기)-해시의 크기를 최적화하는 방법에는 어떤 것이 있을까요?
3-6. 양수로 변환
-음수도 양수로 표현한다(by 2의 보수)
- 8-bit 2's complement
-8bit로 된 부호가 있는 수를 표현하는 방법
-첫 bit가 0이면 양수, 1이면 음수
=> Hashcode의 반환값은 (음수 OR 양수)이지만 해시에 맞게 조정되는 것
-수 표기는 16진법
실행코드)
String s = "My name is Rob";
// data의 index 결정
int hashval = data.hashCode(s);
hashval = hashval & ox7FFFFFFF; // 해시값을 양수로 변환
hashval = hashval % tableSize; // 결과를 해시 크기만큼 %로 연산- 이를 통해 받은 정수는 양수로 변환한 뒤, KEY가 되어 DATA를 배열(해시 크기 내에서)의 어느 위치에 넣을지 결정한다!
KEY - 테이블 내 테이터를 가리킬 위치
생각해보기)-값을 양수로 변환해야 하는 이유는 무엇인가요?
