수업 | 자료구조 4차 수업
2/2 목 4:26~4:37 재청취 필요
출처: 김상헌 강사님 수업
#1. 해시 테이블
키key를 이용하여 값value를 (빠르게!) 알 수 있다.
장점:
- 빠른 데이터 읽기 / 삽입 / 삭제 가능. 시간 복잡도가 0(1)이다!
- 해시 함수를 통해 들어간 값들이기 때문에 어디 있는지 모두 기억되어 있어서 빨리 찾을 수 있다! 사람에 비유하자면 각각이 어디로 분류되어 있는지 외우고 있다고 보면 된다.
- 내가 이해한 것: 다이소에서 혹시 각티슈 어딨어요? 하고 여쭤보면 저기 11번 매대 중간에 보세요! 하고 알려주신다. 짱.
단점:
- 메모리를 많이 차지하고, 데이터 충돌collision 위험이 있다.
- 내가 이해한 것: 데이터 충돌이란 같은 자리에 여러 개의 값이 있는 경우. 목욕탕에서 25번 키를 받아 열었는데 누군가의 짐이 들어있다면 뭔가 단단히 잘못되었다고 생각하겠죠?
해시: 용어모음
해시
(동사) (to) hash
단방향 암호화 기법으로 해시함수를 이용해서 키를 고정된 길이의 암호화된 문자열(해시값)로 바꿔버리는 것.
키
매핑 전 데이터의 값. 평문으로, 즉 오리지널 값이다.
해시함수
다양한 길이의 들어오는 key(평문 = 오리지널 값)들을 미리 지정한 규칙에 의해 일정한 길이의 해시값(정수값- 숫자!)으로 바꿔주는 역할을 함.
해시값은 곧 인덱스가 된다.
이로 인해 저장소를 효율적으로 운영할 수 있음.
함수 규칙에 따라 들어간 값들은 기억해놓은 자리들이 있다보니 바로 조회가 가능함.
해시값
(명사) a hash value
매핑 후의 데이터 값 (해시 돌아가고 나서의 숫자 값. (해시값= 암호문!)
해싱
(동명사) hashing
매핑하는 과정.
해시 충돌collision
해시 함수에 따라 배정된 자리에 2개 이상의 값이 들어가서 데이터가 넘치는 것.
이 경우 같은 인덱스에 저장되고(인덱스에 값 n개!), 데이터는 연결리스트 방식으로 저장됨.
➜ 해결법! 체이닝 및 개방주소법
1) 체이닝
해시 충돌 시 데이터는 연결리스트 방식으로 저장됨.
최악의 경우 시간복잡도 0(n).
2) 개방주소법
해시 충돌 시 다른 index에 value 데이터를 삽입함.
개방주소법 종류 3가지!
1) 선형탐색: 다음 버킷(index)에 저장함
2) 제곱탑색: 제곱만큼 건너뛴 버킷에 저장함
3) 이중해시: 해시 충돌 시 다른 해시함수를 한 번 더 적용한 결과를 저장함
암호화 해시 함수
대표적으로 MD5, SHA1 가 있다.
➜ 들어가는 문자열 길이와 상관 없이 반환되는 해시의 길이는 일정함
해시 복호화?
SALT+해시함수를 알아내면 평문(오리지널 값)으로 복호화 할 수 있나요?
➜ 복호화는 양방향(암호-복호) 암호화에서만 가능함.
그래서 복호화를 못하게 하는 단방향 암호화를 사용해야 함!!
#2. 셋set
- 데이터의 중복을 허용하지 않는 자료구조(모든 값이 고유함!)
- key랑 value가 같을 때 셋을 선택함! (오...)
- 중복 제거할 때 가장 많이 쓰이는 방법임.
- 자료 검색 시 index 대신 key만 사용함.
- 순서가 존재하지 않음.
- 장점: 충돌 x , 빠른 속도 검색 o
- 배열과 비교했을 때: 셋쪽이 더욱 효율적으로 값을 포함하고 있는지 확인 가능함!
#3. 객체object VS 맵map
객체
- Key: string, symbol을 값으로 사용할 수 있음
- 크기: 수동으로 추적
- 사용 경우: 적용할 로직이 있을 때
맵
- Key: 모든 타입의 값을 사용할 수 있음
- 크기: 내부 프로퍼티
- 사용 경우:
1) 키를 알 수 없고
2) 모든 키와 값이 동일할 경우.
#4. 셋Set VS 배열Array
셋Set
- 중복 허용: Yes!!
- 인덱스 참조: 그건 안돼요...
배열Array
- 중복 허용: No!!
- 인덱스 참조: 됩니다.
기타
- iterable 객체인지 알고 싶으면: dir 찍어서 prototype에 symbol.iterator 있으면 맞음
- generator function에 대해 좀 알아볼까...
