📍Hash
🔎 Hash 정의
- Key:Value의 구조를 갖는 자료구조
- 단방향 암호화 기법
- 해시 함수를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미
🔎 Hash 용어
- Key : 매핑 전 원래 데이터의 값
- Hash value : 매핑 후 데이터의 값(해쉬 테이블의 index)
- Hash table : (Index, value)의 집합
- Hashing : 매핑하는 과정
🔎 Hash 사용
- 해시 테이블
- 암호화
- 데이터 축약
📍해시 함수
🔎 해시 함수 정의
- 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수
🔎 해시 함수 특징
- 해시 함수 예시: SHA(Secure Hash Algorithm) 알고리즘
- 어떤 입력 값에도 항상 고정된 길이의 해시값을 출력
- 같은 입력 값(key)에 대해서는 같은 출력 값(index)가 출력
- 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 실행
🔎 해시 함수 사용 이유
- 효율적인 데이터 관리
- 빠른 데이터 처리
📍해시 충돌
🔎 해시 충돌 정의
- 해시 함수에서 입력 값의 범위보다 출력 값의 범위가 좁은 경우가 많기 때문에 입력 값이 다르더라도 동일한 값이 출력되는 경우
- 비밀번호, 전자서명, 전자투표, 전자상거래와 같은 민감한 정보의 무결성을 검증할 때 사용
🔎 해시 충돌 원인
적재율(load factor): 적재율이란 해시 테이블의 크기에 대한 키의 개수의 비율을 뜻한다. 즉 키의 개수를 K, 해시 테이블의 크기를 N이라고 했을 때 적재율은 K/N이다. -> 충돌이 발생할 경우에는 탐색과 삭제 연산이 O(K)만큼 걸리게 된다. 삽입은 그대로 O(1).
🔎 해시 충돌 해결 방법
➕ 분리 연결법(Separate Chaning)
해시 테이블의 크기를 유연하게 만들어 해결
➕ 개방 주소법(Open Addressing)
해시 테이블 크기는 고정시키되 저장해 둘 위치를 잘 찾는데 관점을 둠
📍해시 테이블
🔎 해시 테이블 정의
해시 함수를 사용하여 키를 해시 값으로 매핑하고, 매핑한 해시 값의 인덱스 주소 값과 키를 함께 저장하는 자료구조
🔎 해시 테이블 특징
- 인덱스 주소와 값이 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다.
- 평균 O(1)의 시간복잡도
🔎 해시 테이블 과정
충분히 큰 공간을 할당 받은 다음, 해시 함수를 이용하여 고유 색인(index)을
-> 고유 인덱스와 맞는 위치에 데이터를 저장(매핑)
📍스터디 회고
🔎 아쉬운 점
생각보다 공부할 내용이 많아서 자세하게 하지 못한게 아쉬웠다.
추가로 더 공부해 봐야겠다
🔎 추가로 알게 된 내용
🔎 추가로 공부할 내용
📍공부한 곳
https://velog.io/@edie_ko/hashtable-with-js
https://growth-msleeffice.tistory.com/93
https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
https://dbehdrhs.tistory.com/70
공부하자