[Java] HashMap 정리

HashMap

key 와 value를 이용해 데이터를 저장하는 자료 구조

• 기존의 HashTable을 베이스로 하여 Collections의 Map 인터페이스를 implement하였다.
• key를 이용한 조회, 수정, 삭제가 용이하다 (빠르다)
• key는 Unique 해야 한다 : key를 해싱에 이용하기 때문

📌 HashTable과 다른점

1. key와 value 에 null 허용

2. unsynchronized

   여러 쓰레드에서 동시에 같은 HashMap에 접근하여 값을 수정하게 되면 의도한 결과와 다른 결과를 볼 수 있다..

• Thread-safe 하지 않다. (Multi-thread 환경에서 사용하면 안된다.)
• Multi-thread 환경이 아니면 HashTable 보다 빠르다.
  

// 멀티 스레드 환경에서 사용시 권장 방법 (java docs 참고)
Map m = Collections.synchronizedMap(new HashMap(...));

📌 HashMap의 구조

• 배열과 LinkedList의 조합으로 이루어져 있다.
• 배열에는 LinkedList의 주소가 저장되어 있고, 배열의 위치는 key로 Hash Function을 돌린 결과로 알 수 있다.

  배열의 장점인 빠른 조회와 LinkedList의 장점인 비순차적인 데이터의 빠른 수정을 합친 자료구조 이다..

📌 해싱

해싱

• 해시 함수를 이용해 데이터를 해쉬테이블에 저장하는 기법
• key를 매개체로 Hash Function을 돌린 값을 데이터 저장 위치에 사용한다. 하여, key 값만 알고 있으면 데이터를 빠르게 찾을 수 있다.

해시함수

• 해시 값을 만들기 위해 사용하는 함수 (알고리즘에 따라 다른 값)
• 동일한 값에 중복된 해시 값을 반환하지 않도록 해시 알고리즘을 짜는 것이 중요하다.
• Collection프레임워크에서는 해싱을 구현할 때, Object 클래스의 hashCode()를 해시 함수로 사용한다.
  • Object에 기본 정의된 hashCode()는 객체의 주소를 이용해 해시코드를 만들어 낸다.
  • String 클래스의 경우 hashCode()로 문자열을 사용한다. 그래서 동일한 문자열을 가지면 해시값도 동일하다.

사용자 정의함수 만들시 equals()와 hashCode()를 같이 override 하는 이유

• equals()를 override하는 이유는 자바에서 동등성 비교에 사용되는 함수인 equals()를 사용했을 때 같은 값임을 반환하기 위해서 이다.
• hashCode()를 override하는 이유는 해싱 기법을 사용하는 자료구조를 이용할 때 equals()의 결과와 동일한 결과를 반환하기 위해서 필요하다.

  의도한 대로 객체가 동등성을 유지하도록 하기 위해 두 함수 모두 같이 override 해야하는 것이다..

참고자료

• 자바의 정석
• java api docs