[CS/자료구조/Java] 해시테이블

해시테이블

해시테이블은 데이터를 key-value 쌍으로 저장하는 자료구조이다. 해시테이블은 해시함수를 이용해 키를 해시값으로 변환한 후, 이 해시값을 인덱스로 사용해 배열의 특정 위치에 값을 저장하는 방식으로 동작한다. 키를 해시 함수로 계산한 결과를 배열의 인덱스로 변환해 저장하기에 값을 빠르게 검색할 수 있다.

저장

1. key의 해시코드 계산
2. 해시코드를 이용해 배열의 인덱스 구함
3. 키와 값을 해당 인덱스에 저장

조회

1. 찾고 싶은 key를 해시 함수에 넣음
2. 해시값을 구한 뒤, 해시값을 이용해 찾으려는 key 반환

이렇게되면, O(1) 시간 복잡도로 즉시 데이터에 접근 가능하다.

해시 충돌 (Hash Collision)

해시 충돌은 서로 다른 키가 같은 해시값을 가질 수 있다는 문제를 말한다. 다른 key가 해시함수를 적용했을 때 동일한 해시값을 가질 수 있다는 것이다.

이를 해결하기 위해 체이닝, 개방 주소법을 사용한다.

• 체이닝 : 충돌난 키들을 연결 리스트로 묶어 하나의 인덱스에 저장
• 개방 주소법 : 충돌 발생 시, 다른 빈 슬롯을 찾아 저장

시간 복잡도

연산	시간 복잡도 (평균)	설명
삽입(put)	O(1)	해시 계산 후 즉시 저장
조회(get)	O(1)	인덱스로 바로 접근
삭제(remove)	O(1)	동일 원리
최악의 경우	O(n)	해시 충돌이 많거나 버킷이 부족할 때

Java에서의 해시테이블

자바의 HashMap은 해시테이블의 대표적인 구현체이다.

import java.util.HashMap;

public class Example {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();

        // 데이터 저장
        map.put("홍길동", "010-1234-5678");
        map.put("이순신", "010-9876-5432");

        // 조회
        System.out.println(map.get("홍길동"));  // 010-1234-5678
    }
}

내부적으로 key 값을 해싱하여 배열 인덱스로 바꾸고 그 인덱스 위치에 value 값을 저장한다.

해시 암호와의 차이점

구분	해시 함수	해시테이블
목적	데이터 보호(암호화)	효율적인 데이터 검색을 위한 자료구조
결과물	고정 길이 해시값	인덱스
복호화 가능성	불가능	의미 없음