오늘 배운 자료구조 HashTable에 대해 적어보려 한다.
간단한 해쉬 함수
String name = "Donuts";
(int)(name.charAt(0)) % 20 //8
Key가 문자열일 때, 맨 앞글자를 숫자로 변환해 Division 기법을 사용하여 Key에 대한 주소(인덱스 번호)계산.
Q. 원하는 요소를 찾을 때, 연결 리스트와 해시의 시간 복잡도?
A. 연결 리스트는 O(n), 해시는 O(1)
Q. 해시 함수를 작성할 때, 코드를 새로 실행하면 객체가 같더라도 다른 값이 나올 수 있다. 왜?
A. 객체의 hashcod 함수는 객체의 (힙)메모리 상의 주소값을 반환한다. 때문에 같은 객체이더라도 코드가 새로 실행될 때 마다 메모리 주소값이 변경되어 다른 값을 반환하게 된다. Object 클래스의 toString, equals, hashCode와 같은 메소드들은 오버라이딩을 하지 않으면 기본적으로 메모리 위치를 기반으로 코드가 실행된다.
Q. 해쉬 충돌을 방지하기 위해 해시의 크기를 최적화하는 방법
A.
1. 해시의 크기를 홀수로 설정하여 % 연산자를 사용했을 때 다양한 결과가 나오게 한다.
2. 해시의 크기를 소수로 설정하여 나머지가 다양한 숫자가 나오게 한다.