💻 Algorithm
[알고리즘] Hash Table 해시 테이블 (매우 중요!)
date
Jul 11, 2023
slug
algorithm-hashtable
author
status
Public
tags
Tech
summary
type
Post
thumbnail
updatedAt
Jul 11, 2023 02:47 PM
category
💻 Algorithm
해시 테이블
해시테이블이란 무엇인가?
: key value system을 이용해서 자료를 정리한다.
ex) 사전
만약에, 1. 배열에 저장했을 때
그 안에서 pizze 값을 찾으려고 한다면
선형 검색을 한다. → 각각 아이템을 첫번째부터 끝까지 체크한다.
⇒ 시간이 매우 오래 걸린다. 이때 해시 테이블을 이용한다!
시간 복잡도: O(N)
2. 해시테이블에 저장했을 때,
key를 가지고 곧바로 value를 찾는다.
시간복잡도: O(1)
⇒ array랑 비교했을 때 매우 빠르다!
hash table 이용 기술:
key에 지정할 값을 설정하고, value는 그냥 모두 true로 설정한다.
그렇게 되면, key로 검색했을 때, 값이 있으면 true 반환을 해준다.
값이 없으면 undefined를 반환해서 딱 1번의 움직임으로 사용 가능하다.
해시테이블이 작동하는 원리
해시테이블에는 array 구조가 있다.
array 구조를 가져서 느릴것 같지만, 해시테이블이 빠른 이유는
hash function(해시 함수) 때문이다.
해시 함수가 내가 저장하고 싶은 key를 숫자로 바꾼다.
따라서 그 숫자 = 인덱스가 된다.
그리고 value에 값이 저장된다.
작동 원리를 설명하자면, 다음과 같다. 메뉴의 가격을 검색하는 상황이다.
- 만약에 cake라는 key가 있다.
- 이것을 해시 함수에 넣는다.
- 해시 함수는 cake를 세려서 4라는 값을 도출하고, 돌려준다.
- 그리고 리스트 4에 cake 가격을 저장한다.
해시 충돌
: 각기 다른 key에 대해서 해시함수가 동일한 숫자를 준 경우이다.
그럴 때 해결방법은 다음과 같다.
- 리스트 4에 두개의 쌍을 저장한다.
이렇게 되면 중복된 key값이 발생하더라도
value로 이동해서 두개의 쌍에서 음식의 가격을 찾는 선형 검색을 할 수 있다.
해시 충돌과 같은 이유로, 해시 테이블의 작동시간이 항상 상수 시간인 것은 아니다.
그러나 전체적인 이유로 O(1)을 갖는다. 해시테이블은 쉽고 빠르게 사용할 수 있다.