JAVA] HashMap을 알아보자

Map

map은 key-value를 저장하는 ADT이다 .같은키를 가지는 pair은 최대 한개만 존재한다.

키는 중복이 불가능하지만 value는 중복이 가능하다.

---

맵은 언제쓸까?

예를들어 전화번호부를 저장할때 ( key: 전화번호부 value: 이름)

투표와 투표수를 저장할때

등등이 있다.

---

일단hash, hashmap과hashTable, hash function, hashing은 뭐야.

Hash란 데이터를 다루는 기법중 하나이며, 검색과 저장이 아주 빠르게 진행되는 특징이 있다. 데이터를 검색할때 사용할 key와 실제 데이터값이 한쌍으로 존재하고 key값이 배열의 인덱스로 변환되기 때문이다. 시간복잡도는 O(1)이다. 

 

해쉬함수(hash function는 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

매핑전 원래 데이터값을 Key, 매핑후의 데이터 값을 Hash value(해쉬값)또는 해시코드라고 하며, key와 value로 매핑되는 과정 자체를 해싱이라고 한다

 

자바에서 hashMap과 hashTable이 각각 존재한다.

해시테이블과 해시맵은 차이점이 존재한다.

자바에서 해쉬테이블이 있지만 오래된 레거시가 아니면 잘 사용하지 않는다.

hashTable대신 ConcurrentHashMap를사용하는데, concurrentHashMap이 성능적으로 우수하기 때문이다.

1. HashMap
   1. key와 value에 null을 허용한다
   2. 동기화를 보장하지 않는다. 

      💡 해쉬맵은 thread - safe하지 않아 싱글스레드환경에서 사용하는게 좋다. 한편, 동기화 처리를 하지 않기 때문에 데이터를 탐색하는 속도가 빠르다. 결국 HashTable과 ConcurrentHashMap보다 데이터를 찾는 속도는 빠르지만, 신뢰성과 안정성이 떨어진다.

2. HashTable
   1. key 와 value에 null을 허용하지 않는다.
   2. 동기화를 보장한다

   💡 HashTable은 thread-safe하기 때문에, 멀티 쓰레드 환경에서 사용할 수 있다. 이는 데이터를 다루는 메소드(get(), put(), remove() 등)에 synchronized 키워드가 붙어 있다. 해당 키워드는 메소드를 호출하기 전에 쓰레드간 동기화 락을 건다. 그래서 멀티 쓰레드 환경에서도 데이터의 무결성을 보장한다. 그러나, 쓰레드간 동기화 락은 매우 느린 동작이라는 단점이 있다.

3.  ConcurrentHashMap

1. key 와 value에 null을 허용하지 않는다.
2. 동기화를 보장한다

💡 ConcurrentHashMap은 thread-safe하기 때문에, 멀티 쓰레드 환경에서 사용할 수 있다. 이 구현체는 HashMap의 동기화 문제를 보완하기 위해 나타났다. 동기화 처리를 할 때, 어떤 Entry를 조작하는 경우에 해당 Entry에 대해서만 락을 건다. 그래서 HashTable보다 데이터를 다루는 속도가 빠르다. 즉, Entry 아이템별로 락을 걸어 멀티 쓰레드 환경에서의 성능을 향상시킨다.

---

HashMap(Hash table)

배열과 해시함수(hash function)를 이용하여 map을 구현한 자료구조

일반적으로 상수시간으로 데이터에 접근하기때문에 빠르다.

해쉬함수의 가장 중요한점은 고유한 인덱스를 만드는것이다.

 

해시테이블은 키를 해시함수(hash function)로 계산해서 그 값을 배열의 인덱스로 사용한다.

이때 해시함수에 의해 반환된 데이터의 고유 숫자값을 해시값, 또는 해시코드라고 한다.

즉 key값을 해시함수를 통해서 배열의 인덱스로 바꿔주고 그 자리에 데이터를 저장한다.

중복되는 인덱스가 발생한다면 이는 충돌로 이어진다.

 

해쉬테이블안에서 해쉬 펑션은 어떻게 동작할까?

어떠한 임의의 데이터 예를들어 “아이폰”이라는 Key가  hash function에 들어갔을때 정수값 4310이 output으로 나온다고 가정해보자. 

이때 나오는 4310이 바로 hash값이다. 

 

해쉬테이블은 어떻게 동작할까

hashMpa.put(”test”,”값”)을 입력했다고 하자.

hash function 에 넣엇을 때 output으로 hash 202라는 정수값이 나왔다.

이 202를 capacity로 나눈값이 바로 인덱스이다.

 

충돌 (Collision)

key 는 다른데 hash가 같을때를 얘기하는것이다

1. open addressing(linear probing)바로 다음에 비어있는 공간에 데이터를 넣는것이다.
2. 인덱스가 같은값으로 두개가 나왔을 때, 해쉬충돌이 발생하면
3. separate Chaining 분리연결법근데 다른 키를 해시펑션에 결과값으로 5가 똑같이 나왔다.그러면 키의 값을 비교해서 같은 키이면 값을 변경한다.이때 separate chaining은 먼저들어온값을 저장하고 키 밸류 페어를 리스트방식으로 같은 인덱스에 집어넣는다.키 벨류페어를 linked list로 저장한다.
4. jdk내부에서는 이 방식을 사용하고 있다.
5. 그러나 키가 같지 않다면 해시충돌이 일어난다.
6. 같은 인덱스에 2개의 값이 들어가게 된결과가 나온것이다.
7. key를 hash function에 넣었더니 37이 해쉬값으로 나왔고 capacity로 나눴더니 5로 나왔다.

Capacity ,Load factor은 뭐야 

capacity는 해시의 크기이다.

hashMap api를 보면

HashMap의 기본 생성자에서 capacity는 16, load factor는 0.75로 생성됩니다.

라고한다. 이를 자세히 이해해보자.

자바에서 해시맵의 크기는 초기용량(capacity)와 로드팩터(load factor)을 설정하여 제어할 수 있다.

해시맵은 내부적으로 배열을 사용하여 요소를 저장하고, 배열의 크기는 초기용량으로 설정된다.

기본적으로 해시맵은 초기용량이 16이며 요소개수가 일정수중 이상으로 증가하면 자동으로 배열의 크기를 조정하며 저장공간을 확장한다.

이 과정을 리해싱(rehashing)이라고 한다.

다시 얘기하면 해시맵의 초기 크기는 16개의 인덱스를 가진 배열로 이루어져있고 배열이 75%이상 차면 크기를 조정한다는 말이다.

자바에서 해시맵의 크기를 개발자가 직접 제어하는 방법은 없을까,

**HashMap<KeyType, ValueType> hashMap = new HashMap<>(32);**

와 같이 생성자에 초기 용량을 전달하여 hashMap을 생성하는 방법이 있다.

HashMap<KeyType, ValueType> hashMap = new HashMap<>(16, 0.5f);

위와같이 로드팩터를 조절할수도 있다.