[JAVA] 해시(HASH) 정복
프로그래머스 알고리즘 고득점 Kit을 풀며 Hash에 대해 정리한 내용을 공유해본다.
Hash는 List의 한계를 극복하며 저장 또는 검색 등에서 자주 활용 되는 자료구조다.
그렇다면 List의 한계점부터 알아보고 넘어가자
ArrayList
사용자가 정의한 <제네릭> 객체에 맞는 값을 순차적으로 저장하고 중복 삽입 가능하다. 단, 수정 시 배열을 새로 생성해서 배열채로 집어 넣기 때문에 속도가 느리다.
- for each문에서 데이터 검색 시 Hash보다 ArrayList가 더 빠르다던데?
-> ArrayList는 순차적인 데이터 구조를 가지기 때문에, 순서가 중요하거나 순차적으로 데이터에 엑세스 해야 하는 경우 더 빠를 수 있다.
LinkedList
추가/삭제 시 인근 노드들의 참조 값만 수정해 줌으로써 빠른 처리가 가능하지만 데이터를 검색할 경우 해당 노드를 찾기 위해 처음부터 끝까지 순회 검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어지는 구조이다.
*즉, ArrayList의 느린 데이터의 수정, LinkedList의 느린 탐색 속도를 개선한 것이 Hash이다.
해시(Hash)
key값을 해시함수를 사용해 특정 해시값으로 계산하고 그 해시값을 인덱스로 변환하여 key와 value를 저장하는 자료구조이다. 때문에 기존 데이터를 밀어내거나 당기는 작업이 필요없어 수정과 탐색이 빠르다.
해시 함수(Hash Method)
데이터의 고유한 숫자 값을 만들어 인덱스로 사용하는 알고리즘을 구현한 함수를 의미한다.(데이터가 저장되어 있는 곳을 알려줌) 해시 함수에 의해 반환된 데이터의 고유 숫자 값은 Hash Code라고 한다.
해시 코드(Hash Code)
같은 입력(키)에 대해 항상 동일한 해시 코드가 생성 되며, 이는 해시 테이블 내에서 데이터의 저장 위치(인덱스)를 결정하는 데 사용된다.
1
2
3
4
5
String s1 = "string";
String s2 = "string";
System.out.println(s1.hashCode()); // -731585331
System.out.println(s2.hashCode()); // -731585331
System.out.println(s1.equals(s2)); // true
*해시 코드와 인덱스의 차이점에 대해 헷갈려 할 분들을 위해
해시 코드와 인덱스는 밀접한 관련이 있는데, 해시 코드는 데이터의 식별자이며, 이것을 사용해 데이터의 저장 위치(인덱스)를 찾아간다.
그림으로 이해하면 더 쉬울테니 아래 해시 테이블 예시를 보자.
해시 테이블(Hash Table)
key와 value를 함께 저장해 둔 데이터 구조를 말하며 Hash가 내부적으로 사용하는 배열이다. 위치가 무작위로 지정되기 때문에 중간에 여유 공간이 발생할 수도 있다.
- 버킷(bucket) : 하나의 주소를 갖는 파일의 한 구역, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수
- 슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간, 한 버킷 안에 여러 슬롯이 있다.
해싱(Hashing)
해시 함수를 이용해 해시 코드를 출력하고, 데이터를 해시 테이블에 저장하기까지의 행위를 말한다.
🔎종류
HashMap
key와 value를 개발자가 직접 기입하고 key의 중복을 배제한다.(value는 허용) Map은 key와 value로 구성된 Entry 객체를 저장하는 구조를 가진다. 여기서 key와 value는 모두 객체로 이루어져 있다.
주요 메소드
| 메소드 | 설명 |
|---|---|
| map.put(key, value); | 값 넣기 |
| map.get(key); | 해당 key의 value를 가져옴 |
| map.size(); | Map 크기 확인 |
| map.replace(key, value); | 해당 key의 값을 새 value로 대체 |
| map.containsKey(key); | 해당 key가 들었는지 확인 |
| map.containsValue(value); | 해당 value가 들었는지 확인 |
| map.isEmpty(); | Map의 크기가 0인지 확인 |
| map.remove(key); | 해당 key와 value 삭제 |
| map.getOrDefalut(key, defalut); | 해당 key가 존재하면 대응하는 value 값을, 없다면 defalut 값을 가져옴 |
| map.entrySet(); | key와 value 값을 전부 가져옴 |
| map.keySet(); | key의 값만 전부 가져옴 |
- 이해하기 쉽게 파라미터를 key와 value로 표시함
LinkedHashMap
순서를 가진다는 점이 HashMap과의 차이점이다.
HashSet
key 값으로 삽입되는 객체 자체를, value 값으론 HashSet 내부 구현 코드에서 미리 선언해둔 dummy 객체를 사용한다. (내부적으로 HashMap을 사용)
순서없이 배열에서 중복된 값을 없앤 새로운 데이터 셋을 만들고자 할 때 유용하다.
주요 메소드
| 메소드 | 설명 |
|---|---|
| set.add(E e); | 값 넣기 |
| set.addAll(Collection<? extends E> c); | 제공한 컬렌션의 값을 합침 |
| set.remove(Object o); | 해당 value 삭제 |
| set.removeAll(Collection<? extends E> c); | 제공한 컬렉션의 값을 모두 지움 |
| set.size(); | set 크기 확인 |
| set.contains(Object o); | 해당 value가 들었는지 확인 |
add()메소드로 데이터를 저장할 때, 내부적으로 hashCode() 메소드로 해시값을 생성하고 eqauls() 메소드를 통해 중복된 객체가 있는지 확인한다.
LinkedHashSet
순서를 가진다는 점이 HashSet과의 차이점이다.
HashTable
HashMap과 동일한 특징을 가지지만, Thread-Safe하여 동기화를 지원하는 점이 차이점이다.
HashMap은 key와 value가 같이 들어가기에 알고리즘을 풀며 key가 필요없는 경우 HashSet을 사용했다. 그런데 다른 사람 풀이를 보니 굳이 key가 필요없음에도 HashMap을 사용하는 것을 보고 알아보니 HashMap이 HashSet보다 더 빠르고 데이터의 유일함을 유지하기 위해 HashMap이 더 선호된다고 한다.
해시의 주요 용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
예를 들면, 캐시 구현과 같이 데이터를 빠르게 검색하고 유지 관리해야 하는 경우가 되겠다.