[자료구조] 해시(Hash)

DevelopHeo·2024년 8월 25일
자료구조
0
post-thumbnail

1. 해시의 특징

  • 해시는 저장 또는 검색 등에서 자주 활용되는 자료구조입니다.
  • 정확하게는 특정한 함수(알고리즘)를 통해서 값을 추출학고 활용하는 것.
  • 해시는 더 나아가서 암호, 블록체인, 메시지 인증 코드 등에서 활용 됩니다!
  • 키(KEY)에 데이터(Value)를 매핑할 수 있는 데이터 구조
  • 해시 함수를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스 번호)를 계산
  • 키를 통해서 저장된 데이터를 빠르게 찾고, 저장 및 탐색 속도가 획기적으로 빨리짐

해시(Hash)

  • 해시(Hash)는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말합니다.
    • 다른 말로는 해시 값(Hash value), 해시 코드 ,체크섬 이라고도 합니다.
  • 이러한 해시는 '해시 함수'에 의해서 얻게 됩니다.
    • 데이터의 KEY 값이 해시 함수를 통해서 변환된 간단한 정수입니다.
    • 이렇게 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용 됩니다.

시간 복잡도

  • 해시 자료구조는 충돌이 없는 일반적인 경우는 O(1)이 발생합니다. (키를 통해 바로 저장과 검색을 하여 값을 구하기 때문)
  • 최악의 경우, 즉 모든 index에서 충돌이 발생할 경우는 O(n) 발생합니다.

2. 해시 테이블(Hash Table)

키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

  • 테이블은 키와 값을 함께 저장해 둔 데이터 구조입니다.
  • 테이블에 데이터를 저장할 때 위치는 무작위로 지정되어 작성됩니다.
  • 따라서 중간에 여유 공간이 발생할 수 있습니다.
  • 버킷(bucket) : 하나의 주소를 갖는 파일의 한 구역, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수
  • 슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간, 한 버킷 안에 여러 개의 슬롯이 있음

3. 해싱(Hashing)

해싱은 해시 함수에서 해시를 출력하고, 해시 테이블에 저장하는 과정까지의 행위

4. 해시의 장단점과 용도

1) 장점

  • 데이터 저장 / 읽기 속도가 빠름(검색 속도가 빠름)
  • 해시는 키에 대한 데이터가 있는지 확인이 쉬움

2) 단점

  • 일반적으로 저장공간이 많이 필요(메모리 공간)
  • 여러 키에 해당하는 주소(인덱스)가 동일한 경우 충돌을 해결하기 위한 별도 자료구조 필요

3) 주요 용도

  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현

5. 해시 구현하기

기본적인 해시 테이블 구현

https://github.com/Si-Hyeak-KANG/java_algorithm/blob/master/src/dataStructureSudy/base01/Hash.java

실행

    public static void main(String[] args) {

        Hash myHash = new Hash(20);

        myHash.saveData("Lee","30000");
        myHash.saveData("James","15000");
        myHash.saveData("Denny","5000");

        System.out.println(myHash.getData("Lee"));
        System.out.println(myHash.getData("James"));
        System.out.println(myHash.getData("Denny"));

    }

결과

30000
15000
5000

HashMap과 Hashtable

  • HashMap과 Hashtable 모두 Map 인터페이스를 구현한 클래스
  • 거의 비슷하지만 다른 점은 "동시성 문제"
  • Hashtable은 Thread-safe하고, HashMap은 그렇지 않습니다.
  • 따라서 멀티스레드 환경에서는 Hashtable을 싱글스레드 환경에서는 HashMap을 사용해야 할 것입니다.
  • HashMap : not synchronized, Thread-safe X -> single thread
  • Hashtable : synchronized, Thread safe -> multi thread

HashTable은 JDK 1.0부터 있던 Java의 API이고,
HashMap은 Java 2에서 처음 선보인 Java Collections Framework에 속한 API이다.
HashTable은 구현에 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 업데이트 되고 있다고 한다.

따라서 왠만하면 HashMap을 사용하고, 멀티스레드 환경에서는 ConcurrentHashMap를 사용하는게 좋습니다.

HashMap 선언

HashMap, Hashtable 모두 Map 인터페이스를 구현한 클래스이기 때문에 아래와 같이 Map형으로 선언할 수 있습니다.

HashMap<String,Integer> hashMap = new HashtMap<>();
Hashtable<String,Integer> hashtalbe = new Hashtable<>();

Map<String,Integer> map1 = new HashtMap<>();
Map<String,Integer> map2 = new Hashtable<>();

Methods

put() : 값 넣기

  • put(K,V) : 데이터 쌍 넣기
  • putIfAbsent(K,V) : 이미 있으면 그대로, 없으면 값 넣어줌.
Map<String,Integer> map = new HashMap<>();
map.put("A", 1);//{A=1}
map.put("B", 3);//{A=1, B=3}
map.putIfAbsent("C", 5);//{A=1, B=3, C=5}
map.putIfAbsent("C", 7);//{A=1, B=3, C=5}

get() : 값 조회

  • get(K) : Key에 해당하는 value 꺼내기
  • getOrDefault(K, default) : Key에 해당하는 value를 꺼내거나 , 없으면 default값 꺼내기
  • keySet() : K들만 뽑아냄
  • values() : V들만 뽑아냄
//{A=1, B=3, C=5}
int a = map.get("A"); //a = 1
int e = map.getOrDefault("E",-1); //e = -1

System.out.println(map.keySet()); //[A, B, C]
System.out.println(map.values()); //[1, 3, 5]

remove() : 값 삭제

  • remove(K) : K에 해당하는 값 삭제 + 삭제되는 V return
  • remove(K, V) : K와 V 모두 존재할때만 삭제 + true,false로 출력도 가능
//{A=2, B=4, C=10}
map.remove("A");// {B=4, C=10}
map.remove("C", 11); //{B=4, C=10}
map.remove("C", 10); //{B=4}

replace () : 값 교체

  • replace(K,V) : 교체
  • replace(K,old V, new V) : old Value가 일치할때만 new Value로 교체
  • 이미 존재하는 key에 put()메서드를 이용해서 값을 넣으면 새로 넣은 값으로 변경된다.
//{A=1, B=3, C=5}
map.replace("B", 4); //{A=1, B=4, C=5}
map.replace("C",6); //{A=1, B=4, C=6}
map.replace("C",6,10); //{A=1, B=4, C=10}
map.replace("C",6,12 ); //{A=1, B=4, C=10} => C=6이 아니기때문에 값은 그대로.

map.put("A",2); //{A=2, B=4, C=10}

기타 기능

size(), isEmpty(), clear()

  • size() : map의 사이즈를 반한
  • isEmpty() : map이 비어있는지 여부를 boolean으로 반환
  • clear() : map의 데이터를 모두 삭제
  • containsKey(), containsValue() : 값이 존재하는지 확인한다.
//{A=1, B=3, C=5}
System.out.println(map.containsKey("A")); //true
System.out.println(map.containsValue("5")); //true
System.out.println(map.containsValue("7")); //false

6. 충돌(Collision)

해시에서는 입력받은 키의 첫 번째 문자를 배열의 크기로 나눈 나머지를 인덱스로 사용합니다.

만약 다른 키가 있는데 이 키의 첫 번째 문자가 동일핟다면, 인덱스는 동일하게 반환될 것이니다.
그럼 배열에서 같은 장소에 저장되고, 이전에 저장된 정보는 사라질 것입니다.
이를 충돌이 발생했다고 하는데요. 또는 Collision이라고 합니다.

충돌 발생 이유 2가지

  1. 함수 알고리즘의 성능이 좋지 못하여 발생
  2. 저장되는 데이터 양이 해시 테이블의 크기보다 클 때

충돌 해결하기

1) Chaining 기법

  • 개방 해싱 또는 Open Hashing 기법 중 하나 : 해시 테이블 저장공간 외의 공간을 활용하는 기법
  • 충돌이 발생했을 때, 연결 리스트(Linked List) 자료구조를 사용해서 해결하는 방법

Chaining 기법을 구현한 코드
https://github.com/Si-Hyeak-KANG/java_algorithm/blob/master/src/dataStructureSudy/base01/Hash_Chaining.java

2) Linear Probing 기법

  • 폐쇄 해싱 또는 Close Hashing 기법 중 하나 : 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
  • 충돌이 발생했을 때, 해당 해시 주소(index)의 다음 주소(index)부터 맨 처음까지 순회하며 빈 공간을 찾는 방식
  • 저장공간 활용도를 높이기 위한 기법

Linear Probing 기법은 해시 함수를 통해서 얻은 주소(인덱스)에 이미 데이터가 있다면, 다음 주소를 체크합니다. 만약 체크했을 때 데이터가 없다면, 해당 자리에 저장이 됩니다.

Linear Probing 기법을 구현한 코드
https://github.com/Si-Hyeak-KANG/java_algorithm/blob/master/src/dataStructureSudy/base01/Hash_LinearProbing.java

7. 실습문제

profile
DevelopHeo
다음 포스트

[Spring]DI

0개의 댓글