해시
-
해시(Hash)와 해시 충돌 해결 방법CS(Computer Science)/Data Structure 2021. 11. 26. 16:08
1. 해시란? 💡 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑 해시 함수: 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다. 해시 테이블: 키와 값을 매핑해둔 데이터 구조이다. 해시 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장하여 효율적인 검색을 위해 사용된다. 1-1. 해시 순서 해당 원소의 해시 함수를 이용하여 해시값을 얻는다. 해시값을 주소로 하는 위치에 원소를 저장한다. 저장 후 검색 시에도 원소의 해시값으로 계산하여 해당 위치로 이동한다. 1-2. 사용 용도 무결성 검사: 파일 다운로드..
-
python 해시 테이블알고리즘/문제풀이 2020. 9. 20. 16:28
이번 시간에는 python 해시 관련하여 알아본다. python 해시 테이블 방식과 dict 자료형을 알아보고 자주 사용되는 모듈을 알아본다. 1. 파이썬 해시 테이블 파이썬에서 해시 테이블로 구현된 자료형은 딕셔너리다. 그렇다면 파이썬의 해시 테이블은 충돌 시 어떤 방식을 사용할까? 파이썬에는 오픈 어드레싱 방식으로 구현되어 있다. 파이썬에서 오픈 어드레싱 방식을 사용한 이유는 체이닝 시 malloc으로 메모리 할당하는 오버헤드가 높아서 오픈 어드레싱을 선택했다고 한다. 오픈 어드레싱 방식은 체이닝에 비해 성능이 좋다. 하지만 슬롯이 80% 이상 차게 되면 급격하게 성능 저하가 일어나며, 체이닝과 달리 로드 팩터 1 이상은 저장할 수 없다. 따라서 파이썬은 오픈 어드레싱 방식을 택해 성능을 높이지만 로..