[Java] Hash 동작방식

해시, 쉽게말하면 많은 것들이 있지만 Hash 기반으로 동작하는 hashMap에 대해서 동작방식을 정리한다.

 

Object클래스 기준, hashCode메서드에 대한 설명이다.

해당 메서드는 오브젝트의 해시코드 값을 리턴하고, 두 오브젝트가 equals를 통해 같다고 판별되면

hashcode또한 동일해야한다. equals메서드를 통해 다르다고 판별되더라도, hashcode가 꼭 달라야하는 것은 아니지만

hashCode가 다르면, 해시 테이블을 사용할때 성능상 이점이 나온다.

 

HashMap은 기본적으로 bucket배열을 16으로 설정한다. bucket이란, HashTable에 데이터를 담는 공간을 의미한다.

이 용량은 설정해 놓은 LOAD_FACTOR기준에 다다르면 자동으로 2배씩 증가한다.

용량을 작게 설정한 이유는 hashCode는 정수 범위의 값을 리턴하는데, 이 범위 전체의 배열을 만드려면 OOM이 발생될 수 있기 때문이다.

 

그럼 충돌은?

세퍼레이트 체이닝 방식을 사용한다. LinkedList로 연결되어있는 형태이다.

HashMap은 동일한 키값으로 저장이 불가하다. 만약에 key가 같은 값이라면, 최종 값으로 update를 한다.

 

put을 할때는 putVal이라는 메서드를 호출하는데, key의 해시를 추가해서 인자로 전달 된다.

putVal에는 hash값과, 넣기 위한 데이터들을 파라미터로 넘긴다.

human1,human2의 hash는 같은 값이므로, 동일한 버킷 인덱스로 접근한다.

 

없다면, 신규로 생성을 해주는데 만약에 이미 해당 버킷인덱스에 존재한다면?

hash가 같고 && equals를 하여 같은값 || key의 참조가 같다면, 동일 식별자로 판단한다

 

 

그 후, 같다고 판단이 되면 새로운 값으로 변경하는 작업을 진행한다.

 

---정리----

Hashmap은 Java2에서 나온 Collections Framework에 속한 Api이다.

HashTable은 Java1에서 나온 Api이름이다.

HashMap은 보조해시함수를 제공, 충돌가능성이 낮고, 성능상 이점을 가진다.

HashTable은 구현에 거의 변화가 없고, 해시맵은 지속 개선이 되고있다.

 

정의하자면, 키에 대한 해시값을 사용하여, 값을 저장하고 조회하며

키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 배열의 형태를 가진다.

 

해시 맵은 기본적으로 hashcode메서드가 반환하는 값을 사용하는데, int로 반환한다.

논리적으로 생성 가능한 원소의 개수가 21억을 넘을수도있고, O(1)의 탐색 효율을 보장하려면

모든 HashMap을 가지고있어야 하기 때문이다.

 

그런데 이럴경우에는 메모리 문제가 있어, 표현 정수 범위 |N| 보다 작은 M개의 원소가 있는 배열만을

사용한다.

따라서 객체에 대한 해시코드의 나머지 값을 해시 버킷 인덱스 값으로 사용한다.

 

int index =.X.hashCode() % M;

 

해시코드를 총 원소의 개수로 나눈 나머지의 값을 해시 버킷 인덱스로 사용하게 되고

associative array 구현체에서는 이렇게 메모리를 절약하게 된다.

 

해시 충돌은 다양하게 발생할 수있다.

1/M의 확률로 발생할 수 있는 충돌은 두가지 방법으로 회피가 가능하다.

 

* load factor -> 한 버킷에 몇개의 키가 매핑 되느냐

* 해시 테이블 -> 해시함수를 사용해 키를 해시값에 매핑, 이 해시값을 색인 혹은 주소 데이터의 값을 키와 함께 

저장하는 자료구조 (주소데이터 + 키)

* 데이터가 저장되는 곳  -> 버킷 or 슬롯

 

 

1)open addressing

데이터를 삽입하려는 해시 버킷이 이미 사용중인 경우, 다른 해시 버킷에 해당 데이터를 삽입 하는 방식이다.

-> 메모리 문제는 막아주지만, 해시충돌은 발생된다.

데이터를 저장/조회할때, Linear Probing, Quadratic Probing를 사용한다.

-Linear Probing
선형탐사는 , 해시값에 해당하는 버킷에 다른 데이터가 저장되 있으면 해당 해시값에서 고정폭을 옮겨 다음 해시값에 저장한다.

(주변 버킷이 채워져있을수록, 성능이 저하된다.)

-Quadratic Probing

여러개의 서로다른 키들이 동일한 초기 해시값을 갖는 것에 취약하다, 탐사 위치가 동일하기 때문에, 효율성이 떨어진다.

 

 

2)separate Chaining

각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분이다.

연속된 공간에 데이터를 저장하기때문에, openaddressing은 캐시효율이 높다.

데이터개수가 적다면, open addressing이 더 성능이 좋다.

 

 

자바에서는 seperate방식을 쓴다. open addressing 은 데이터를 삭제할때 처리가 효율적이지 않기떄문이다.

또한 세퍼레이트 체이닝은, 해시 함수를 잘 고르게 만들면, 충돌이 잘 발생하지 않도록 조정할 수있다.

 

 

Java 8 hashMap에서는 Entry 대신, Node를 사용한다.

이는 트리를 사용할 수 있는 하위 클래스인 TreeNode가 있고, 일정 개수 이상이 넘어가면, LinkedList에서

레드 블랙 트리 형태로 변경되게 된다.

 

보조 해시함수는 키의 해시값을 변경하여 해시 충돌 가능성을 줄여주는 것이다.