해시 (Hash)

❓공부하게 된 계기

프로그래머스 해시 파트를 풀기 전 개념을 확인

❗️공부한 내용

1️⃣ Hash

➡️ 관련 자료구조를 살펴보기 전 Hash 의 개념에 대해서 알 필요가 있다.

 

① Hash 의 등장배경

➡️ 배열은 내부 인덱스를 이용하여 검색이 한번에 이루어져 빠른 검색 속도를 보이지만, 샥제&삽입의 과정에서는 그만큼 기존 원소들을 이동시켜야하기 때문에 비효율적이다.

탐색 (Search)	삭제(Delete) & 삽입 (Insert)
O(1)	O(n)

➡️ 링크드리스트는 삭제&삽입의 과정에서는 단순 참조 값을 수정하여 처리 가능하지만, 검색의 경우 처음이나 마지막 노드가 아닌 이상 순회 검색을 해야하기 때문에 비효율적이다.

탐색 (Search)	삭제(Delete) & 삽입 (Insert)
O(n)	O(1)

배열과 링크드리스트의 각 한계를 해결하기 위해 제시된 방법이 해쉬(Hash) 이다.

 

② Hash 란?

➡️ 해시는 내부적으로 Hash Table 이라고 하는 배열을 사용하여 데이터를 저장하여 빠른 검색 속도를 가지며, 삽입&삭제 과정에서는 일반 배열처럼 기존 데이터를 이동시킬 필요가 없기 때문에 간편하다.

탐색 (Search)	삭제(Delete) & 삽입 (Insert)
O(1)	O(1)

③ Hash Table

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    /**
     * The hash table data.
     */
    private transient Entry<?,?>[] table;
}

➡️ Hash Table 정의 중 앞부분 인데 앞에서 의미한 배열의 의미를 알 수 있을 것 같아서 가지고 와 보았다. Entry 객체가 들어가는 배열이라고 볼 수 있다.

➡️ Key 와 Value 가 함께 저장되는 구조이며, 일반 배열과는 다르게 순차적 저장이 아닌 전 영역에 고르게 분포되어 저장된다.

➡️ 이때 Key 값은 중복될 수 없다.

출처 : https://velog.io/@kkw9312/javaHash

④ Hash Method

➡️ 위에서 언급한 Hash 와 Hash Table 의 개념을 적용하기 위해 필요한 것이 Hash Method 이다.

➡️ Hash Table 의 경우 전 영역에 고르게 분포되어 저장된다고 했는데 hashCode() 메서드가 이를 위해 활용된다. hashCode() 는 입력값을 알고리즘을 통해 특정 길이의 숫자값으로 반환에 주는 메서드이다.

// 예시) Hash Table 의 크기 : 10

String a = "a";
String b = "b";
Stirng c = "c";

int index_a = a.hashCode(); // 결과값 : 97
int index_b = b.hashCode(); // 결과값 : 91
int index_c. = c.hashCode(); // 결과값 : 93

(결과)
a 의 인덱스 : 97 % 10 = 7
b 의 인덱스 : 91 % 10 = 1
c 의 인덱스 : 93 % 10 = 3

➡️ 결과에 따라 인덱스 1, 3, 7 에 차례대로 "b", "c", "a" 가 담기게 된다. (고르게 분포)

➡️ 이 때 index 의 중복을 최대한 막기 위해서 배열의 크기는 소수(Pime Number) 로 지정한다.

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode(); // (1)
    int index = (hash & 0x7FFFFFFF) % tab.length; // (2)
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) { // (3)
            return (V)e.value;
        }
    }
    return null;
}

➡️ 위 내용을 이해하고 나면 Hash Table 의 get 매서드를 이해하는 것도 어렵지 않을것 같다.

1) hash 값을 구한다.

2) 해당 값을 배열의 크기로 나누어 나머지 값으로 index 를 확인한다.

3) 해당 위치에 있는 객체의 hash 값이 찾던 key 의 해쉬값과 일치하고 객체도 일치하면 해당 value 값을 돌려준다. 일치하지 않으면 null

2️⃣ Map

➡️ HashMap 을 공부하기 전 인터페이스인 Map 에 대해 알 필요가 있다.

 

① 구조

➡️ 키 (key) 와 값 (value) 로 구성된 엔트리 (Entry) 객체를 저장한다. 키와 값은 모두 객체이며, 키는 중복 저장할 수 없지만 값은 중복 저장할 수 있다.

Map 기본 구조

➡️ 기존에 저장된 키와 동일한 키로 값을 저장하면 기존 값은 없어지고, 새로운 값으로 대체되며, 키끼리 또는 값끼리 묶어 Set 형태로 반환 가능하다.

 

② 구현체

➡️ Map 인터페이스의 대표적인 구현체로는 HashMap, HashTable, TreeMap, Properties 가 있다.

3️⃣ HashMap

① 선언

➡️ Map 인터페이스의 구현체로서 아래와 같이 선언 가능하다.

// 선언
Map<(key 의 Type), (value 의 Type)> map = new HashMap<>();

// 예시
Map<String, Integer> map = new HashMap<String, Integer>();
Map<String, Integer> map = new HashMap<>();

 

② HashMap 에서 중복 key 값을 확인하는 과정

HashMap 키값 확인 구조

 

③ 예제 코드

import java.util.Map;
import java.uril.HashMap;

public class HashMapExample {
    public static void main(String[] src) {
        // Map 컬렉션 생성
        Map<String, Integer> map = new HashMap<>();
        
        // (1) 객체 저장
        map.push("가", 10);
        map.push("나", 20);
        map.push("다", 30);
        // 중복에 발생 ➡️ 덮어쓰기
        map.push("가", 40);
        
        System.out.println(map.size()); // 출력 : 3
        
        // (2) 키로 값 얻기
        String key = "나";
        int value = map.get(key);
        System.out.println(value); // 출력 : 20
        
        // (3) Set 컬렉션 얻기
        Set<String> keySet = map.keySet(); // 키 값만 조회
        Set<Entry<String, Integer>> entrySet = map.entrySet(); // 모든 엔트리 조회
    }
}

4️⃣ Hash Set

① 선언

➡️ Set 인터페이스의 구현체로서 아래와 같이 선언 가능하다.

// 선언
Set<(Type))> set = new HashSet<>();

// 예시
Set<String> set = new HashSet<>();

② HashMap 에서 중복값을 확인하는 과정

③ 예제 코드

import java.util.HashSet;

public class HashSetExample {
    public static void main (String[] args) {
        // HashSet 생성
        Set<String> set = new HashSet<>();
        
        // 객체 저장
        set.add("Java");
        set.add("Python");
        set.add("C++");
        set.add("Java"); // 중복 객체이므로 저장하지 않음
    }
}

✏️ 적용 시켜본 예제

(추가예정)

🧐 추가로 궁금한 점

1️⃣ hashCode() 와 equals() 의 사용

➡️ 공부한 내용의 2️⃣-② 부분에서 hasCode() 결과값만 일치하면 되는 것이 아니라 equals() 까지 반환값이 true 여야만 중복으로 판단하는지 궁금했다. 해당 내용은 equals 와 hasCode 는 왜 같이 재정의 해야할까? 라는 모던 자바 인 액션 책 내용에서 알 수 있었다.

 

🔗 참고

① 이것이 자바다 : Ch15-4 Map 컬레션 요약 영상

(https://www.youtube.com/watch?v=y5PJ9YCuDVM&list=PLVsNizTWUw7EmX1Y-7tB2EmsK6nu6Q10q&index=149)

② Tecoble : equals 와 hashCode 는 왜 같이 재정의 해야 할까?

(https://tecoble.techcourse.co.kr/post/2020-07-29-equals-and-hashCode/)

③ Hash란 무엇일까?

(https://jroomstudio.tistory.com/10)