해시맵

해시맵과 해시테이블

해시 테이블은 JDK1.0부터있던 자바 api이고 해시맵은 java2부터 자바 collection 프레임워크에 속한 api이다. 보조 해시함수를 사용하여 해시 테이블보다 해시 충돌이 덜발생하나 기능은 거의 같다. 다만 해시맵은 지속적으로 개선하고 있으나 해시테이블은 거의 동일하다. 해시맵은 병렬처리를 하지 않고 null 값을 허용한다. 해시테이블은 병렬 처리 하고 null을 허용한다.

 

해시맵의 정의

키에 대한 해시 값을 이용하여 값을 저장하고 조회하며, 키-값 쌍의 수에 따라 동적으로 크기를 증하가하는 associate array(=Map, Dictionary, Symbol)이다.(해시 맵에서는 assiciate array를 저장하기 위해 map이라는 용어를, 해시테이블에서는 Dictionary라는 용어를 쓴다.)

함수에서와 같이 키 집합인 정의역과 값 집합인 공역에 대응하는 해시 함수를 사용한다.

해시함수는 각 객체의 hashCode() 메서드를 반환하는 값을 사용한다. 결과 자료형은 int이다. 따라서 2의 32승 이상의 객체보다 많은 객체를 만들 수 없다. 또한 해시 맵에서는 메모리를 절약하기위해 함수의 정수 표현범위 |N|보다 작은 M개의 원소개 있는 배열로 해시코드의 나머지 값을 해시 버킷 인덱스 값으로 사용한다.

int index = X.hasCode() %M;

해시 함수

- 같은 자리에 여러 키가 해시되는 것을 막기 위해 골고루 저장될 수 있도록 적용하는 함수.

- x.hashCode()%M으로 인덱스를 결정 후에도 많이 몰리는 것을 대비하여 보조 함수를 사용한다.

- 보조 함수

(h=key.hasCode()) & (h>>16)

- 좋은 해시 코드는 충돌을 최소화하는 방향으로 설계해야한다. 

해시 충돌 해결 기법

 

1. Open Addressing

- 연속된 배열에 저장. 이미 값이 있으면 다른 배열에 저장.

- 데이터 개수가 작을 때 유용

 

2. seperate Chainig

- 추가적인 메모리를 사용하여 버킷에 값이 있으면 링크드 리스트로 저장하는 방식.

- 데이터 수가 8개 이상이면 트리 형태 ->6개 이하이면 링크드 리스트로 바뀜

- 동적 리사이징-> 초기 버킷(배열)의 크기는 16으로 설정되어있고, 값이 증가하면 2배씩 증가한다. 증가 시 기존 배열의 두배의 크기 새로운 배열에 기존 값을 복사하는데, 값이 클 수록 성능 문제를 야기한다. 따라서 초기에 버킷 사이즈를 지정하는 것이 좋다.

시간 복잡도

- 해싱의 평균 시간 복잡도 O(1)

- 해싱 최악 시간복잡도 O(n)

 

- 체이닝을 이용한 해싱맵의 시간 복잡도

• 최악: 한 슬롯에 모든 원소들이 연결리스트로 들어갈떄 O(n)
• 평균: 해당 술롯에 접근하기위해 O(1)이 걸리고 리스트 탐색 O(a) => O(1+a)

 

 

 

 

 

 

 

 

 

 

 

 

 

출처)

https://d2.naver.com/helloworld/831311

https://m.blog.naver.com/weplayicecream/221467971945