HashMap
HashMap은 Map을 구현했으므로 키와 값을 묶어서 하나의 데이터로 저장한다는 특징을 갖는다.
그리고 해싱(Hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.
HashMap은 키와 값을 각각 Object타입으로 저장한다. 즉, (Object, Object)의 형태로 저장하기 때문에 어떠한 객체도 저장할 수 있지만 키는 주로 String을 대문자 또는 소문자로 통일해서 사용하곤 한다.
키(key) : 컬렉션 내의 키(key) 중에서 유일해야 한다.
값(value) : 키(key)와 달리 데이터의 중복을 허용한다.
Hashing
해싱과 해시함수
해싱이란 해시함수(Hash function)를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다.
해시함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.
해싱에서 사용하는 자료구조는 다음과 같이 배열과 링크드 리스트의 조합으로 되어 있다.
저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그곳에 연결되어 있는 링크드 리스트에 저장하게 된다.
다음 이미지는 검색과정을 보여준다.
- 검색하고자 하는 값의 키로 해시함수를 호출한다.
- 해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 링크드 리스트를 찾는다.
- 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.
링크드 리스트는 검색에 불리한 자료구조이기 때문에 링크드 리스트의 크기가 커질수록 검색속도가 떨어지게 된다.
이는 하나의 서랍에 데이터의 수가 많을 수록 검색에 시간이 더 걸리는 것과 같다.
반면에 배열은 배열의 크기가 커져도, 원하는 요소가 몇 번째에 있는 지만 알면 아래의 공식에 의해서 빠르게 원하는 값을 찾을 수 있다.
배열의 인덱스가 n인 요소의 주소 = 배열의 시작주소 + type의 size * n
.jpg)