날짜를 확인해보니 세상에 마지막 알고리즘 포스트를 쓴지 벌써 8개월이나 됐다.
네이버 부스트캠프가 끝나고 지원서 작성 때문에
자소서 쓰고, 포트폴리오 수정하고, 학교도 다니고(학점을 들 채웠다ㅠ)해야 된다는 핑계(?)로
기술블로그에 너무 소홀히 한 것 같다. 이젠 진짜 써야 된다!! (기술블로그 스터디에 들어간 1인^^)
아무튼 그래서 오늘 프로그래머스의 알고리즘 고득점-kit 해시 문제를 풀어보러 갔다.
해시가 뭐였지 큰일났다..
Hash(해시)란?
출처: https://hsp1116.tistory.com/35
해시는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다.
해시 알고리즘은 해쉬를 하는 방법에 대해 절차적으로 명세한다.
이를 이용해 특정한 배열의 인덱스나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.
기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던 것에 비해,
해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.
Direct Addressing Table
key-value 쌍의 데이터를 배열에 저장할 때
key 값을 직접적으로 배열의 인덱스로 사용하는 방법이다.
예를 들면 key=400인 데이터는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다.
똑같은 키 값이 존재하지 않는다고 가정하면, 삽입 시에는 각 키마다 자신의 공간이 존재하므로 그 위치에다 저장을 하면 되고,
삭제 시에는 해당 키의 위치에 NULL값을 넣어주면 된다. 탐색 시에는 해당 키의 위치를 그냥 찾아가서 참조하면 된다.
찾고자 하는 데이터의 key만 알고 있으면 즉시 위치를 찾는 것이 가능하므로 탐색, 저장, 삭제, 갱신은 모두 선형시간인 O(1)으로 매우 빠른 속도로 처리가 가능하다.
다만 key값의 최대 크기만큼 배열이 할당되기 때문에, 크기는 매우 큰데, 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 있다.
Hash Table
Hash Table은 key-value 쌍에서 key값을 테이블에 저장할 때, Direct Addressing Table과 달리 key 값을 함수를 이용해 계산을 수행한 후, 그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다.
여기서 key값을 계산하는 함수는 해쉬 함수(Hash Function)이라고 부르며, 해쉬 함수는 입력으로 key를 받아, 0부터 배열의 크기-1 사이의 값을 출력한다. 해쉬에 대한 첫 정의대로 임의의 숫자를 배열의 크기만큼으로 변환시킨 것이다.
이 경우 k값이 h(k)로 해쉬되었다고 하며, h(k)는 k의 해쉬값이라고 한다.
위 그림을 참조하면 각 k값들의 해쉬값인 h(k)값들이 배열의 인덱스로 사용됨을 확인할 수 있다.
해쉬 테이블은 Direct Addressing Table에 비해 공간 낭비가 매우 적은데 이는 key값의 크기에 테이블의 크기가 좌우되는 것이 아니고, h(k)만큼의 공간에 저장되기 때문이다.
탐색 알고리즘
갑분 탐색 알고리즘. 다른 블로그 타고타고 들어가다 발견하고 정리하고 싶어져서ㅎ
체계 없는 내 블로그~ㅋㅋ
출처: https://adjh54.tistory.com/193
해시탐색은 탐색 알고리즘 중 하나이다.
코테 공부할 때 봤던 브루트 포스, 백트레킹, DFS, BFS, ... 이렇게 묶이는 거였다니
이걸 몰랐어? 이제라도 알았으니 다행이지 뭐!
💡 탐색 알고리즘 (Searching Algorithm)
- 데이터 구조 내에서 필요한 정보를 빠르게 찾아내는 데 사용되는 알고리즘입니다.
- 탐색 알고리즘의 종류에 따라 데이터의 크기와 구조 그리고 찾고자 하는 정보의 특성에 따라 탐색 시간이 달라질 수 있습니다.
- 따라서 효율적인 탐색 알고리즘을 선택하여 사용하면 비용과 시간을 크게 절약할 수 있습니다.
탐색 알고리즘의 종류와 시간복잡도는 다음과 같다.
시간 복잡도
~시간 복잡도 복습~
💡 시간 복잡도(Time Complexity)
- 알고리즘이 실행될 때 필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 효율적인 알고리즘을 나타내는 척도를 의미합니다.
해시 알고리즘
💡 해시 알고리즘 (Hash Algorithm)
- 데이터를 빠르게 저장하고 검색하기 위한 알고리즘으로 ‘키(key)’를 사용하여 ‘데이터 값(value)’을 조회하는 방법을 의미합니다. 이러한 ‘키-값’을 ‘해시 테이블’이라는 데이터 구조에 저장하여 키에 매핑되는 인덱스 값으로 빠르게 찾을 수 있습니다.
- 키는 해시 함수를 통과하여 해시 값으로 변환되며 이 해시 값은 데이터가 저장되는 배열의 인덱스를 결정합니다.
해시 알고리즘 처리 방식
💡 해시 알고리즘 처리 방식
- key, value의 형태의 해시는 해시 함수를 통해서 key의 값은 ‘고유한 해시값’으로 변환이 됩니다.
- 이 변환된 해시 값을 기반으로 ‘해시 인덱스’를 결정하여 해시 테이블에는 해시 인덱스와 고유한 해시 값이 저장이 됩니다.
- 탐색을 위해서는 key를 호출하면 인덱스를 찾아서 값을 반환해 주기에 빠르게 조회가 가능합니다.
- 키(Key)
- 문자열 혹은 정수 형태로 구성된 키이며, key-value 형태로 실제 데이터 구조를 가지고 있습니다. 이 중 키는 실제 데이터를 찾기 위해 사용되는 고유 식별자를 의미합니다.
- 해당 과정에서는 Key 값은 해시함수(Hash Function)로 전달되어 처리가 됩니다.
- 해시 함수(Hash Function)
- 전달받은 키(Key) 값을 통해서 해시 함수가 수행이 됩니다. 이 해시 함수 내에서는 키를 ‘고유한 해시값’으로 변환합니다.
- 또한 변환된 해시 값은 해시 테이블(Hash Table)의 해시 인덱스(Hash Index)로 저장이 됩니다.
- 해시 테이블(Hash Table)
- 해시 함수로 전달받은 ‘고유한 해시값’을 기반으로 ‘해시 인덱스(Hash Index)’를 결정하고, 해시 값(Hash Value)은 실제 값이 들어갑니다.
- 고유한 해시값을 가지고 있기에 ‘키’를 통해서 빠르게 값을 검색할 수 있습니다.
[ 더 알아보기 ]
💡 Hash Function이 처리된 값을 Hash Table에 저장하는 과정을 보면 저장 순서가 보장되지 않는 거네?
- 해시 알고리즘은 데이터를 빠르게 검색하고 찾기 위한 목적으로 설계된 알고리즘입니다. 이 알고리즘은 키(key)를 해시 함수를 통해 고유한 해시 값으로 변환하는 방식으로 작동합니다. 이 과정에서 키(key)의 원래 순서는 사라지게 됩니다.
- 결과적으로, 해시 알고리즘과 해시 기반의 데이터 구조는 데이터의 빠른 검색과 접근을 우선시하며, 이를 위해 데이터의 입력 순서나 정렬 상태를 보장하지 않습니다. 이러한 특징은 알고리즘의 효율성과 속도를 높이는 데 중요한 역할을 합니다.
해시 함수
💡 해시 함수(Hash Function)
- h(x)에서 'h'에 해당하는 거가 해시 함수
- 해시 함수 'h'가 key값 'x'를 받아서 해시값 'h(x)'으로 변환시킴
- 이 해시값들은 '해시 테이블'의 '해시 인덱스'로 저장됨
- '해시 인덱스'는 데이터의 저장 및 검색에 활용됨
- '해시값' 데이터는 고정된 길이의 동일한 크기의 데이터로 매핑을 수행함
- 즉 key는 고유한 값과 동일한 크기를 갖는 해시로 변환됨
- 하나의 키가 항상 동일한 해시 값을 생성하도록 설계하게 되어 있어서 데이터 검색 시 원하는 데이터를 빠르게 찾아낼 수 있음
- 하지만, 다른 키가 동일한 해시 값을 생성하게 되면 해시 충돌이 발생하게 되며, 이를 처리하기 위한 여러 방법들이 존재함
key값 --h해시함수--> hash값 --> data 매핑
[ 더 알아보기 ]
💡 해시 키 값이 인덱스와 같이 00, 01로 들어가는 건 예시로 보여주는 거지?
- 맞습니다. 해시 값은 예시로 보여주기 위한 것이며 실제는 '해시 값'이 들어가게 됩니다.
해시 테이블
💡 해시 테이블 (Hash Table)
- '키(key)'와 '값(value)'을 매핑하는 데이터 구조를 가집니다. 이 구조에서 해시 함수를 사용하여 키를 ‘고유한 해시 값’으로 변환되고 이 해시 값은 배열의 ‘인덱스’로 사용됩니다. 따라서 키를 통해 값을 빠르게 검색할 수 있습니다.
- 하지만 서로 다른 키가 동일한 해시 값을 가질 경우, 즉 해시 충돌이 발생할 경우, 체이닝과 같은 방법을 사용하여 충돌을 해결할 수 있습니다.
해시 테이블 요소 : 키, 인덱스(해시값), 버킷(해시값이 동일한 항목을 저장하는 공간, 연결리스트)
해시 충돌
💡 해시 충돌(Hash Collision)
- 서로 다른 키가 동일한 해시 값을 가질 때 발생하는 현상입니다. 이는 해시 함수의 특성상 피할 수 없는 문제로 이를 해결하기 위한 다양한 기법들이 존재합니다.
💡 해시 충돌(Hash Collision) 예시
- key = 10, key = 15인 값이 두 개가 존재한다고 가정할 때, 이를 해시 함수(Hash Function)를 통해서 수행을 하면 ‘해시 값’으로 변환이 됩니다.
- 이 변환된 해시 값은 해시 테이블(Hash Table) 내의 해시 인덱스(Hash Index)로 저장이 되는 시점에 ‘동일한 해시 값’을 가지는 문제가 발생합니다.
💡 해시 충동 해결방법(Collision Resolution Technique) 종류
- Separate Chaining (Open Hashing)
- Open Addressing (Closed Hashing)
ㄴ 선형 탐사 (Linear Probing)
ㄴ 이차 탐사 (Quadratic Probing)
ㄴ 더블 해싱 (Duble Hashing)
Separate Chaining (Open Hashing)
💡 Separate Chaining (Open Hashing)
- 같은 해시 값을 가진 항목들을 연결 리스트로 관리하는 방법을 말합니다. 이 방법은 해시 값이 같은 모든 키-값 쌍을 하나의 연결 리스트에 저장하므로, 충돌이 발생하면 해당 리스트에 추가하는 방식으로 충돌을 해결합니다.
Open Addressing (Closed Hashing)
💡 Open Addressing(Closed Hashing)
- 해시 테이블에서 충돌이 발생하면, 다른 빈 위치를 찾아 데이터를 저장하는 방법을 말합니다.
- 이 방식은 선형 탐사, 이차 탐사, 더블 해싱 등의 방법이 있습니다.
해시 알고리즘의 시간 복잡도
💡 해시 알고리즘의 시간 복잡도
- 배열을 저장하는 데 시간 복잡도는 O(1) 시간이 걸리지만 검색하는 데는 '최소한' O(log n) 시간이 걸립니다. (이진 탐색 알고리즘 - O(log n)
- 이 시간은 짧은 것처럼 보이지만 큰 데이터 세트의 경우 많은 문제가 발생할 수 있으며 이로 인해 Array 데이터 구조가 비효율적입니다.
Reference
