-
Hash Table , Hash Function 공부, 정리Programming/Computer Science 2022. 4. 18. 16:42
Hash Table
hash...hash tag...?
hash table개념은 생소하지만, hash tag는 익숙하다.
hash tag는 지정한 키워드를 걸어두면 "빠르게" 해당 키워드 내용이 검색에 걸리게 하는 알고리즘이다.
Hash Table은 Hash Function을 사용한다.
예시를 들어보자.
메뉴판이라는 데이터가 있고 내가 찾고싶은 것은 피자의 가격이다.
{
"치킨":20000,
"파스타":15000,
"햄버거세트":10000,
"피자":30000,
,,,
}
대충 이런 데이터셋이 있다고 한다면 위에서부터 하나하나 피자 key값을 찾게된다.
그런데 이 때 문제는 메뉴판 메뉴가 많을수록 피자를 찾는 시간이 오래 걸린다는 것이다.
이것을 해결하기 위한 개념이 Hash function이다.
array 의 index를 생각해보자.
치킨: 0
파스타:1
햄버거세트:2
피자:3
이렇게 숫자를 매칭해놓고
{
0 : 20000,
1 : 15000,
2 : 10000,
3 : 30000,
,,,
}
아까와 비슷하지만 array index가 붙은 데이터셋에서
피자의 값 3을 찾으면 바로 3을 찾을 수 있다.
처음의 검색방법과는 다른게 index는 순서가 정해져 있으므로 한번에 빠르게 3을 찾을 수 있는 것이다.
Hash Function
input을 랜덤한 output으로 바꿔준다.
규칙 1 인간이 보았을 때 전혀 관련이 없어보이도록(해독이 어렵도록)
규칙 2 같은 인풋은 언제나 같은 아웃풋을 낸다
규칙 3 일방향성. output에서 input을 얻을 수 없다
공부하면서 더 추가예정입니다.
참고
'Programming > Computer Science' 카테고리의 다른 글
[TIL] 230519 - 운영체제 / 프로세스 스레드 / CPU 스케줄링 (0) 2023.05.19 [TIL] 230516 코딩테스트, 시간복잡도 (0) 2023.05.17 개발자의 능력 척도 - 드라이퍼스 모델 (0) 2022.05.12 Redis 입문용 정리 (0) 2022.04.19 자료구조 공부, 정리 (0) 2022.04.18