해시테이블

0. 해시함수

임의의 길이의 데이터를 고정된 길이의 데이터로 변환하는 함수이다

1. 해시테이블

해시함수를 통해 고정된 길이로 변환된 데이터를 인덱스로 사용하여 접근할수 있는 버킷들의 배열을 해시테이블이라고 한다. 해시함수 연산의 시간복잡도는 O(1)로, 버킷에 빠르게 접근할수 있는 장점이 있다. 다만 고정된 길이로 변환하기 때문에 서로 다른 데이터를 해시함수에 통과 시킬때, 같은 버킷으로 충돌이 일어날수 있다. 이때는 충돌된 데이터들중 찾아야 하므로 O(N)이 될수 있다. 충돌을 해결하기 위해서는 probing(근처의 빈공간에 넣자), Chaining 기법(리스트 형식으로 넣자)이 있다.

2. 자바의 HashMap 과 TreeMap 의 차이점

• HashMap HashMap은 hashcode를 통해 데이터가 삽입될 bucket를 고른다. hashCode() 메서드의 결과 자료형은 int로 O(1)을 위해선 2^32개의 배열이 필요하다. 이렇게 되면 HashMap 객체를 만들기 위해서 많은 공간복잡도를 필요로 하므로 이보다 작은 크기의 배열을 만들어 modulo 연산 기법을 활용한다. 따라서 hashcode가 같거나 hashcode의 modulo 연산 결과가 같다면 충돌이 발생할수 있다. equals() 메소드를 통해 두 데이터가 같은지 검증한다. 만약 같다면 삽입이 거부된다.

• TreeMap hashMap이 hashcode를 비교하는것과 다르게, compareTo 함수를 이용하여 정렬을 하고 삽입을 한다. 같은 hashcode를 가지지만 compareTo의 결과에 의해 다르다고 판단되면 삽입이 될수 있다. ex(0.10, 0.100)