Computer Science/Data Structure
2021. 11. 9.
[Data Structure] 해시
해시란 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것을 말한다. 데이터를 효율적으로 관리한다. 해시 함수를 통해 데이터 값을 해시 값으로 매핑한다. 해시 테이블을 사용하면 적은 자원으로 많은 데이터를 효율적으로 관리할 수 있다. 빠른 데이터 검색이 가능하다. 해시테이블의 시간 복잡도 : O(1) 해시의 특징 무결성 보안성 : 해시는 복호화가 불가능하다. Collision 현상 데이터가 많아지면서 다른 데이터가 같은 해시 값으로 충돌나는 현상이다. 충돌 문제 해결 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 선형 탐사 : 정해진 고정 폭으로 옮겨 해기값의 중복을 피함 제곱 탐사 :..