JAVA HashMap 동작
HashMap은 키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array라고 할 수 있다.
암호학이나 보안에 관심이 있는 사람이라면 Hash라는 것이 무엇인지 알고 있을 것이다. 예를 들어 어떤 문자열을 어떤 해시 함수를 통하면 일정한 길이의 해시된 값이 나오는데 이 값은 어떤 방법으로도 복원할 수 없다고 알려져 있다. 하지만 값에 따라 해시 값이 같은 즉 해시의 충돌이 발생할 수 있다. 해시 충돌이 없는 해시 함수를 완전 해시 함수라고 칭하지만 완전한 해시 함수를 구현하는 것은 사실상 불가능하다고 알려져 있다.
해시의 충돌을 막는 방법으로는 여러가지가 존재한다. 가장 일반적인 방법은 해시 함수의 표현 정수 범위 N보다 작은 M개의 원소가 있는 배열만을 사용하는 것이다.
즉, Index = hashCode(X) % M; 의 형태로 인덱스를 정할 수 있고 이 인덱스를 해시 버킷에 인덱스 값으로 사용한다.
하지만 이렇게 해도 1/M의 확률로 해시의 충돌이 발생하게 된다. 따라서 Separate Chaining 방식을 사용한다. 만약 버킷의 인덱스에 데이터가 들어있다면 해당 버킷에 linkedList를 생성하여 연결을 시키는 것이다. 이 방식은 현재 JAVA HashMap에서 사용하는 방식이다.
암호학이나 보안에 관심이 있는 사람이라면 Hash라는 것이 무엇인지 알고 있을 것이다. 예를 들어 어떤 문자열을 어떤 해시 함수를 통하면 일정한 길이의 해시된 값이 나오는데 이 값은 어떤 방법으로도 복원할 수 없다고 알려져 있다. 하지만 값에 따라 해시 값이 같은 즉 해시의 충돌이 발생할 수 있다. 해시 충돌이 없는 해시 함수를 완전 해시 함수라고 칭하지만 완전한 해시 함수를 구현하는 것은 사실상 불가능하다고 알려져 있다.
해시의 충돌을 막는 방법으로는 여러가지가 존재한다. 가장 일반적인 방법은 해시 함수의 표현 정수 범위 N보다 작은 M개의 원소가 있는 배열만을 사용하는 것이다.
즉, Index = hashCode(X) % M; 의 형태로 인덱스를 정할 수 있고 이 인덱스를 해시 버킷에 인덱스 값으로 사용한다.
하지만 이렇게 해도 1/M의 확률로 해시의 충돌이 발생하게 된다. 따라서 Separate Chaining 방식을 사용한다. 만약 버킷의 인덱스에 데이터가 들어있다면 해당 버킷에 linkedList를 생성하여 연결을 시키는 것이다. 이 방식은 현재 JAVA HashMap에서 사용하는 방식이다.
