[java] hash

코딩테스트를 하다보면, 해시방법을 쓰라는 힌트를 볼 때가 있습니다.

HashMap, HashSet의 Hash를 의미하는 거 같긴한데 구체적으로 어떤 방식일까요? 🤔

Hash란?

임의의 길이의 데이터(key)를 고정 길이의 데이터(hash)로 매핑해주는 방법입니다.

자세히 설명하기 전 다른 자료구조 형식을 먼저 알아보도록 하겠습니다.

자바에서 Collection이나 Map같은 클래스를 사용하면 동적으로 데이터를 저장할 수 있는데요.

그중 Hash와 대비되는 자료구조 ArrayList와 LinkedList를 보면 아래와 같은 장단점을 갖고 있습니다.

ArrayList

장점: 빠른 검색 속도 단점: 느린 추가 삭제

내부 인덱스를 이용해 검색이 이뤄지기에 검색이 빠르지만 데이터 추가 삭제시 인덱스를 변경해야 되서 시간소모가 큽니다.

LinkedList

장점 : 빠른 추가 삭제 단점 : 느린 검색 속도

LinkedList는 추가 삭제시 인근 노드들의 참조값만 수정해 빠른 처리가 가능하지만 데이터를 검색할 경우 인덱스가 없어 해당 노드를 찾기 위해 전체를 순회해야 됩니다. 따라서 데이터의 양이 많아지면 시간이 오래 걸리고 비효율적입니다.

💥 이런 한계를 극복하기 위해 나온 방법이 Hash입니다.

Hash 자료구조

key - value 사용 빠른 검색, 추가, 삭제 HashSet, HashTable, HashMap

Hash는 내부적으로 배열을 사용해 데이터를 value에 저장하기 때문에 빠른 검색이 가능합니다.

그리고 Hash Code라는 고유값 key를 인덱스처럼 사용하기 때문에 데이터 추가 삭제시에도 인덱스가 변경되지 않아 효율적입니다.

1. HashTable

key-value인 Map 구조이며 아래와 같이 사용합니다.

Map<Integer, String> table = new HashTable<>();
table.put(1,"yes");
table.put(2,"no");

HashTable은 동기화를 지원하며 thread-safe하기 때문에 멀티스레드 환경에서 사용하기 좋습니다. key와 value엔 null값이 들어갈 수 없습니다.

2. HashMap

HashTable과 마찬가지로 map 구조고 사용방법도 비슷합니다.

Map<Integer, String> map = new HashMap<>();
map.put(1,"yes");
map.put(2,"no");

하지만 다음과 같은 차이점이 있습니다.

HashMap은 key 값이나 value값에 null이 들어갈 수 있습니다.

비동기식이라 단일 스레드 환경에서 사용하기 좋습니다. 따라서 스레드의 작업완료를 차례대로 기다려야 되는 멀티 스레드 HashTable보다 빠릅니다.

3. HashSet

위의 자료구조들과 달리 Set구조로 key값만 저장됩니다.

Map<Integer> set = new HashSet<>();
set.add(1);
set.add(2);

Hash 용어정리

• key : 매핑 전 입력 데이터

• HashCode : 매핑 후 출력 데이터의 값

• Hash Method : hashCode(), key를 Hash Code로 반환해줌

• Hashing : 위의 매핑 과정

• value : 저장소(버킷, 슬롯)에 최종적으로 저장되는 값 - hash와 매칭됨

Hash 특징

• 동일한 입력값에 동일한 출력값 보장

• 출력 데이터로 원본 입력 데이터 값을 알 수 없음

• 해시 함수의 알고리즘이 일반적으로 복잡하지 않기에 메모리 자원 소모가 크지 않음

• 입력값 범위보다 출력값의 범위가 좁아서 드물게 다른 입력값에 동일한 출력값을 가질 수 있음 -> 충돌

참조

💻 Hash의 개념 및 설명

💻 해시 테이블

💻 HashSet

💻 Hash 충돌,체이닝